1/*
2 * Copyright 2013-present Facebook, Inc.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17#include <folly/Varint.h>
18
19#include <array>
20#include <initializer_list>
21#include <random>
22#include <vector>
23
24#include <glog/logging.h>
25
26#include <folly/Benchmark.h>
27#include <folly/Random.h>
28#include <folly/portability/GTest.h>
29
30DEFINE_int32(random_seed, folly::randomNumberSeed(), "random seed");
31
32namespace folly {
33namespace test {
34
35void testVarint(uint64_t val, std::initializer_list<uint8_t> bytes) {
36 size_t n = bytes.size();
37 ByteRange expected(&*bytes.begin(), n);
38
39 {
40 uint8_t buf[kMaxVarintLength64];
41 EXPECT_EQ(expected.size(), encodeVarint(val, buf));
42 EXPECT_TRUE(ByteRange(buf, expected.size()) == expected);
43 EXPECT_EQ(expected.size(), encodeVarintSize(val));
44 }
45
46 {
47 ByteRange r = expected;
48 uint64_t decoded = decodeVarint(r);
49 EXPECT_TRUE(r.empty());
50 EXPECT_EQ(val, decoded);
51 }
52
53 if (n < kMaxVarintLength64) {
54 // Try from a full buffer too, different code path
55 uint8_t buf[kMaxVarintLength64];
56 memcpy(buf, &*bytes.begin(), n);
57
58 uint8_t fills[] = {0, 0x7f, 0x80, 0xff};
59
60 for (uint8_t fill : fills) {
61 memset(buf + n, fill, kMaxVarintLength64 - n);
62 ByteRange r(buf, kMaxVarintLength64);
63 uint64_t decoded = decodeVarint(r);
64 EXPECT_EQ(val, decoded);
65 EXPECT_EQ(kMaxVarintLength64 - n, r.size());
66 }
67 }
68}
69
70TEST(Varint, Interface) {
71 // Make sure decodeVarint() accepts all of StringPiece, MutableStringPiece,
72 // ByteRange, and MutableByteRange.
73 char c = 0;
74
75 StringPiece sp(&c, 1);
76 EXPECT_EQ(decodeVarint(sp), 0);
77
78 MutableStringPiece msp(&c, 1);
79 EXPECT_EQ(decodeVarint(msp), 0);
80
81 ByteRange br(reinterpret_cast<unsigned char*>(&c), 1);
82 EXPECT_EQ(decodeVarint(br), 0);
83
84 MutableByteRange mbr(reinterpret_cast<unsigned char*>(&c), 1);
85 EXPECT_EQ(decodeVarint(mbr), 0);
86}
87
88TEST(Varint, Simple) {
89 testVarint(0, {0});
90 testVarint(1, {1});
91 testVarint(127, {127});
92 testVarint(128, {0x80, 0x01});
93 testVarint(300, {0xac, 0x02});
94 testVarint(16383, {0xff, 0x7f});
95 testVarint(16384, {0x80, 0x80, 0x01});
96
97 testVarint(static_cast<uint32_t>(-1), {0xff, 0xff, 0xff, 0xff, 0x0f});
98 testVarint(
99 static_cast<uint64_t>(-1),
100 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01});
101}
102
103void testVarintFail(std::initializer_list<uint8_t> bytes) {
104 size_t n = bytes.size();
105 ByteRange data(&*bytes.begin(), n);
106 auto ret = tryDecodeVarint(data);
107 EXPECT_FALSE(ret.hasValue());
108}
109
110TEST(Varint, Fail) {
111 testVarintFail({0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff});
112}
113
114TEST(ZigZag, Simple) {
115 EXPECT_EQ(0, encodeZigZag(0));
116 EXPECT_EQ(1, encodeZigZag(-1));
117 EXPECT_EQ(2, encodeZigZag(1));
118 EXPECT_EQ(3, encodeZigZag(-2));
119 EXPECT_EQ(4, encodeZigZag(2));
120
121 EXPECT_EQ(0, decodeZigZag(0));
122 EXPECT_EQ(-1, decodeZigZag(1));
123 EXPECT_EQ(1, decodeZigZag(2));
124 EXPECT_EQ(-2, decodeZigZag(3));
125 EXPECT_EQ(2, decodeZigZag(4));
126}
127
128namespace {
129
130constexpr size_t kNumValues = 1000;
131std::vector<uint64_t> gValues;
132std::vector<uint64_t> gDecodedValues;
133std::vector<uint8_t> gEncoded;
134
135void generateRandomValues() {
136 LOG(INFO) << "Random seed is " << FLAGS_random_seed;
137 std::mt19937 rng(FLAGS_random_seed);
138
139 // Approximation of power law
140 std::uniform_int_distribution<int> numBytes(1, 8);
141 std::uniform_int_distribution<int> byte(0, 255);
142
143 gValues.resize(kNumValues);
144 gDecodedValues.resize(kNumValues);
145 gEncoded.resize(kNumValues * kMaxVarintLength64);
146 for (size_t i = 0; i < kNumValues; ++i) {
147 int n = numBytes(rng);
148 uint64_t val = 0;
149 for (int j = 0; j < n; ++j) {
150 val = (val << 8) + byte(rng);
151 }
152 gValues[i] = val;
153 }
154}
155
156// Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
157//
158// I0814 19:13:14.466256 7504 VarintTest.cpp:146] Random seed is -1216518886
159// ============================================================================
160// folly/test/VarintTest.cpp relative time/iter iters/s
161// ============================================================================
162// VarintEncoding 6.69us 149.37K
163// VarintDecoding 6.85us 145.90K
164// ============================================================================
165//
166// Disabling the "fast path" code in decodeVarint hurts performance:
167//
168// I0814 19:15:13.871467 9550 VarintTest.cpp:156] Random seed is -1216518886
169// ============================================================================
170// folly/test/VarintTest.cpp relative time/iter iters/s
171// ============================================================================
172// VarintEncoding 6.75us 148.26K
173// VarintDecoding 12.60us 79.37K
174// ============================================================================
175
176BENCHMARK(VarintEncoding, iters) {
177 uint8_t* start = &(*gEncoded.begin());
178 uint8_t* p = start;
179 while (iters--) {
180 p = start;
181 for (auto& v : gValues) {
182 p += encodeVarint(v, p);
183 }
184 }
185
186 gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
187}
188
189BENCHMARK(VarintDecoding, iters) {
190 while (iters--) {
191 size_t i = 0;
192 ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
193 while (!range.empty()) {
194 gDecodedValues[i++] = decodeVarint(range);
195 }
196 }
197}
198
199} // namespace
200} // namespace test
201} // namespace folly
202
203int main(int argc, char* argv[]) {
204 testing::InitGoogleTest(&argc, argv);
205 gflags::ParseCommandLineFlags(&argc, &argv, true);
206 google::InitGoogleLogging(argv[0]);
207 int ret = RUN_ALL_TESTS();
208 if (ret == 0) {
209 folly::test::generateRandomValues();
210 folly::runBenchmarksOnFlag();
211 }
212 return ret;
213}
214