folly/experimental/test/EliasFanoCodingTest.cpp

   1 /*
   2  * Copyright 2017 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 <numeric>
  19 #include <random>
  20 #include <vector>
  21
  22 #include <folly/Benchmark.h>
  23 #include <folly/experimental/EliasFanoCoding.h>
  24 #include <folly/experimental/Select64.h>
  25 #include <folly/experimental/test/CodingTestUtils.h>
  26
  27 using namespace folly::compression;
  28
  29 #ifndef EF_TEST_ARCH
  30 #define EF_TEST_ARCH Default
  31 #endif  // EF_TEST_ARCH
  32
  33 class EliasFanoCodingTest : public ::testing::Test {
  34  public:
  35   void doTestEmpty() {
  36     typedef EliasFanoEncoderV2<uint32_t, size_t> Encoder;
  37     typedef EliasFanoReader<Encoder> Reader;
  38     testEmpty<Reader, Encoder>();
  39   }
  40
  41   template <size_t kSkipQuantum, size_t kForwardQuantum>
  42   void doTestAll() {
  43     typedef EliasFanoEncoderV2<
  44       uint32_t, uint32_t, kSkipQuantum, kForwardQuantum> Encoder;
  45     typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
  46     testAll<Reader, Encoder>({0});
  47     testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
  48     testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
  49   }
  50 };
  51
  52 TEST_F(EliasFanoCodingTest, Empty) {
  53   doTestEmpty();
  54 }
  55
  56 TEST_F(EliasFanoCodingTest, Simple) {
  57   doTestAll<0, 0>();
  58 }
  59
  60 TEST_F(EliasFanoCodingTest, SkipPointers) {
  61   doTestAll<128, 0>();
  62 }
  63
  64 TEST_F(EliasFanoCodingTest, ForwardPointers) {
  65   doTestAll<0, 128>();
  66 }
  67
  68 TEST_F(EliasFanoCodingTest, SkipForwardPointers) {
  69   doTestAll<128, 128>();
  70 }
  71
  72 TEST_F(EliasFanoCodingTest, Select64) {
  73   typedef instructions::EF_TEST_ARCH instr;
  74   constexpr uint64_t kPrime = uint64_t(-59);
  75   for (uint64_t x = kPrime, i = 0; i < (1 << 20); x *= kPrime, i += 1) {
  76     size_t w = instr::popcount(x);
  77     for (size_t k = 0; k < w; ++k) {
  78       auto pos = folly::select64<instr>(x, k);
  79       CHECK_EQ((x >> pos) & 1, 1);
  80       CHECK_EQ(instr::popcount(x & ((uint64_t(1) << pos) - 1)), k);
  81     }
  82   }
  83 }
  84
  85 namespace bm {
  86
  87 typedef EliasFanoEncoderV2<uint32_t, uint32_t, 128, 128> Encoder;
  88 typedef EliasFanoReader<Encoder> Reader;
  89
  90 std::vector<uint32_t> data;
  91 std::vector<size_t> order;
  92
  93 std::vector<uint32_t> encodeSmallData;
  94 std::vector<uint32_t> encodeLargeData;
  95
  96 typename Encoder::MutableCompressedList list;
  97
  98 void init() {
  99   std::mt19937 gen;
 100
 101   data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
 102   list = Encoder::encode(data.begin(), data.end());
 103
 104   order.resize(data.size());
 105   std::iota(order.begin(), order.end(), size_t());
 106   std::shuffle(order.begin(), order.end(), gen);
 107
 108   encodeSmallData = generateRandomList(10, 100 * 1000, gen);
 109   encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
 110 }
 111
 112 void free() {
 113   list.free();
 114 }
 115
 116 }  // namespace bm
 117
 118 BENCHMARK(Next, iters) {
 119   bmNext<bm::Reader>(bm::list, bm::data, iters);
 120 }
 121
 122 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
 123   bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 124   return iters;
 125 }
 126
 127 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
 128 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
 129 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
 130 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
 131 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
 132 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
 133 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
 134
 135 BENCHMARK(Jump_ForwardQ128, iters) {
 136   bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
 137 }
 138
 139 BENCHMARK_DRAW_LINE();
 140
 141 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
 142   bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 143   return iters;
 144 }
 145
 146 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
 147 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
 148 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
 149 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
 150 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
 151 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
 152 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
 153
 154 BENCHMARK(JumpTo_SkipQ128, iters) {
 155   bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
 156 }
 157
 158 BENCHMARK_DRAW_LINE();
 159
 160 BENCHMARK(Encode_10) {
 161   auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
 162                                   bm::encodeSmallData.end());
 163   list.free();
 164 }
 165
 166 BENCHMARK(Encode) {
 167   auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
 168                                   bm::encodeLargeData.end());
 169   list.free();
 170 }
 171
 172 #if 0
 173 Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz (turbo off),
 174 using instructions::Haswell and GCC 4.9 with --bm_min_usec 100000.
 175 ============================================================================
 176 folly/experimental/test/EliasFanoCodingTest.cpp relative  time/iter  iters/s
 177 ============================================================================
 178 Next                                                         2.59ns  386.60M
 179 Skip_ForwardQ128(1)                                          4.03ns  248.16M
 180 Skip_ForwardQ128(2)                                          5.28ns  189.39M
 181 Skip_ForwardQ128(4_pm_1)                                     7.48ns  133.75M
 182 Skip_ForwardQ128(16_pm_4)                                   20.28ns   49.32M
 183 Skip_ForwardQ128(64_pm_16)                                  28.19ns   35.47M
 184 Skip_ForwardQ128(256_pm_64)                                 31.99ns   31.26M
 185 Skip_ForwardQ128(1024_pm_256)                               32.51ns   30.76M
 186 Jump_ForwardQ128                                            33.77ns   29.61M
 187 ----------------------------------------------------------------------------
 188 SkipTo_SkipQ128(1)                                           4.34ns  230.66M
 189 SkipTo_SkipQ128(2)                                           8.90ns  112.38M
 190 SkipTo_SkipQ128(4_pm_1)                                     12.12ns   82.49M
 191 SkipTo_SkipQ128(16_pm_4)                                    32.52ns   30.75M
 192 SkipTo_SkipQ128(64_pm_16)                                   44.82ns   22.31M
 193 SkipTo_SkipQ128(256_pm_64)                                  49.52ns   20.19M
 194 SkipTo_SkipQ128(1024_pm_256)                                52.88ns   18.91M
 195 JumpTo_SkipQ128                                             54.65ns   18.30M
 196 ----------------------------------------------------------------------------
 197 Encode_10                                                   98.70ns   10.13M
 198 Encode                                                       5.48ms   182.33
 199 ============================================================================
 200 #endif
 201
 202 int main(int argc, char** argv) {
 203   testing::InitGoogleTest(&argc, argv);
 204   gflags::ParseCommandLineFlags(&argc, &argv, true);
 205
 206   auto ret = RUN_ALL_TESTS();
 207   if (ret == 0 && FLAGS_benchmark) {
 208     bm::init();
 209     folly::runBenchmarks();
 210     bm::free();
 211   }
 212
 213   return ret;
 214 }