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(GoTo_ForwardQ128_1M) {
 135   bmGoTo<bm::Reader>(bm::list, bm::data, bm::order, bm::k1M);
 136 }
 137
 138 BENCHMARK(SkipTo1_SkipQ128_1M) {
 139   bmSkipTo<bm::Reader>(bm::list, bm::data, 1, bm::k1M);
 140 }
 141
 142 BENCHMARK_DRAW_LINE();
 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_DRAW_LINE();
 157
 158 BENCHMARK(Encode_10) {
 159   auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
 160                                   bm::encodeSmallData.end());
 161   list.free();
 162 }
 163
 164 BENCHMARK(Encode_1M) {
 165   auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
 166                                   bm::encodeLargeData.end());
 167   list.free();
 168 }
 169
 170 #if 0
 171 Intel(R) Xeon(R) CPU E5-2660 @ 2.7GHz (turbo on), using instructions::Fast.
 172
 173 ============================================================================
 174 folly/experimental/test/EliasFanoCodingTest.cpp relative  time/iter  iters/s
 175 ============================================================================
 176 Next_1M                                                      4.86ms   205.97
 177 Skip1_ForwarQ128_1M                                          5.17ms   193.36
 178 Skip10_ForwarQ128_1M                                        13.69ms    73.03
 179 Skip100_ForwardQ128_1M                                      26.76ms    37.37
 180 Skip1000_ForwardQ128_1M                                     20.66ms    48.40
 181 GoTo_ForwardQ128_1M                                         43.75ms    22.86
 182 ----------------------------------------------------------------------------
 183 SkipTo1_SkipQ128_1M                                          9.74ms   102.70
 184 SkipTo10_SkipQ128_1M                                        30.62ms    32.66
 185 SkipTo100_SkipQ128_1M                                       37.70ms    26.53
 186 SkipTo1000_SkipQ128_1M                                      31.14ms    32.11
 187 ----------------------------------------------------------------------------
 188 Encode_10                                                  208.16ns    4.80M
 189 Encode_1M                                                    8.90ms   112.37
 190 ============================================================================
 191 #endif
 192
 193 int main(int argc, char** argv) {
 194   testing::InitGoogleTest(&argc, argv);
 195   gflags::ParseCommandLineFlags(&argc, &argv, true);
 196
 197   auto ret = RUN_ALL_TESTS();
 198   if (ret == 0 && FLAGS_benchmark) {
 199     bm::init();
 200     folly::runBenchmarks();
 201     bm::free();
 202   }
 203
 204   return ret;
 205 }