folly/experimental/test/BitVectorCodingTest.cpp

   1 /*
   2  * Copyright 2015-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 <numeric>
  19 #include <random>
  20 #include <vector>
  21
  22 #include <folly/Benchmark.h>
  23 #include <folly/experimental/BitVectorCoding.h>
  24 #include <folly/experimental/Select64.h>
  25 #include <folly/experimental/test/CodingTestUtils.h>
  26
  27 using namespace folly::compression;
  28
  29 #ifndef BV_TEST_ARCH
  30 #define BV_TEST_ARCH Default
  31 #endif // BV_TEST_ARCH
  32
  33 class BitVectorCodingTest : public ::testing::Test {
  34  public:
  35   void doTestEmpty() {
  36     typedef BitVectorEncoder<uint32_t, size_t> Encoder;
  37     typedef BitVectorReader<Encoder, instructions::BV_TEST_ARCH> Reader;
  38     testEmpty<Reader, Encoder>();
  39   }
  40
  41   template <size_t kSkipQuantum, size_t kForwardQuantum>
  42   void doTestAll() {
  43     typedef BitVectorEncoder<uint32_t, uint32_t, kSkipQuantum, kForwardQuantum>
  44         Encoder;
  45     typedef BitVectorReader<Encoder> Reader;
  46     testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
  47     testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
  48   }
  49 };
  50
  51 TEST_F(BitVectorCodingTest, Empty) {
  52   doTestEmpty();
  53 }
  54
  55 TEST_F(BitVectorCodingTest, Simple) {
  56   doTestAll<0, 0>();
  57 }
  58
  59 TEST_F(BitVectorCodingTest, SkipPointers) {
  60   doTestAll<128, 0>();
  61 }
  62
  63 TEST_F(BitVectorCodingTest, ForwardPointers) {
  64   doTestAll<0, 128>();
  65 }
  66
  67 TEST_F(BitVectorCodingTest, SkipForwardPointers) {
  68   doTestAll<128, 128>();
  69 }
  70
  71 namespace bm {
  72
  73 typedef BitVectorEncoder<uint32_t, uint32_t, 128, 128> Encoder;
  74 typedef BitVectorReader<Encoder> Reader;
  75
  76 std::vector<uint32_t> data;
  77 std::vector<size_t> order;
  78
  79 std::vector<uint32_t> encodeSmallData;
  80 std::vector<uint32_t> encodeLargeData;
  81
  82 typename Encoder::MutableCompressedList list;
  83
  84 void init() {
  85   std::mt19937 gen;
  86
  87   data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
  88   list = Encoder::encode(data.begin(), data.end());
  89
  90   order.resize(data.size());
  91   std::iota(order.begin(), order.end(), size_t());
  92   std::shuffle(order.begin(), order.end(), gen);
  93
  94   encodeSmallData = generateRandomList(10, 100 * 1000, gen);
  95   encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
  96 }
  97
  98 void free() { list.free(); }
  99
 100 } // namespace bm
 101
 102 BENCHMARK(Next, iters) { bmNext<bm::Reader>(bm::list, bm::data, iters); }
 103
 104 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
 105   bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 106   return iters;
 107 }
 108
 109 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
 110 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
 111 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
 112 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
 113 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
 114 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
 115 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
 116
 117 BENCHMARK(Jump_ForwardQ128, iters) {
 118   bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
 119 }
 120
 121 BENCHMARK_DRAW_LINE();
 122
 123 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
 124   bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
 125   return iters;
 126 }
 127
 128 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
 129 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
 130 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
 131 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
 132 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
 133 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
 134 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
 135
 136 BENCHMARK(JumpTo_SkipQ128, iters) {
 137   bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
 138 }
 139
 140 BENCHMARK_DRAW_LINE();
 141
 142 BENCHMARK(Encode_10) {
 143   auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
 144                                   bm::encodeSmallData.end());
 145   list.free();
 146 }
 147
 148 BENCHMARK(Encode) {
 149   auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
 150                                   bm::encodeLargeData.end());
 151   list.free();
 152 }
 153
 154 #if 0
 155 Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz (turbo off),
 156 using instructions::Default and GCC 4.8 with --bm_min_usec 100000.
 157 ============================================================================
 158 folly/experimental/test/BitVectorCodingTest.cpp relative  time/iter  iters/s
 159 ============================================================================
 160 Next                                                         9.59ns  104.25M
 161 Skip_ForwardQ128(1)                                         11.56ns   86.53M
 162 Skip_ForwardQ128(2)                                         23.30ns   42.93M
 163 Skip_ForwardQ128(4_pm_1)                                    52.99ns   18.87M
 164 Skip_ForwardQ128(16_pm_4)                                  200.85ns    4.98M
 165 Skip_ForwardQ128(64_pm_16)                                 733.20ns    1.36M
 166 Skip_ForwardQ128(256_pm_64)                                748.35ns    1.34M
 167 Skip_ForwardQ128(1024_pm_256)                              742.77ns    1.35M
 168 Jump_ForwardQ128                                           752.98ns    1.33M
 169 ----------------------------------------------------------------------------
 170 SkipTo_SkipQ128(1)                                          23.47ns   42.62M
 171 SkipTo_SkipQ128(2)                                          24.48ns   40.85M
 172 SkipTo_SkipQ128(4_pm_1)                                     22.16ns   45.13M
 173 SkipTo_SkipQ128(16_pm_4)                                    28.43ns   35.17M
 174 SkipTo_SkipQ128(64_pm_16)                                   45.51ns   21.97M
 175 SkipTo_SkipQ128(256_pm_64)                                  44.03ns   22.71M
 176 SkipTo_SkipQ128(1024_pm_256)                                45.84ns   21.81M
 177 JumpTo_SkipQ128                                             15.33ns   65.25M
 178 ----------------------------------------------------------------------------
 179 Encode_10                                                    1.60us  624.33K
 180 Encode                                                      16.98ms    58.89
 181 ============================================================================
 182 #endif
 183
 184 int main(int argc, char** argv) {
 185   testing::InitGoogleTest(&argc, argv);
 186   gflags::ParseCommandLineFlags(&argc, &argv, true);
 187
 188   auto ret = RUN_ALL_TESTS();
 189   if (ret == 0 && FLAGS_benchmark) {
 190     bm::init();
 191     folly::runBenchmarks();
 192     bm::free();
 193   }
 194
 195   return ret;
 196 }