1/*
2 * Copyright 2015-present 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 <numeric>
19#include <random>
20#include <vector>
21
22#include <folly/Benchmark.h>
23#include <folly/experimental/BitVectorCoding.h>
24#include <folly/experimental/Select64.h>
25#include <folly/experimental/test/CodingTestUtils.h>
26#include <folly/init/Init.h>
27
28using namespace folly::compression;
29
30class BitVectorCodingTest : public ::testing::Test {
31 public:
32 void doTestEmpty() {
33 typedef BitVectorEncoder<uint32_t, size_t> Encoder;
34 typedef BitVectorReader<Encoder, instructions::Default> Reader;
35 testEmpty<Reader, Encoder>();
36 }
37
38 template <size_t kSkipQuantum, size_t kForwardQuantum>
39 void doTestAll() {
40 typedef BitVectorEncoder<uint32_t, uint32_t, kSkipQuantum, kForwardQuantum>
41 Encoder;
42 typedef BitVectorReader<Encoder> Reader;
43 testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
44 testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
45 }
46};
47
48TEST_F(BitVectorCodingTest, Empty) {
49 doTestEmpty();
50}
51
52TEST_F(BitVectorCodingTest, Simple) {
53 doTestAll<0, 0>();
54}
55
56TEST_F(BitVectorCodingTest, SkipPointers) {
57 doTestAll<128, 0>();
58}
59
60TEST_F(BitVectorCodingTest, ForwardPointers) {
61 doTestAll<0, 128>();
62}
63
64TEST_F(BitVectorCodingTest, SkipForwardPointers) {
65 doTestAll<128, 128>();
66}
67
68namespace bm {
69
70typedef BitVectorEncoder<uint32_t, uint32_t, 128, 128> Encoder;
71
72std::vector<uint32_t> data;
73std::vector<size_t> order;
74
75std::vector<uint32_t> encodeSmallData;
76std::vector<uint32_t> encodeLargeData;
77
78typename Encoder::MutableCompressedList list;
79
80void init() {
81 std::mt19937 gen;
82
83 data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
84 list = Encoder::encode(data.begin(), data.end());
85
86 order.resize(data.size());
87 std::iota(order.begin(), order.end(), size_t());
88 std::shuffle(order.begin(), order.end(), gen);
89
90 encodeSmallData = generateRandomList(10, 100 * 1000, gen);
91 encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
92}
93
94void free() {
95 list.free();
96}
97
98} // namespace bm
99
100BENCHMARK(Next, iters) {
101 dispatchInstructions([&](auto instructions) {
102 bmNext<BitVectorReader<bm::Encoder, decltype(instructions)>>(
103 bm::list, bm::data, iters);
104 });
105}
106
107size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
108 dispatchInstructions([&](auto instructions) {
109 bmSkip<BitVectorReader<bm::Encoder, decltype(instructions)>>(
110 bm::list, bm::data, logAvgSkip, iters);
111 });
112 return iters;
113}
114
115BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
116BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
117BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
118BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
119BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
120BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
121BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
122
123BENCHMARK(Jump_ForwardQ128, iters) {
124 dispatchInstructions([&](auto instructions) {
125 bmJump<BitVectorReader<bm::Encoder, decltype(instructions)>>(
126 bm::list, bm::data, bm::order, iters);
127 });
128}
129
130BENCHMARK_DRAW_LINE();
131
132size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
133 dispatchInstructions([&](auto instructions) {
134 bmSkipTo<BitVectorReader<bm::Encoder, decltype(instructions)>>(
135 bm::list, bm::data, logAvgSkip, iters);
136 });
137 return iters;
138}
139
140BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
141BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
142BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
143BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
144BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
145BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
146BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
147
148BENCHMARK(JumpTo_SkipQ128, iters) {
149 dispatchInstructions([&](auto instructions) {
150 bmJumpTo<BitVectorReader<bm::Encoder, decltype(instructions)>>(
151 bm::list, bm::data, bm::order, iters);
152 });
153}
154
155BENCHMARK_DRAW_LINE();
156
157BENCHMARK(Encode_10) {
158 auto list = bm::Encoder::encode(
159 bm::encodeSmallData.begin(), bm::encodeSmallData.end());
160 list.free();
161}
162
163BENCHMARK(Encode) {
164 auto list = bm::Encoder::encode(
165 bm::encodeLargeData.begin(), bm::encodeLargeData.end());
166 list.free();
167}
168
169#if 0
170// Intel(R) Xeon(R) CPU E5-2678 v3 @ 2.50GHz (turbo on),
171// Using GCC 5 with --bm_min_usec 100000.
172V1008 12:32:25.863286 101188 Instructions.h:161] Will use folly::compression::instructions::Haswell
173============================================================================
174folly/experimental/test/BitVectorCodingTest.cpp relative time/iter iters/s
175============================================================================
176Next 9.52ns 104.99M
177Skip_ForwardQ128(1) 13.90ns 71.96M
178Skip_ForwardQ128(2) 25.02ns 39.97M
179Skip_ForwardQ128(4_pm_1) 28.25ns 35.40M
180Skip_ForwardQ128(16_pm_4) 39.64ns 25.23M
181Skip_ForwardQ128(64_pm_16) 112.19ns 8.91M
182Skip_ForwardQ128(256_pm_64) 137.75ns 7.26M
183Skip_ForwardQ128(1024_pm_256) 131.56ns 7.60M
184Jump_ForwardQ128 133.30ns 7.50M
185----------------------------------------------------------------------------
186SkipTo_SkipQ128(1) 13.30ns 75.16M
187SkipTo_SkipQ128(2) 13.81ns 72.40M
188SkipTo_SkipQ128(4_pm_1) 12.23ns 81.80M
189SkipTo_SkipQ128(16_pm_4) 13.72ns 72.89M
190SkipTo_SkipQ128(64_pm_16) 21.18ns 47.22M
191SkipTo_SkipQ128(256_pm_64) 20.15ns 49.63M
192SkipTo_SkipQ128(1024_pm_256) 21.86ns 45.74M
193JumpTo_SkipQ128 23.10ns 43.30M
194----------------------------------------------------------------------------
195Encode_10 344.50ns 2.90M
196Encode 10.88ms 91.90
197============================================================================
198#endif
199
200int main(int argc, char** argv) {
201 testing::InitGoogleTest(&argc, argv);
202 folly::init(&argc, &argv);
203 gflags::ParseCommandLineFlags(&argc, &argv, true);
204
205 auto ret = RUN_ALL_TESTS();
206 if (ret == 0 && FLAGS_benchmark) {
207 bm::init();
208 folly::runBenchmarks();
209 bm::free();
210 }
211
212 return ret;
213}
214