2 * Copyright 2015-present 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/BitVectorCoding.h>
24 #include <folly/experimental/Select64.h>
25 #include <folly/experimental/test/CodingTestUtils.h>
27 using namespace folly::compression;
30 #define BV_TEST_ARCH Default
31 #endif // BV_TEST_ARCH
33 class BitVectorCodingTest : public ::testing::Test {
36 typedef BitVectorEncoder<uint32_t, size_t> Encoder;
37 typedef BitVectorReader<Encoder, instructions::BV_TEST_ARCH> Reader;
38 testEmpty<Reader, Encoder>();
41 template <size_t kSkipQuantum, size_t kForwardQuantum>
43 typedef BitVectorEncoder<uint32_t, uint32_t, kSkipQuantum, kForwardQuantum>
45 typedef BitVectorReader<Encoder> Reader;
46 testAll<Reader, Encoder>(generateRandomList(100 * 1000, 10 * 1000 * 1000));
47 testAll<Reader, Encoder>(generateSeqList(1, 100000, 100));
51 TEST_F(BitVectorCodingTest, Empty) {
55 TEST_F(BitVectorCodingTest, Simple) {
59 TEST_F(BitVectorCodingTest, SkipPointers) {
63 TEST_F(BitVectorCodingTest, ForwardPointers) {
67 TEST_F(BitVectorCodingTest, SkipForwardPointers) {
68 doTestAll<128, 128>();
73 typedef BitVectorEncoder<uint32_t, uint32_t, 128, 128> Encoder;
74 typedef BitVectorReader<Encoder> Reader;
76 std::vector<uint32_t> data;
77 std::vector<size_t> order;
79 std::vector<uint32_t> encodeSmallData;
80 std::vector<uint32_t> encodeLargeData;
82 typename Encoder::MutableCompressedList list;
87 data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
88 list = Encoder::encode(data.begin(), data.end());
90 order.resize(data.size());
91 std::iota(order.begin(), order.end(), size_t());
92 std::shuffle(order.begin(), order.end(), gen);
94 encodeSmallData = generateRandomList(10, 100 * 1000, gen);
95 encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
98 void free() { list.free(); }
102 BENCHMARK(Next, iters) { bmNext<bm::Reader>(bm::list, bm::data, iters); }
104 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
105 bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
109 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
110 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
111 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
112 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
113 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
114 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
115 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
117 BENCHMARK(Jump_ForwardQ128, iters) {
118 bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
121 BENCHMARK_DRAW_LINE();
123 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
124 bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
128 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
129 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
130 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
131 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
132 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
133 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
134 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
136 BENCHMARK(JumpTo_SkipQ128, iters) {
137 bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
140 BENCHMARK_DRAW_LINE();
142 BENCHMARK(Encode_10) {
143 auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
144 bm::encodeSmallData.end());
149 auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
150 bm::encodeLargeData.end());
155 Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz (turbo off),
156 using instructions::Default and GCC 4.8 with --bm_min_usec 100000.
157 ============================================================================
158 folly/experimental/test/BitVectorCodingTest.cpp relative time/iter iters/s
159 ============================================================================
161 Skip_ForwardQ128(1) 11.56ns 86.53M
162 Skip_ForwardQ128(2) 23.30ns 42.93M
163 Skip_ForwardQ128(4_pm_1) 52.99ns 18.87M
164 Skip_ForwardQ128(16_pm_4) 200.85ns 4.98M
165 Skip_ForwardQ128(64_pm_16) 733.20ns 1.36M
166 Skip_ForwardQ128(256_pm_64) 748.35ns 1.34M
167 Skip_ForwardQ128(1024_pm_256) 742.77ns 1.35M
168 Jump_ForwardQ128 752.98ns 1.33M
169 ----------------------------------------------------------------------------
170 SkipTo_SkipQ128(1) 23.47ns 42.62M
171 SkipTo_SkipQ128(2) 24.48ns 40.85M
172 SkipTo_SkipQ128(4_pm_1) 22.16ns 45.13M
173 SkipTo_SkipQ128(16_pm_4) 28.43ns 35.17M
174 SkipTo_SkipQ128(64_pm_16) 45.51ns 21.97M
175 SkipTo_SkipQ128(256_pm_64) 44.03ns 22.71M
176 SkipTo_SkipQ128(1024_pm_256) 45.84ns 21.81M
177 JumpTo_SkipQ128 15.33ns 65.25M
178 ----------------------------------------------------------------------------
179 Encode_10 1.60us 624.33K
181 ============================================================================
184 int main(int argc, char** argv) {
185 testing::InitGoogleTest(&argc, argv);
186 gflags::ParseCommandLineFlags(&argc, &argv, true);
188 auto ret = RUN_ALL_TESTS();
189 if (ret == 0 && FLAGS_benchmark) {
191 folly::runBenchmarks();