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 | |
28 | using namespace folly::compression; |
29 | |
30 | class 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 | |
48 | TEST_F(BitVectorCodingTest, Empty) { |
49 | doTestEmpty(); |
50 | } |
51 | |
52 | TEST_F(BitVectorCodingTest, Simple) { |
53 | doTestAll<0, 0>(); |
54 | } |
55 | |
56 | TEST_F(BitVectorCodingTest, SkipPointers) { |
57 | doTestAll<128, 0>(); |
58 | } |
59 | |
60 | TEST_F(BitVectorCodingTest, ForwardPointers) { |
61 | doTestAll<0, 128>(); |
62 | } |
63 | |
64 | TEST_F(BitVectorCodingTest, SkipForwardPointers) { |
65 | doTestAll<128, 128>(); |
66 | } |
67 | |
68 | namespace bm { |
69 | |
70 | typedef BitVectorEncoder<uint32_t, uint32_t, 128, 128> Encoder; |
71 | |
72 | std::vector<uint32_t> data; |
73 | std::vector<size_t> order; |
74 | |
75 | std::vector<uint32_t> encodeSmallData; |
76 | std::vector<uint32_t> encodeLargeData; |
77 | |
78 | typename Encoder::MutableCompressedList list; |
79 | |
80 | void 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 | |
94 | void free() { |
95 | list.free(); |
96 | } |
97 | |
98 | } // namespace bm |
99 | |
100 | BENCHMARK(Next, iters) { |
101 | dispatchInstructions([&](auto instructions) { |
102 | bmNext<BitVectorReader<bm::Encoder, decltype(instructions)>>( |
103 | bm::list, bm::data, iters); |
104 | }); |
105 | } |
106 | |
107 | size_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 | |
115 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0) |
116 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1) |
117 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2) |
118 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4) |
119 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6) |
120 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8) |
121 | BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10) |
122 | |
123 | BENCHMARK(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 | |
130 | BENCHMARK_DRAW_LINE(); |
131 | |
132 | size_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 | |
140 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0) |
141 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1) |
142 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2) |
143 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4) |
144 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6) |
145 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8) |
146 | BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10) |
147 | |
148 | BENCHMARK(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 | |
155 | BENCHMARK_DRAW_LINE(); |
156 | |
157 | BENCHMARK(Encode_10) { |
158 | auto list = bm::Encoder::encode( |
159 | bm::encodeSmallData.begin(), bm::encodeSmallData.end()); |
160 | list.free(); |
161 | } |
162 | |
163 | BENCHMARK(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. |
172 | V1008 12:32:25.863286 101188 Instructions.h:161] Will use folly::compression::instructions::Haswell |
173 | ============================================================================ |
174 | folly/experimental/test/BitVectorCodingTest.cpp relative time/iter iters/s |
175 | ============================================================================ |
176 | Next 9.52ns 104.99M |
177 | Skip_ForwardQ128(1) 13.90ns 71.96M |
178 | Skip_ForwardQ128(2) 25.02ns 39.97M |
179 | Skip_ForwardQ128(4_pm_1) 28.25ns 35.40M |
180 | Skip_ForwardQ128(16_pm_4) 39.64ns 25.23M |
181 | Skip_ForwardQ128(64_pm_16) 112.19ns 8.91M |
182 | Skip_ForwardQ128(256_pm_64) 137.75ns 7.26M |
183 | Skip_ForwardQ128(1024_pm_256) 131.56ns 7.60M |
184 | Jump_ForwardQ128 133.30ns 7.50M |
185 | ---------------------------------------------------------------------------- |
186 | SkipTo_SkipQ128(1) 13.30ns 75.16M |
187 | SkipTo_SkipQ128(2) 13.81ns 72.40M |
188 | SkipTo_SkipQ128(4_pm_1) 12.23ns 81.80M |
189 | SkipTo_SkipQ128(16_pm_4) 13.72ns 72.89M |
190 | SkipTo_SkipQ128(64_pm_16) 21.18ns 47.22M |
191 | SkipTo_SkipQ128(256_pm_64) 20.15ns 49.63M |
192 | SkipTo_SkipQ128(1024_pm_256) 21.86ns 45.74M |
193 | JumpTo_SkipQ128 23.10ns 43.30M |
194 | ---------------------------------------------------------------------------- |
195 | Encode_10 344.50ns 2.90M |
196 | Encode 10.88ms 91.90 |
197 | ============================================================================ |
198 | #endif |
199 | |
200 | int 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 | |