From 328dda4ba39461638435e9723034a26287238c3c Mon Sep 17 00:00:00 2001 From: Philip Pronin Date: Wed, 27 May 2015 18:06:40 -0700 Subject: [PATCH] drop V0 of EliasFanoEncoder Summary: Cleanup. Drop support for V0 in favor of V1. Test Plan: unit tests Reviewed By: lucian@fb.com Subscribers: fbcode-common-diffs@, chaoyc, search-fbcode-diffs@, unicorn-diffs@, folly-diffs@, yfeldblum, tudort, chalfant FB internal diff: D2105967 Signature: t1:2105967:1432781247:e420d8b4b8c69d28dfc229e8a2af6df8a580f979 --- folly/experimental/EliasFanoCoding.h | 65 +++++-------------- .../experimental/test/EliasFanoCodingTest.cpp | 46 +++++-------- 2 files changed, 33 insertions(+), 78 deletions(-) diff --git a/folly/experimental/EliasFanoCoding.h b/folly/experimental/EliasFanoCoding.h index e5440184..ee4920ab 100644 --- a/folly/experimental/EliasFanoCoding.h +++ b/folly/experimental/EliasFanoCoding.h @@ -74,16 +74,11 @@ struct EliasFanoCompressedList { folly::ByteRange forwardPointers; }; -// Version history: -// In version 1 skip / forward pointers encoding has been changed, -// so SkipValue = uint32_t is able to address up to ~4B elements, -// instead of only ~2B. template -struct EliasFanoEncoder { + size_t kForwardQuantum = 0> // 0 = disabled +struct EliasFanoEncoderV2 { static_assert(std::is_integral::value && std::is_unsigned::value, "Value should be unsigned integral"); @@ -95,7 +90,6 @@ struct EliasFanoEncoder { static constexpr size_t skipQuantum = kSkipQuantum; static constexpr size_t forwardQuantum = kForwardQuantum; - static constexpr size_t version = kVersion; static uint8_t defaultNumLowerBits(size_t upperBound, size_t size) { if (size == 0 || upperBound < size) { @@ -116,14 +110,14 @@ struct EliasFanoEncoder { if (begin == end) { return EliasFanoCompressedList(); } - EliasFanoEncoder encoder(end - begin, *(end - 1)); + EliasFanoEncoderV2 encoder(end - begin, *(end - 1)); for (; begin != end; ++begin) { encoder.add(*begin); } return encoder.finish(); } - EliasFanoEncoder(size_t size, ValueType upperBound) { + EliasFanoEncoderV2(size_t size, ValueType upperBound) { if (size == 0) { return; } @@ -160,11 +154,8 @@ struct EliasFanoEncoder { // 0-bit in upper bits sequence. size_t numSkipPointers = 0; /* static */ if (skipQuantum != 0) { - /* static */ if (kVersion > 0) { - CHECK_LT(size, std::numeric_limits::max()); - } else { - CHECK_LT(upperSizeBits, std::numeric_limits::max()); - } + CHECK_LT(size, std::numeric_limits::max()); + // 8 * upperSize is used here instead of upperSizeBits, as that is // more serialization-friendly way (upperSizeBits isn't known outside of // this function, unlike upperSize; thus numSkipPointers could easily be @@ -181,12 +172,8 @@ struct EliasFanoEncoder { // 1-bit in upper bits sequence. size_t numForwardPointers = 0; /* static */ if (forwardQuantum != 0) { - /* static */ if (kVersion > 0) { - CHECK_LT(upperBound >> numLowerBits, - std::numeric_limits::max()); - } else { - CHECK_LT(upperSizeBits, std::numeric_limits::max()); - } + CHECK_LT(upperBound >> numLowerBits, + std::numeric_limits::max()); // '?: 1' is a workaround for false 'division by zero' compile-time error. numForwardPointers = size / (forwardQuantum ?: 1); @@ -226,26 +213,16 @@ struct EliasFanoEncoder { /* static */ if (skipQuantum != 0) { while ((skipPointersSize_ + 1) * skipQuantum <= upperBits) { - /* static */ if (kVersion > 0) { - // Since version 1, just the number of preceding 1-bits is stored. - skipPointers_[skipPointersSize_] = size_; - } else { - skipPointers_[skipPointersSize_] = - size_ + (skipPointersSize_ + 1) * skipQuantum; - } - ++skipPointersSize_; + // Store the number of preceding 1-bits. + skipPointers_[skipPointersSize_++] = size_; } } /* static */ if (forwardQuantum != 0) { if ((size_ + 1) % forwardQuantum == 0) { const auto pos = size_ / forwardQuantum; - /* static */ if (kVersion > 0) { - // Since version 1, just the number of preceding 0-bits is stored. - forwardPointers_[pos] = upperBits; - } else { - forwardPointers_[pos] = upperBits + size_ + 1; - } + // Store the number of preceding 0-bits. + forwardPointers_[pos] = upperBits; } } @@ -389,13 +366,9 @@ class UpperBitsReader { folly::loadUnaligned( forwardPointers_ + (steps - 1) * sizeof(SkipValueType)); - /* static */ if (Encoder::version > 0) { - reposition(dest + steps * q); - } else { - reposition(dest); - } + reposition(dest + steps * q); n = position_ + 1 - steps * q; // n is > 0. - // correct inner_ will be set at the end. + // Correct inner_ will be set at the end. } size_t cnt; @@ -429,13 +402,9 @@ class UpperBitsReader { folly::loadUnaligned( skipPointers_ + (steps - 1) * sizeof(SkipValueType)); - /* static */ if (Encoder::version > 0) { - reposition(dest + q * steps); - position_ = dest - 1; - } else { - reposition(dest); - position_ = dest - q * steps - 1; - } + reposition(dest + q * steps); + position_ = dest - 1; + // Correct inner_ and value_ will be set during the next() // call at the end. diff --git a/folly/experimental/test/EliasFanoCodingTest.cpp b/folly/experimental/test/EliasFanoCodingTest.cpp index 1453811b..a79b701b 100644 --- a/folly/experimental/test/EliasFanoCodingTest.cpp +++ b/folly/experimental/test/EliasFanoCodingTest.cpp @@ -26,67 +26,53 @@ using namespace folly::compression; -#if defined(EF_TEST_NEHALEM) -#define EF_TEST_ARCH Nehalem -#elif defined(EF_TEST_HASWELL) -#define EF_TEST_ARCH Haswell -#else +#ifndef EF_TEST_ARCH #define EF_TEST_ARCH Default -#endif - -template -struct TestType { - static constexpr size_t Version = kVersion; -}; +#endif // EF_TEST_ARCH -template class EliasFanoCodingTest : public ::testing::Test { public: void doTestEmpty() { - typedef EliasFanoEncoder Encoder; + typedef EliasFanoEncoderV2 Encoder; typedef EliasFanoReader Reader; testEmpty(); } template void doTestAll() { - typedef EliasFanoEncoder< - uint32_t, uint32_t, kSkipQuantum, kForwardQuantum, T::Version> Encoder; + typedef EliasFanoEncoderV2< + uint32_t, uint32_t, kSkipQuantum, kForwardQuantum> Encoder; typedef EliasFanoReader Reader; testAll(generateRandomList(100 * 1000, 10 * 1000 * 1000)); testAll(generateSeqList(1, 100000, 100)); } }; -typedef ::testing::Types, TestType<1>> TestTypes; -TYPED_TEST_CASE(EliasFanoCodingTest, TestTypes); - -TYPED_TEST(EliasFanoCodingTest, Empty) { - TestFixture::doTestEmpty(); +TEST_F(EliasFanoCodingTest, Empty) { + doTestEmpty(); } -TYPED_TEST(EliasFanoCodingTest, Simple) { - TestFixture::template doTestAll<0, 0>(); +TEST_F(EliasFanoCodingTest, Simple) { + doTestAll<0, 0>(); } -TYPED_TEST(EliasFanoCodingTest, SkipPointers) { - TestFixture::template doTestAll<128, 0>(); +TEST_F(EliasFanoCodingTest, SkipPointers) { + doTestAll<128, 0>(); } -TYPED_TEST(EliasFanoCodingTest, ForwardPointers) { - TestFixture::template doTestAll<0, 128>(); +TEST_F(EliasFanoCodingTest, ForwardPointers) { + doTestAll<0, 128>(); } -TYPED_TEST(EliasFanoCodingTest, SkipForwardPointers) { - TestFixture::template doTestAll<128, 128>(); +TEST_F(EliasFanoCodingTest, SkipForwardPointers) { + doTestAll<128, 128>(); } namespace bm { constexpr size_t k1M = 1000000; -constexpr size_t kVersion = 1; -typedef EliasFanoEncoder Encoder; +typedef EliasFanoEncoderV2 Encoder; typedef EliasFanoReader Reader; std::vector data; -- 2.34.1