folly/experimental/test/EliasFanoCodingTest.cpp

   1 /*
   2  * Copyright 2014 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 <random>
  19 #include <vector>
  20
  21 #include <folly/Benchmark.h>
  22 #include <folly/experimental/EliasFanoCoding.h>
  23 #include <folly/experimental/test/CodingTestUtils.h>
  24
  25 using namespace folly::compression;
  26
  27 template <size_t kVersion>
  28 struct TestType {
  29   static constexpr size_t Version = kVersion;
  30 };
  31
  32 template <class T>
  33 class EliasFanoCodingTest : public ::testing::Test {
  34  public:
  35   void doTestEmpty() {
  36     typedef EliasFanoEncoder<uint32_t, size_t, 0, 0, T::Version> 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 EliasFanoEncoder<
  44       uint32_t, uint32_t, kSkipQuantum, kForwardQuantum, T::Version> Encoder;
  45     typedef EliasFanoReader<Encoder> Reader;
  46     testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
  47     testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
  48   }
  49 };
  50
  51 typedef ::testing::Types<TestType<0>, TestType<1>> TestTypes;
  52 TYPED_TEST_CASE(EliasFanoCodingTest, TestTypes);
  53
  54 TYPED_TEST(EliasFanoCodingTest, Empty) {
  55   TestFixture::doTestEmpty();
  56 }
  57
  58 TYPED_TEST(EliasFanoCodingTest, Simple) {
  59   TestFixture::template doTestAll<0, 0>();
  60 }
  61
  62 TYPED_TEST(EliasFanoCodingTest, SkipPointers) {
  63   TestFixture::template doTestAll<128, 0>();
  64 }
  65
  66 TYPED_TEST(EliasFanoCodingTest, ForwardPointers) {
  67   TestFixture::template doTestAll<0, 128>();
  68 }
  69
  70 TYPED_TEST(EliasFanoCodingTest, SkipForwardPointers) {
  71   TestFixture::template doTestAll<128, 128>();
  72 }
  73
  74 namespace bm {
  75
  76 constexpr size_t k1M = 1000000;
  77 constexpr size_t kVersion = 1;
  78
  79 typedef EliasFanoEncoder<uint32_t, uint32_t, 128, 128, kVersion> Encoder;
  80 typedef EliasFanoReader<Encoder> Reader;
  81
  82 std::vector<uint32_t> data;
  83 std::vector<size_t> order;
  84
  85 std::vector<uint32_t> encodeSmallData;
  86 std::vector<uint32_t> encodeLargeData;
  87
  88 typename Encoder::CompressedList list;
  89
  90 void init() {
  91   std::mt19937 gen;
  92
  93   data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
  94   //data = loadList("/home/philipp/pl_test_dump.txt");
  95   list = Encoder::encode(data.begin(), data.end());
  96
  97   order.clear();
  98   order.reserve(data.size());
  99   for (size_t i = 0; i < data.size(); ++i) {
 100     order.push_back(i);
 101   }
 102   std::shuffle(order.begin(), order.end(), gen);
 103
 104   encodeSmallData = generateRandomList(10, 100 * 1000, gen);
 105   encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
 106 }
 107
 108 void free() {
 109   list.free();
 110 }
 111
 112 }  // namespace bm
 113
 114 BENCHMARK(Next_1M) {
 115   bmNext<bm::Reader>(bm::list, bm::data, bm::k1M);
 116 }
 117
 118 BENCHMARK(Skip1_ForwarQ128_1M) {
 119   bmSkip<bm::Reader>(bm::list, bm::data, 1, bm::k1M);
 120 }
 121
 122 BENCHMARK(Skip10_ForwarQ128_1M) {
 123   bmSkip<bm::Reader>(bm::list, bm::data, 10, bm::k1M);
 124 }
 125
 126 BENCHMARK(Skip100_ForwardQ128_1M) {
 127   bmSkip<bm::Reader>(bm::list, bm::data, 100, bm::k1M);
 128 }
 129
 130 BENCHMARK(Skip1000_ForwardQ128_1M) {
 131   bmSkip<bm::Reader>(bm::list, bm::data, 1000, bm::k1M);
 132 }
 133
 134 BENCHMARK(Jump_ForwardQ128_1M) {
 135   bmJump<bm::Reader>(bm::list, bm::data, bm::order, bm::k1M);
 136 }
 137
 138 BENCHMARK_DRAW_LINE();
 139
 140 BENCHMARK(SkipTo1_SkipQ128_1M) {
 141   bmSkipTo<bm::Reader>(bm::list, bm::data, 1, bm::k1M);
 142 }
 143
 144 BENCHMARK(SkipTo10_SkipQ128_1M) {
 145   bmSkipTo<bm::Reader>(bm::list, bm::data, 10, bm::k1M);
 146 }
 147
 148 BENCHMARK(SkipTo100_SkipQ128_1M) {
 149   bmSkipTo<bm::Reader>(bm::list, bm::data, 100, bm::k1M);
 150 }
 151
 152 BENCHMARK(SkipTo1000_SkipQ128_1M) {
 153   bmSkipTo<bm::Reader>(bm::list, bm::data, 1000, bm::k1M);
 154 }
 155
 156 BENCHMARK(JumpTo_SkipQ128_1M) {
 157   bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, bm::k1M);
 158 }
 159
 160 BENCHMARK_DRAW_LINE();
 161
 162 BENCHMARK(Encode_10) {
 163   auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
 164                                   bm::encodeSmallData.end());
 165   list.free();
 166 }
 167
 168 BENCHMARK(Encode_1M) {
 169   auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
 170                                   bm::encodeLargeData.end());
 171   list.free();
 172 }
 173
 174 #if 0
 175 Intel(R) Xeon(R) CPU E5-2660 @ 2.7GHz (turbo on), using instructions::Fast.
 176
 177 ============================================================================
 178 folly/experimental/test/EliasFanoCodingTest.cpp relative  time/iter  iters/s
 179 ============================================================================
 180 Next_1M                                                      4.61ms   216.70
 181 Skip1_ForwarQ128_1M                                          5.33ms   187.71
 182 Skip10_ForwarQ128_1M                                        14.23ms    70.26
 183 Skip100_ForwardQ128_1M                                      29.10ms    34.37
 184 Skip1000_ForwardQ128_1M                                     21.15ms    47.28
 185 Jump_ForwardQ128_1M                                         46.30ms    21.60
 186 ----------------------------------------------------------------------------
 187 SkipTo1_SkipQ128_1M                                         12.03ms    83.15
 188 SkipTo10_SkipQ128_1M                                        36.11ms    27.69
 189 SkipTo100_SkipQ128_1M                                       42.91ms    23.30
 190 SkipTo1000_SkipQ128_1M                                      36.92ms    27.08
 191 JumpTo_SkipQ128_1M                                          78.51ms    12.74
 192 ----------------------------------------------------------------------------
 193 Encode_10                                                  199.19ns    5.02M
 194 Encode_1M                                                    8.82ms   113.37
 195 ============================================================================
 196 #endif
 197
 198 int main(int argc, char** argv) {
 199   testing::InitGoogleTest(&argc, argv);
 200   gflags::ParseCommandLineFlags(&argc, &argv, true);
 201
 202   auto ret = RUN_ALL_TESTS();
 203   if (ret == 0 && FLAGS_benchmark) {
 204     bm::init();
 205     folly::runBenchmarks();
 206     bm::free();
 207   }
 208
 209   return ret;
 210 }