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.
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, Interface) {
69 // Make sure decodeVarint() accepts all of StringPiece, MutableStringPiece,
70 // ByteRange, and MutableByteRange.
73 StringPiece sp(&c, 1);
74 EXPECT_EQ(decodeVarint(sp), 0);
76 MutableStringPiece msp(&c, 1);
77 EXPECT_EQ(decodeVarint(msp), 0);
79 ByteRange br(reinterpret_cast<unsigned char*>(&c), 1);
80 EXPECT_EQ(decodeVarint(br), 0);
82 MutableByteRange mbr(reinterpret_cast<unsigned char*>(&c), 1);
83 EXPECT_EQ(decodeVarint(mbr), 0);
86 TEST(Varint, Simple) {
89 testVarint(127, {127});
90 testVarint(128, {0x80, 0x01});
91 testVarint(300, {0xac, 0x02});
92 testVarint(16383, {0xff, 0x7f});
93 testVarint(16384, {0x80, 0x80, 0x01});
95 testVarint(static_cast<uint32_t>(-1),
96 {0xff, 0xff, 0xff, 0xff, 0x0f});
97 testVarint(static_cast<uint64_t>(-1),
98 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01});
101 TEST(ZigZag, Simple) {
102 EXPECT_EQ(0, encodeZigZag(0));
103 EXPECT_EQ(1, encodeZigZag(-1));
104 EXPECT_EQ(2, encodeZigZag(1));
105 EXPECT_EQ(3, encodeZigZag(-2));
106 EXPECT_EQ(4, encodeZigZag(2));
108 EXPECT_EQ(0, decodeZigZag(0));
109 EXPECT_EQ(-1, decodeZigZag(1));
110 EXPECT_EQ(1, decodeZigZag(2));
111 EXPECT_EQ(-2, decodeZigZag(3));
112 EXPECT_EQ(2, decodeZigZag(4));
117 constexpr size_t kNumValues = 1000;
118 std::vector<uint64_t> gValues;
119 std::vector<uint64_t> gDecodedValues;
120 std::vector<uint8_t> gEncoded;
122 void generateRandomValues() {
123 LOG(INFO) << "Random seed is " << FLAGS_random_seed;
124 std::mt19937 rng(FLAGS_random_seed);
126 // Approximation of power law
127 std::uniform_int_distribution<int> numBytes(1, 8);
128 std::uniform_int_distribution<int> byte(0, 255);
130 gValues.resize(kNumValues);
131 gDecodedValues.resize(kNumValues);
132 gEncoded.resize(kNumValues * kMaxVarintLength64);
133 for (size_t i = 0; i < kNumValues; ++i) {
134 int n = numBytes(rng);
136 for (int j = 0; j < n; ++j) {
137 val = (val << 8) + byte(rng);
143 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
145 // I0814 19:13:14.466256 7504 VarintTest.cpp:146] Random seed is -1216518886
146 // ============================================================================
147 // folly/test/VarintTest.cpp relative time/iter iters/s
148 // ============================================================================
149 // VarintEncoding 6.69us 149.37K
150 // VarintDecoding 6.85us 145.90K
151 // ============================================================================
153 // Disabling the "fast path" code in decodeVarint hurts performance:
155 // I0814 19:15:13.871467 9550 VarintTest.cpp:156] Random seed is -1216518886
156 // ============================================================================
157 // folly/test/VarintTest.cpp relative time/iter iters/s
158 // ============================================================================
159 // VarintEncoding 6.75us 148.26K
160 // VarintDecoding 12.60us 79.37K
161 // ============================================================================
163 BENCHMARK(VarintEncoding, iters) {
164 uint8_t* start = &(*gEncoded.begin());
168 for (auto& v : gValues) {
169 p += encodeVarint(v, p);
173 gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
176 BENCHMARK(VarintDecoding, iters) {
179 ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
180 while (!range.empty()) {
181 gDecodedValues[i++] = decodeVarint(range);
190 int main(int argc, char *argv[]) {
191 testing::InitGoogleTest(&argc, argv);
192 gflags::ParseCommandLineFlags(&argc, &argv, true);
193 google::InitGoogleLogging(argv[0]);
194 int ret = RUN_ALL_TESTS();
196 folly::test::generateRandomValues();
197 folly::runBenchmarksOnFlag();