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/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 constexpr size_t k1M = 1000000;
75 typedef BitVectorEncoder<uint32_t, uint32_t, 128, 128> Encoder;
76 typedef BitVectorReader<Encoder> Reader;
78 std::vector<uint32_t> data;
79 std::vector<size_t> order;
81 std::vector<uint32_t> encodeSmallData;
82 std::vector<uint32_t> encodeLargeData;
84 typename Encoder::CompressedList list;
89 data = generateRandomList(100 * 1000, 10 * 1000 * 1000, gen);
90 list = Encoder::encode(data.begin(), data.end());
92 order.resize(data.size());
93 std::iota(order.begin(), order.end(), size_t());
94 std::shuffle(order.begin(), order.end(), gen);
96 encodeSmallData = generateRandomList(10, 100 * 1000, gen);
97 encodeLargeData = generateRandomList(1000 * 1000, 100 * 1000 * 1000, gen);
100 void free() { list.free(); }
104 BENCHMARK(Next, iters) { bmNext<bm::Reader>(bm::list, bm::data, iters); }
106 size_t Skip_ForwardQ128(size_t iters, size_t logAvgSkip) {
107 bmSkip<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
111 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1, 0)
112 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 2, 1)
113 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 4_pm_1, 2)
114 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 16_pm_4, 4)
115 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 64_pm_16, 6)
116 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 256_pm_64, 8)
117 BENCHMARK_NAMED_PARAM_MULTI(Skip_ForwardQ128, 1024_pm_256, 10)
119 BENCHMARK(Jump_ForwardQ128, iters) {
120 bmJump<bm::Reader>(bm::list, bm::data, bm::order, iters);
123 BENCHMARK_DRAW_LINE();
125 size_t SkipTo_SkipQ128(size_t iters, size_t logAvgSkip) {
126 bmSkipTo<bm::Reader>(bm::list, bm::data, logAvgSkip, iters);
130 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1, 0)
131 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 2, 1)
132 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 4_pm_1, 2)
133 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 16_pm_4, 4)
134 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 64_pm_16, 6)
135 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 256_pm_64, 8)
136 BENCHMARK_NAMED_PARAM_MULTI(SkipTo_SkipQ128, 1024_pm_256, 10)
138 BENCHMARK(JumpTo_SkipQ128, iters) {
139 bmJumpTo<bm::Reader>(bm::list, bm::data, bm::order, iters);
142 BENCHMARK_DRAW_LINE();
144 BENCHMARK(Encode_10) {
145 auto list = bm::Encoder::encode(bm::encodeSmallData.begin(),
146 bm::encodeSmallData.end());
151 auto list = bm::Encoder::encode(bm::encodeLargeData.begin(),
152 bm::encodeLargeData.end());
157 Intel(R) Xeon(R) CPU E5-2673 v3 @ 2.40GHz (turbo off),
158 using instructions::Default and GCC 4.8 with --bm_min_usec 100000.
159 ============================================================================
160 folly/experimental/test/BitVectorCodingTest.cpp relative time/iter iters/s
161 ============================================================================
163 Skip_ForwardQ128(1) 11.56ns 86.53M
164 Skip_ForwardQ128(2) 23.30ns 42.93M
165 Skip_ForwardQ128(4_pm_1) 52.99ns 18.87M
166 Skip_ForwardQ128(16_pm_4) 200.85ns 4.98M
167 Skip_ForwardQ128(64_pm_16) 733.20ns 1.36M
168 Skip_ForwardQ128(256_pm_64) 748.35ns 1.34M
169 Skip_ForwardQ128(1024_pm_256) 742.77ns 1.35M
170 Jump_ForwardQ128 752.98ns 1.33M
171 ----------------------------------------------------------------------------
172 SkipTo_SkipQ128(1) 23.47ns 42.62M
173 SkipTo_SkipQ128(2) 24.48ns 40.85M
174 SkipTo_SkipQ128(4_pm_1) 22.16ns 45.13M
175 SkipTo_SkipQ128(16_pm_4) 28.43ns 35.17M
176 SkipTo_SkipQ128(64_pm_16) 45.51ns 21.97M
177 SkipTo_SkipQ128(256_pm_64) 44.03ns 22.71M
178 SkipTo_SkipQ128(1024_pm_256) 45.84ns 21.81M
179 JumpTo_SkipQ128 15.33ns 65.25M
180 ----------------------------------------------------------------------------
181 Encode_10 1.60us 624.33K
183 ============================================================================
186 int main(int argc, char** argv) {
187 testing::InitGoogleTest(&argc, argv);
188 gflags::ParseCommandLineFlags(&argc, &argv, true);
190 auto ret = RUN_ALL_TESTS();
191 if (ret == 0 && FLAGS_benchmark) {
193 folly::runBenchmarks();