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