2 * Copyright 2014 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.
17 #include <folly/Varint.h>
20 #include <initializer_list>
24 #include <glog/logging.h>
25 #include <gtest/gtest.h>
27 #include <folly/Benchmark.h>
28 #include <folly/Random.h>
30 DEFINE_int32(random_seed, folly::randomNumberSeed(), "random seed");
32 namespace folly { namespace test {
34 void testVarint(uint64_t val, std::initializer_list<uint8_t> bytes) {
35 size_t n = bytes.size();
36 ByteRange expected(&*bytes.begin(), n);
39 uint8_t buf[kMaxVarintLength64];
40 EXPECT_EQ(expected.size(), encodeVarint(val, buf));
41 EXPECT_TRUE(ByteRange(buf, expected.size()) == expected);
45 ByteRange r = expected;
46 uint64_t decoded = decodeVarint(r);
47 EXPECT_TRUE(r.empty());
48 EXPECT_EQ(val, decoded);
51 if (n < kMaxVarintLength64) {
52 // Try from a full buffer too, different code path
53 uint8_t buf[kMaxVarintLength64];
54 memcpy(buf, &*bytes.begin(), n);
56 uint8_t fills[] = {0, 0x7f, 0x80, 0xff};
58 for (uint8_t fill : fills) {
59 memset(buf + n, fill, kMaxVarintLength64 - n);
60 ByteRange r(buf, kMaxVarintLength64);
61 uint64_t decoded = decodeVarint(r);
62 EXPECT_EQ(val, decoded);
63 EXPECT_EQ(kMaxVarintLength64 - n, r.size());
68 TEST(Varint, Simple) {
71 testVarint(127, {127});
72 testVarint(128, {0x80, 0x01});
73 testVarint(300, {0xac, 0x02});
74 testVarint(16383, {0xff, 0x7f});
75 testVarint(16384, {0x80, 0x80, 0x01});
77 testVarint(static_cast<uint32_t>(-1),
78 {0xff, 0xff, 0xff, 0xff, 0x0f});
79 testVarint(static_cast<uint64_t>(-1),
80 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01});
83 TEST(ZigZag, Simple) {
84 EXPECT_EQ(0, encodeZigZag(0));
85 EXPECT_EQ(1, encodeZigZag(-1));
86 EXPECT_EQ(2, encodeZigZag(1));
87 EXPECT_EQ(3, encodeZigZag(-2));
88 EXPECT_EQ(4, encodeZigZag(2));
90 EXPECT_EQ(0, decodeZigZag(0));
91 EXPECT_EQ(-1, decodeZigZag(1));
92 EXPECT_EQ(1, decodeZigZag(2));
93 EXPECT_EQ(-2, decodeZigZag(3));
94 EXPECT_EQ(2, decodeZigZag(4));
99 constexpr size_t kNumValues = 1000;
100 std::vector<uint64_t> gValues;
101 std::vector<uint64_t> gDecodedValues;
102 std::vector<uint8_t> gEncoded;
104 void generateRandomValues() {
105 LOG(INFO) << "Random seed is " << FLAGS_random_seed;
106 std::mt19937 rng(FLAGS_random_seed);
108 // Approximation of power law
109 std::uniform_int_distribution<int> numBytes(1, 8);
110 std::uniform_int_distribution<int> byte(0, 255);
112 gValues.resize(kNumValues);
113 gDecodedValues.resize(kNumValues);
114 gEncoded.resize(kNumValues * kMaxVarintLength64);
115 for (size_t i = 0; i < kNumValues; ++i) {
116 int n = numBytes(rng);
118 for (size_t j = 0; j < n; ++j) {
119 val = (val << 8) + byte(rng);
125 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
127 // I0814 19:13:14.466256 7504 VarintTest.cpp:146] Random seed is -1216518886
128 // ============================================================================
129 // folly/test/VarintTest.cpp relative time/iter iters/s
130 // ============================================================================
131 // VarintEncoding 6.69us 149.37K
132 // VarintDecoding 6.85us 145.90K
133 // ============================================================================
135 // Disabling the "fast path" code in decodeVarint hurts performance:
137 // I0814 19:15:13.871467 9550 VarintTest.cpp:156] Random seed is -1216518886
138 // ============================================================================
139 // folly/test/VarintTest.cpp relative time/iter iters/s
140 // ============================================================================
141 // VarintEncoding 6.75us 148.26K
142 // VarintDecoding 12.60us 79.37K
143 // ============================================================================
145 BENCHMARK(VarintEncoding, iters) {
146 uint8_t* start = &(*gEncoded.begin());
148 bool empty = (iters == 0);
151 for (auto& v : gValues) {
152 p += encodeVarint(v, p);
156 gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
159 BENCHMARK(VarintDecoding, iters) {
162 ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
163 while (!range.empty()) {
164 gDecodedValues[i++] = decodeVarint(range);
173 int main(int argc, char *argv[]) {
174 testing::InitGoogleTest(&argc, argv);
175 gflags::ParseCommandLineFlags(&argc, &argv, true);
176 google::InitGoogleLogging(argv[0]);
177 int ret = RUN_ALL_TESTS();
179 folly::test::generateRandomValues();
180 folly::runBenchmarksOnFlag();