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 | |
30 | DEFINE_int32(random_seed, folly::randomNumberSeed(), "random seed" ); |
31 | |
32 | namespace folly { |
33 | namespace test { |
34 | |
35 | void 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 | |
70 | TEST(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 | |
88 | TEST(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 | |
103 | void 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 | |
110 | TEST(Varint, Fail) { |
111 | testVarintFail({0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}); |
112 | } |
113 | |
114 | TEST(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 | |
128 | namespace { |
129 | |
130 | constexpr size_t kNumValues = 1000; |
131 | std::vector<uint64_t> gValues; |
132 | std::vector<uint64_t> gDecodedValues; |
133 | std::vector<uint8_t> gEncoded; |
134 | |
135 | void 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 | |
176 | BENCHMARK(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 | |
189 | BENCHMARK(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 | |
203 | int 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 | |