2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
22 #include <folly/Benchmark.h>
23 #include <folly/experimental/EliasFanoCoding.h>
24 #include <folly/experimental/Select64.h>
25 #include <folly/experimental/test/CodingTestUtils.h>
27 using namespace folly::compression;
29 #if defined(EF_TEST_NEHALEM)
30 #define EF_TEST_ARCH Nehalem
31 #elif defined(EF_TEST_HASWELL)
32 #define EF_TEST_ARCH Haswell
34 #define EF_TEST_ARCH Default
37 template <size_t kVersion>
39 static constexpr size_t Version = kVersion;
43 class EliasFanoCodingTest : public ::testing::Test {
46 typedef EliasFanoEncoder<uint32_t, size_t, 0, 0, T::Version> Encoder;
47 typedef EliasFanoReader<Encoder> Reader;
48 testEmpty<Reader, Encoder>();
51 template <size_t kSkipQuantum, size_t kForwardQuantum>
53 typedef EliasFanoEncoder<
54 uint32_t, uint32_t, kSkipQuantum, kForwardQuantum, T::Version> Encoder;
55 typedef EliasFanoReader<Encoder, instructions::EF_TEST_ARCH> Reader;
56 testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
57 testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
61 typedef ::testing::Types<TestType<0>, TestType<1>> TestTypes;
62 TYPED_TEST_CASE(EliasFanoCodingTest, TestTypes);
64 TYPED_TEST(EliasFanoCodingTest, Empty) {
65 TestFixture::doTestEmpty();
68 TYPED_TEST(EliasFanoCodingTest, Simple) {
69 TestFixture::template doTestAll<0, 0>();
72 TYPED_TEST(EliasFanoCodingTest, SkipPointers) {
73 TestFixture::template doTestAll<128, 0>();
76 TYPED_TEST(EliasFanoCodingTest, ForwardPointers) {
77 TestFixture::template doTestAll<0, 128>();
80 TYPED_TEST(EliasFanoCodingTest, SkipForwardPointers) {
81 TestFixture::template doTestAll<128, 128>();
86 constexpr size_t k1M = 1000000;
87 constexpr size_t kVersion = 1;
89 typedef EliasFanoEncoder<uint32_t, uint32_t, 128, 128, kVersion> Encoder;
90 typedef EliasFanoReader<Encoder> Reader;
92 std::vector<uint32_t> data;
93 std::vector<size_t> order;
95 std::vector<uint32_t> encodeSmallData;
96 std::vector<uint32_t> encodeLargeData;
98 typename Encoder::CompressedList list;
103 data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
104 //data = loadList("/home/philipp/pl_test_dump.txt");
105 list = Encoder::encode(data.begin(), data.end());
107 order.resize(data.size());
108 std::iota(order.begin(), order.end(), size_t());
109 std::shuffle(order.begin(), order.end(), gen);
111 encodeSmallData = generateRandomList(10, 100 * 1000, gen);
112 encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
121 BENCHMARK(Next, iters) {
122 bmNext<bm::Reader>(bm::list, bm::data, iters);
125 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
126 bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
130 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
131 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
132 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
133 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
134 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
135 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
136 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
138 BENCHMARK(Jump_ForwardQ128, iters) {
139 bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
142 BENCHMARK_DRAW_LINE();
144 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
145 bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
149 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
150 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
151 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
152 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
153 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
154 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
155 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
157 BENCHMARK(JumpTo_SkipQ128, iters) {
158 bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
161 BENCHMARK_DRAW_LINE();
163 BENCHMARK(Encode_10) {
164 auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
165 bm::encodeSmallData.end());
170 auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
171 bm::encodeLargeData.end());
175 BENCHMARK_DRAW_LINE();
177 BENCHMARK(Select64, iters) {
178 typedef instructions::EF_TEST_ARCH instr;
179 constexpr uint64_t kPrime = uint64_t(-59);
180 for (uint64_t x = kPrime, i = 0; i < iters; x *= kPrime, i += 1) {
181 size_t w = instr::popcount(x);
182 folly::doNotOptimizeAway(folly::select64<instr>(x, w - 1));
187 Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz (turbo off),
188 using instructions::Haswell and GCC 4.9 with --bm_min_usec 100000.
189 ============================================================================
190 folly/experimental/test/EliasFanoCodingTest.cpp relative time/iter iters/s
191 ============================================================================
193 Skip_ForwardQ128(1) 3.92ns 255.28M
194 Skip_ForwardQ128(2) 5.08ns 197.04M
195 Skip_ForwardQ128(4_pm_1) 7.04ns 142.02M
196 Skip_ForwardQ128(16_pm_4) 19.68ns 50.82M
197 Skip_ForwardQ128(64_pm_16) 27.58ns 36.26M
198 Skip_ForwardQ128(256_pm_64) 32.49ns 30.78M
199 Skip_ForwardQ128(1024_pm_256) 33.39ns 29.95M
200 Jump_ForwardQ128 34.05ns 29.37M
201 ----------------------------------------------------------------------------
202 SkipTo_SkipQ128(1) 4.42ns 226.49M
203 SkipTo_SkipQ128(2) 8.58ns 116.55M
204 SkipTo_SkipQ128(4_pm_1) 11.43ns 87.50M
205 SkipTo_SkipQ128(16_pm_4) 31.19ns 32.06M
206 SkipTo_SkipQ128(64_pm_16) 43.88ns 22.79M
207 SkipTo_SkipQ128(256_pm_64) 49.08ns 20.37M
208 SkipTo_SkipQ128(1024_pm_256) 52.24ns 19.14M
209 JumpTo_SkipQ128 54.61ns 18.31M
210 ----------------------------------------------------------------------------
211 Encode_10 117.24ns 8.53M
213 ----------------------------------------------------------------------------
214 Select64 8.04ns 124.35M
215 ============================================================================
218 int main(int argc, char** argv) {
219 testing::InitGoogleTest(&argc, argv);
220 gflags::ParseCommandLineFlags(&argc, &argv, true);
222 auto ret = RUN_ALL_TESTS();
223 if (ret == 0 && FLAGS_benchmark) {
225 folly::runBenchmarks();