folly/experimental/test/EliasFanoCodingTest.cpp

   1 /*
   2  * Copyright 2013-present Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #include <algorithm>
  18 #include <limits>
  19 #include <numeric>
  20 #include <random>
  21 #include <vector>
  22
  23 #include <folly/Benchmark.h>
  24 #include <folly/experimental/EliasFanoCoding.h>
  25 #include <folly/experimental/Select64.h>
  26 #include <folly/experimental/test/CodingTestUtils.h>
  27
  28 using namespace folly::compression;
  29
  30 #ifndef EF_TEST_ARCH
  31 #define EF_TEST_ARCH Default
  32 #endif  // EF_TEST_ARCH
  33
  34 namespace {
  35
  36 uint8_t slowDefaultNumLowerBits(size_t upperBound, size_t size) {
  37   if (size == 0 || upperBound < size) {
  38     return 0;
  39   }
  40   // floor(log(upperBound / size));
  41   return uint8_t(folly::findLastSet(upperBound / size) - 1);
  42 }
  43
  44 } // namespace
  45
  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;
  55   };
  56   auto batch = [&compare](size_t initialUpperBound) {
  57     for (size_t upperBound = initialUpperBound, i = 0;
  58          i < kNumIterations;
  59          ++i, --upperBound) {
  60       // Test "size" values close to "upperBound".
  61       for (size_t size = upperBound, j = 0; j < kNumIterations; ++j, --size) {
  62         compare(upperBound, size);
  63       }
  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);
  69       }
  70       // Test "size" values close to 0.
  71       for (size_t size = 0; size < kNumIterations; ++size) {
  72         compare(upperBound, size);
  73       }
  74     }
  75   };
  76   batch(std::numeric_limits<size_t>::max());
  77   batch(kNumIterations + 1312213123);
  78   batch(kNumIterations);
  79
  80   std::mt19937 gen;
  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));
  86   }
  87 }
  88
  89 class EliasFanoCodingTest : public ::testing::Test {
  90  public:
  91   void doTestEmpty() {
  92     typedef EliasFanoEncoderV2<uint32_t, size_t> Encoder;
  93     typedef EliasFanoReader<Encoder> Reader;
  94     testEmpty<Reader, Encoder>();
  95   }
  96
  97   template <size_t kSkipQuantum, size_t kForwardQuantum, class SizeType>
  98   void doTestAll() {
  99     typedef EliasFanoEncoderV2<
 100       uint32_t, uint32_t, kSkipQuantum, kForwardQuantum> Encoder;
 101     using Reader =
 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));
 106   }
 107 };
 108
 109 TEST_F(EliasFanoCodingTest, Empty) {
 110   doTestEmpty();
 111 }
 112
 113 TEST_F(EliasFanoCodingTest, Simple) {
 114   doTestAll<0, 0, uint32_t>();
 115   doTestAll<0, 0, size_t>();
 116 }
 117
 118 TEST_F(EliasFanoCodingTest, SkipPointers) {
 119   doTestAll<128, 0, uint32_t>();
 120   doTestAll<128, 0, size_t>();
 121 }
 122
 123 TEST_F(EliasFanoCodingTest, ForwardPointers) {
 124   doTestAll<0, 128, uint32_t>();
 125   doTestAll<0, 128, size_t>();
 126 }
 127
 128 TEST_F(EliasFanoCodingTest, SkipForwardPointers) {
 129   doTestAll<128, 128, uint32_t>();
 130   doTestAll<128, 128, size_t>();
 131 }
 132
 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);
 142     }
 143   }
 144 }
 145
 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;
 150
 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);
 157   }
 158   auto list = Encoder::encode(data.begin(), data.end());
 159
 160   {
 161     Reader reader(list);
 162     ASSERT_TRUE(reader.skipTo(kLargeValue - 1));
 163     ASSERT_EQ(kLargeValue, reader.value());
 164     ASSERT_EQ(0, reader.previousValue());
 165   }
 166
 167   list.free();
 168 }
 169
 170 namespace bm {
 171
 172 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 128, 128> Encoder;
 173 typedef EliasFanoReader<Encoder> Reader;
 174
 175 std::vector<uint32_t> data;
 176 std::vector<size_t> order;
 177
 178 std::vector<uint32_t> encodeSmallData;
 179 std::vector<uint32_t> encodeLargeData;
 180
 181 std::vector<std::pair<size_t, size_t>> numLowerBitsInput;
 182
 183 typename Encoder::MutableCompressedList list;
 184
 185 void init() {
 186   std::mt19937 gen;
 187
 188   data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
 189   list = Encoder::encode(data.begin(), data.end());
 190
 191   order.resize(data.size());
 192   std::iota(order.begin(), order.end(), size_t());
 193   std::shuffle(order.begin(), order.end(), gen);
 194
 195   encodeSmallData = generateRandomList(10, 100 * 1000, gen);
 196   encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
 197
 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));
 203   }
 204 }
 205
 206 void free() {
 207   list.free();
 208 }
 209
 210 } // namespace bm
 211
 212 BENCHMARK(Next, iters) {
 213   bmNext<bm::Reader>(bm::list, bm::data, iters);
 214 }
 215
 216 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
 217   bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 218   return iters;
 219 }
 220
 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)
 228
 229 BENCHMARK(Jump_ForwardQ128, iters) {
 230   bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
 231 }
 232
 233 BENCHMARK_DRAW_LINE();
 234
 235 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
 236   bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 237   return iters;
 238 }
 239
 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)
 247
 248 BENCHMARK(JumpTo_SkipQ128, iters) {
 249   bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
 250 }
 251
 252 BENCHMARK_DRAW_LINE();
 253
 254 BENCHMARK(Encode_10) {
 255   auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
 256                                   bm::encodeSmallData.end());
 257   list.free();
 258 }
 259
 260 BENCHMARK(Encode) {
 261   auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
 262                                   bm::encodeLargeData.end());
 263   list.free();
 264 }
 265
 266 BENCHMARK_DRAW_LINE();
 267
 268 BENCHMARK(defaultNumLowerBits, iters) {
 269   using Encoder = EliasFanoEncoderV2<size_t>;
 270
 271   size_t i = 0;
 272   while (iters--) {
 273     const auto& p = bm::numLowerBitsInput[i];
 274     folly::doNotOptimizeAway(Encoder::defaultNumLowerBits(p.first, p.second));
 275     if (++i == bm::numLowerBitsInput.size()) {
 276       i = 0;
 277     }
 278   }
 279 }
 280
 281 BENCHMARK(slowDefaultNumLowerBits, iters) {
 282   size_t i = 0;
 283   while (iters--) {
 284     const auto& p = bm::numLowerBitsInput[i];
 285     folly::doNotOptimizeAway(slowDefaultNumLowerBits(p.first, p.second));
 286     if (++i == bm::numLowerBitsInput.size()) {
 287       i = 0;
 288     }
 289   }
 290 }
 291
 292 #if 0
 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 ============================================================================
 298 Next                                                         2.31ns  433.77M
 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
 318 Encode                                                       4.73ms   211.41
 319 ----------------------------------------------------------------------------
 320 defaultNumLowerBits                                          2.20ns  455.01M
 321 slowDefaultNumLowerBits                                      7.90ns  126.59M
 322 ============================================================================
 323 #endif
 324
 325 int main(int argc, char** argv) {
 326   testing::InitGoogleTest(&argc, argv);
 327   gflags::ParseCommandLineFlags(&argc, &argv, true);
 328
 329   auto ret = RUN_ALL_TESTS();
 330   if (ret == 0 && FLAGS_benchmark) {
 331     bm::init();
 332     folly::runBenchmarks();
 333     bm::free();
 334   }
 335
 336   return ret;
 337 }