2 * Copyright 2013-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.
17 #include <folly/Varint.h>
20 #include <initializer_list>
24 #include <glog/logging.h>
26 #include <folly/Benchmark.h>
27 #include <folly/Random.h>
28 #include <folly/portability/GTest.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 void testVarintFail(std::initializer_list<uint8_t> bytes) {
102 size_t n = bytes.size();
103 ByteRange data(&*bytes.begin(), n);
104 auto ret = tryDecodeVarint(data);
105 EXPECT_FALSE(ret.hasValue());
109 testVarintFail({0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff});
112 TEST(ZigZag, Simple) {
113 EXPECT_EQ(0, encodeZigZag(0));
114 EXPECT_EQ(1, encodeZigZag(-1));
115 EXPECT_EQ(2, encodeZigZag(1));
116 EXPECT_EQ(3, encodeZigZag(-2));
117 EXPECT_EQ(4, encodeZigZag(2));
119 EXPECT_EQ(0, decodeZigZag(0));
120 EXPECT_EQ(-1, decodeZigZag(1));
121 EXPECT_EQ(1, decodeZigZag(2));
122 EXPECT_EQ(-2, decodeZigZag(3));
123 EXPECT_EQ(2, decodeZigZag(4));
128 constexpr size_t kNumValues = 1000;
129 std::vector<uint64_t> gValues;
130 std::vector<uint64_t> gDecodedValues;
131 std::vector<uint8_t> gEncoded;
133 void generateRandomValues() {
134 LOG(INFO) << "Random seed is " << FLAGS_random_seed;
135 std::mt19937 rng(FLAGS_random_seed);
137 // Approximation of power law
138 std::uniform_int_distribution<int> numBytes(1, 8);
139 std::uniform_int_distribution<int> byte(0, 255);
141 gValues.resize(kNumValues);
142 gDecodedValues.resize(kNumValues);
143 gEncoded.resize(kNumValues * kMaxVarintLength64);
144 for (size_t i = 0; i < kNumValues; ++i) {
145 int n = numBytes(rng);
147 for (int j = 0; j < n; ++j) {
148 val = (val << 8) + byte(rng);
154 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
156 // I0814 19:13:14.466256 7504 VarintTest.cpp:146] Random seed is -1216518886
157 // ============================================================================
158 // folly/test/VarintTest.cpp relative time/iter iters/s
159 // ============================================================================
160 // VarintEncoding 6.69us 149.37K
161 // VarintDecoding 6.85us 145.90K
162 // ============================================================================
164 // Disabling the "fast path" code in decodeVarint hurts performance:
166 // I0814 19:15:13.871467 9550 VarintTest.cpp:156] Random seed is -1216518886
167 // ============================================================================
168 // folly/test/VarintTest.cpp relative time/iter iters/s
169 // ============================================================================
170 // VarintEncoding 6.75us 148.26K
171 // VarintDecoding 12.60us 79.37K
172 // ============================================================================
174 BENCHMARK(VarintEncoding, iters) {
175 uint8_t* start = &(*gEncoded.begin());
179 for (auto& v : gValues) {
180 p += encodeVarint(v, p);
184 gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
187 BENCHMARK(VarintDecoding, iters) {
190 ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
191 while (!range.empty()) {
192 gDecodedValues[i++] = decodeVarint(range);
201 int main(int argc, char *argv[]) {
202 testing::InitGoogleTest(&argc, argv);
203 gflags::ParseCommandLineFlags(&argc, &argv, true);
204 google::InitGoogleLogging(argv[0]);
205 int ret = RUN_ALL_TESTS();
207 folly::test::generateRandomValues();
208 folly::runBenchmarksOnFlag();