folly/experimental/test/EliasFanoCodingTest.cpp

   1 /*
   2  * Copyright 2013 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 "folly/experimental/test/CodingTestUtils.h"
  18 #include "folly/experimental/EliasFanoCoding.h"
  19 #include "folly/Benchmark.h"
  20
  21 using namespace folly::compression;
  22
  23 template <class List>
  24 void testAll() {
  25   typedef EliasFanoReader<List> Reader;
  26   testAll<Reader, List>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
  27   testAll<Reader, List>(generateSeqList(1, 100000, 100));
  28 }
  29
  30 TEST(EliasFanoCompressedList, Empty) {
  31   typedef EliasFanoCompressedList<uint32_t> List;
  32   typedef EliasFanoReader<List> Reader;
  33   testEmpty<Reader, List>();
  34 }
  35
  36 TEST(EliasFanoCompressedList, Simple) {
  37   testAll<EliasFanoCompressedList<uint32_t> >();
  38 }
  39
  40 TEST(EliasFanoCompressedList, SkipPointers) {
  41   testAll<EliasFanoCompressedList<uint32_t, uint32_t, 128, 0> >();
  42 }
  43
  44 TEST(EliasFanoCompressedList, ForwardPointers) {
  45   testAll<EliasFanoCompressedList<uint32_t, uint32_t, 0, 128> >();
  46 }
  47
  48 TEST(EliasFanoCompressedList, SkipForwardPointers) {
  49   testAll<EliasFanoCompressedList<uint32_t, uint32_t, 128, 128> >();
  50 }
  51
  52 namespace bm {
  53
  54 constexpr size_t k1M = 1000000;
  55 typedef EliasFanoCompressedList<uint32_t, uint32_t, 128, 128> List;
  56 typedef EliasFanoReader<List> Reader;
  57
  58 std::vector<uint32_t> data;
  59 List list;
  60
  61 void init() {
  62   data = generateRandomList(100 * 1000, 10 * 1000 * 1000);
  63   //data = loadList("/home/philipp/pl_test_dump.txt");
  64   List::encode(data.data(), data.size(), bm::list);
  65 }
  66
  67 void free() {
  68   list.free();
  69 }
  70
  71 }  // namespace bm
  72
  73 BENCHMARK(Next_1M) {
  74   bmNext<bm::Reader>(bm::list, bm::data, bm::k1M);
  75 }
  76
  77 BENCHMARK(Skip1_ForwarQ128_1M) {
  78   bmSkip<bm::Reader>(bm::list, bm::data, 1, bm::k1M);
  79 }
  80
  81 BENCHMARK(Skip10_ForwarQ128_1M) {
  82   bmSkip<bm::Reader>(bm::list, bm::data, 10, bm::k1M);
  83 }
  84
  85 BENCHMARK(Skip100_ForwardQ128_1M) {
  86   bmSkip<bm::Reader>(bm::list, bm::data, 100, bm::k1M);
  87 }
  88
  89 BENCHMARK(Skip1000_ForwardQ128_1M) {
  90   bmSkip<bm::Reader>(bm::list, bm::data, 1000, bm::k1M);
  91 }
  92
  93 BENCHMARK(SkipTo1_SkipQ128_1M) {
  94   bmSkipTo<bm::Reader>(bm::list, bm::data, 1, bm::k1M);
  95 }
  96
  97 BENCHMARK(SkipTo10_SkipQ128_1M) {
  98   bmSkipTo<bm::Reader>(bm::list, bm::data, 10, bm::k1M);
  99 }
 100
 101 BENCHMARK(SkipTo100_SkipQ128_1M) {
 102   bmSkipTo<bm::Reader>(bm::list, bm::data, 100, bm::k1M);
 103 }
 104
 105 BENCHMARK(SkipTo1000_SkipQ128_1M) {
 106   bmSkipTo<bm::Reader>(bm::list, bm::data, 1000, bm::k1M);
 107 }
 108
 109 int main(int argc, char** argv) {
 110   testing::InitGoogleTest(&argc, argv);
 111   google::ParseCommandLineFlags(&argc, &argv, true);
 112
 113   auto ret = RUN_ALL_TESTS();
 114   if (ret == 0 && FLAGS_benchmark) {
 115     bm::init();
 116     folly::runBenchmarks();
 117     bm::free();
 118   }
 119
 120   return ret;
 121 }