2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
23 #include <folly/Benchmark.h>
24 #include <folly/experimental/EliasFanoCoding.h>
25 #include <folly/experimental/Select64.h>
26 #include <folly/experimental/test/CodingTestUtils.h>
28 using namespace folly::compression;
31 #define EF_TEST_ARCH Default
32 #endif // EF_TEST_ARCH
36 uint8_t slowDefaultNumLowerBits(size_t upperBound, size_t size) {
37 if (size == 0 || upperBound < size) {
40 // floor(log(upperBound / size));
41 return uint8_t(folly::findLastSet(upperBound / size) - 1);
46 TEST(EliasFanoCoding, defaultNumLowerBits) {
47 // Verify that slowDefaultNumLowerBits and optimized
48 // Encoder::defaultNumLowerBits agree.
49 static constexpr size_t kNumIterations = 2500;
50 auto compare = [](size_t upperBound, size_t size) {
51 using Encoder = EliasFanoEncoderV2<size_t>;
52 EXPECT_EQ(int(slowDefaultNumLowerBits(upperBound, size)),
53 int(Encoder::defaultNumLowerBits(upperBound, size)))
54 << upperBound << " " << size;
56 auto batch = [&compare](size_t initialUpperBound) {
57 for (size_t upperBound = initialUpperBound, i = 0;
60 // Test "size" values close to "upperBound".
61 for (size_t size = upperBound, j = 0; j < kNumIterations; ++j, --size) {
62 compare(upperBound, size);
64 // Sample "size" values between [0, upperBound].
65 for (size_t size = upperBound;
66 size > 1 + upperBound / kNumIterations;
67 size -= 1 + upperBound / kNumIterations) {
68 compare(upperBound, size);
70 // Test "size" values close to 0.
71 for (size_t size = 0; size < kNumIterations; ++size) {
72 compare(upperBound, size);
76 batch(std::numeric_limits<size_t>::max());
77 batch(kNumIterations + 1312213123);
78 batch(kNumIterations);
81 std::uniform_int_distribution<size_t> distribution;
82 for (size_t i = 0; i < kNumIterations; ++i) {
83 const auto a = distribution(gen);
84 const auto b = distribution(gen);
85 compare(std::max(a, b), std::min(a, b));
89 class EliasFanoCodingTest : public ::testing::Test {
92 typedef EliasFanoEncoderV2<uint32_t, size_t> Encoder;
93 typedef EliasFanoReader<Encoder> Reader;
94 testEmpty<Reader, Encoder>();
97 template <size_t kSkipQuantum, size_t kForwardQuantum, class SizeType>
99 typedef EliasFanoEncoderV2<
100 uint32_t, uint32_t, kSkipQuantum, kForwardQuantum> Encoder;
102 EliasFanoReader<Encoder, instructions::EF_TEST_ARCH, false, SizeType>;
103 testAll<Reader, Encoder>({0});
104 testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
105 testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
109 TEST_F(EliasFanoCodingTest, Empty) {
113 TEST_F(EliasFanoCodingTest, Simple) {
114 doTestAll<0, 0, uint32_t>();
115 doTestAll<0, 0, size_t>();
118 TEST_F(EliasFanoCodingTest, SkipPointers) {
119 doTestAll<128, 0, uint32_t>();
120 doTestAll<128, 0, size_t>();
123 TEST_F(EliasFanoCodingTest, ForwardPointers) {
124 doTestAll<0, 128, uint32_t>();
125 doTestAll<0, 128, size_t>();
128 TEST_F(EliasFanoCodingTest, SkipForwardPointers) {
129 doTestAll<128, 128, uint32_t>();
130 doTestAll<128, 128, size_t>();
133 TEST_F(EliasFanoCodingTest, Select64) {
134 typedef instructions::EF_TEST_ARCH instr;
135 constexpr uint64_t kPrime = uint64_t(-59);
136 for (uint64_t x = kPrime, i = 0; i < (1 << 20); x *= kPrime, i += 1) {
137 size_t w = instr::popcount(x);
138 for (size_t k = 0; k < w; ++k) {
139 auto pos = folly::select64<instr>(x, k);
140 CHECK_EQ((x >> pos) & 1, 1);
141 CHECK_EQ(instr::popcount(x & ((uint64_t(1) << pos) - 1)), k);
146 TEST_F(EliasFanoCodingTest, BugLargeGapInUpperBits) { // t16274876
147 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 2, 2> Encoder;
148 typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
149 constexpr uint32_t kLargeValue = 127;
151 // Build a list where the upper bits have a large gap after the
152 // first element, so that we need to reposition in the upper bits
153 // using skips to position the iterator on the second element.
154 std::vector<uint32_t> data = {0, kLargeValue};
155 for (uint32_t i = 0; i < kLargeValue; ++i) {
156 data.push_back(data.back() + 1);
158 auto list = Encoder::encode(data.begin(), data.end());
162 ASSERT_TRUE(reader.skipTo(kLargeValue - 1));
163 ASSERT_EQ(kLargeValue, reader.value());
164 ASSERT_EQ(0, reader.previousValue());
172 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 128, 128> Encoder;
173 typedef EliasFanoReader<Encoder> Reader;
175 std::vector<uint32_t> data;
176 std::vector<size_t> order;
178 std::vector<uint32_t> encodeSmallData;
179 std::vector<uint32_t> encodeLargeData;
181 std::vector<std::pair<size_t, size_t>> numLowerBitsInput;
183 typename Encoder::MutableCompressedList list;
188 data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
189 list = Encoder::encode(data.begin(), data.end());
191 order.resize(data.size());
192 std::iota(order.begin(), order.end(), size_t());
193 std::shuffle(order.begin(), order.end(), gen);
195 encodeSmallData = generateRandomList(10, 100 * 1000, gen);
196 encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
198 std::uniform_int_distribution<size_t> distribution;
199 for (size_t i = 0; i < 10000; ++i) {
200 const auto a = distribution(gen);
201 const auto b = distribution(gen);
202 numLowerBitsInput.emplace_back(std::max(a, b), std::min(a, b));
212 BENCHMARK(Next, iters) {
213 bmNext<bm::Reader>(bm::list, bm::data, iters);
216 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
217 bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
221 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
222 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
223 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
224 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
225 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
226 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
227 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
229 BENCHMARK(Jump_ForwardQ128, iters) {
230 bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
233 BENCHMARK_DRAW_LINE();
235 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
236 bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
240 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
241 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
242 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
243 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
244 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
245 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
246 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
248 BENCHMARK(JumpTo_SkipQ128, iters) {
249 bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
252 BENCHMARK_DRAW_LINE();
254 BENCHMARK(Encode_10) {
255 auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
256 bm::encodeSmallData.end());
261 auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
262 bm::encodeLargeData.end());
266 BENCHMARK_DRAW_LINE();
268 BENCHMARK(defaultNumLowerBits, iters) {
269 using Encoder = EliasFanoEncoderV2<size_t>;
273 const auto& p = bm::numLowerBitsInput[i];
274 folly::doNotOptimizeAway(Encoder::defaultNumLowerBits(p.first, p.second));
275 if (++i == bm::numLowerBitsInput.size()) {
281 BENCHMARK(slowDefaultNumLowerBits, iters) {
284 const auto& p = bm::numLowerBitsInput[i];
285 folly::doNotOptimizeAway(slowDefaultNumLowerBits(p.first, p.second));
286 if (++i == bm::numLowerBitsInput.size()) {
293 Intel(R) Xeon(R) CPU E5-2678 v3 @ 2.50GHz (turbo on),
294 using -DEF_TEST_ARCH Haswell and GCC 4.9 with --bm_min_usec 100000.
295 ============================================================================
296 folly/experimental/test/EliasFanoCodingTest.cpp relative time/iter iters/s
297 ============================================================================
299 Skip_ForwardQ128(1) 3.73ns 267.93M
300 Skip_ForwardQ128(2) 4.89ns 204.34M
301 Skip_ForwardQ128(4_pm_1) 6.86ns 145.79M
302 Skip_ForwardQ128(16_pm_4) 18.92ns 52.85M
303 Skip_ForwardQ128(64_pm_16) 26.56ns 37.66M
304 Skip_ForwardQ128(256_pm_64) 30.12ns 33.20M
305 Skip_ForwardQ128(1024_pm_256) 30.74ns 32.53M
306 Jump_ForwardQ128 30.49ns 32.80M
307 ----------------------------------------------------------------------------
308 SkipTo_SkipQ128(1) 3.86ns 258.96M
309 SkipTo_SkipQ128(2) 7.73ns 129.36M
310 SkipTo_SkipQ128(4_pm_1) 10.29ns 97.18M
311 SkipTo_SkipQ128(16_pm_4) 28.69ns 34.86M
312 SkipTo_SkipQ128(64_pm_16) 39.73ns 25.17M
313 SkipTo_SkipQ128(256_pm_64) 43.45ns 23.01M
314 SkipTo_SkipQ128(1024_pm_256) 44.66ns 22.39M
315 JumpTo_SkipQ128 47.98ns 20.84M
316 ----------------------------------------------------------------------------
317 Encode_10 77.92ns 12.83M
319 ----------------------------------------------------------------------------
320 defaultNumLowerBits 2.20ns 455.01M
321 slowDefaultNumLowerBits 7.90ns 126.59M
322 ============================================================================
325 int main(int argc, char** argv) {
326 testing::InitGoogleTest(&argc, argv);
327 gflags::ParseCommandLineFlags(&argc, &argv, true);
329 auto ret = RUN_ALL_TESTS();
330 if (ret == 0 && FLAGS_benchmark) {
332 folly::runBenchmarks();