folly/test/VarintTest.cpp

   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 { namespace test {
  33
  34 void testVarint(uint64_t val, std::initializer_list<uint8_t> bytes) {
  35   size_t n = bytes.size();
  36   ByteRange expected(&*bytes.begin(), n);
  37
  38   {
  39     uint8_t buf[kMaxVarintLength64];
  40     EXPECT_EQ(expected.size(), encodeVarint(val, buf));
  41     EXPECT_TRUE(ByteRange(buf, expected.size()) == expected);
  42   }
  43
  44   {
  45     ByteRange r = expected;
  46     uint64_t decoded = decodeVarint(r);
  47     EXPECT_TRUE(r.empty());
  48     EXPECT_EQ(val, decoded);
  49   }
  50
  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);
  55
  56     uint8_t fills[] = {0, 0x7f, 0x80, 0xff};
  57
  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());
  64     }
  65   }
  66 }
  67
  68 TEST(Varint, Interface) {
  69   // Make sure decodeVarint() accepts all of StringPiece, MutableStringPiece,
  70   // ByteRange, and MutableByteRange.
  71   char c = 0;
  72
  73   StringPiece sp(&c, 1);
  74   EXPECT_EQ(decodeVarint(sp), 0);
  75
  76   MutableStringPiece msp(&c, 1);
  77   EXPECT_EQ(decodeVarint(msp), 0);
  78
  79   ByteRange br(reinterpret_cast<unsigned char*>(&c), 1);
  80   EXPECT_EQ(decodeVarint(br), 0);
  81
  82   MutableByteRange mbr(reinterpret_cast<unsigned char*>(&c), 1);
  83   EXPECT_EQ(decodeVarint(mbr), 0);
  84 }
  85
  86 TEST(Varint, Simple) {
  87   testVarint(0, {0});
  88   testVarint(1, {1});
  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});
  94
  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});
  99 }
 100
 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());
 106 }
 107
 108 TEST(Varint, Fail) {
 109   testVarintFail({0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff});
 110 }
 111
 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));
 118
 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));
 124 }
 125
 126 namespace {
 127
 128 constexpr size_t kNumValues = 1000;
 129 std::vector<uint64_t> gValues;
 130 std::vector<uint64_t> gDecodedValues;
 131 std::vector<uint8_t> gEncoded;
 132
 133 void generateRandomValues() {
 134   LOG(INFO) << "Random seed is " << FLAGS_random_seed;
 135   std::mt19937 rng(FLAGS_random_seed);
 136
 137   // Approximation of power law
 138   std::uniform_int_distribution<int> numBytes(1, 8);
 139   std::uniform_int_distribution<int> byte(0, 255);
 140
 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);
 146     uint64_t val = 0;
 147     for (int j = 0; j < n; ++j) {
 148       val = (val << 8) + byte(rng);
 149     }
 150     gValues[i] = val;
 151   }
 152 }
 153
 154 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
 155 //
 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 // ============================================================================
 163 //
 164 // Disabling the "fast path" code in decodeVarint hurts performance:
 165 //
 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 // ============================================================================
 173
 174 BENCHMARK(VarintEncoding, iters) {
 175   uint8_t* start = &(*gEncoded.begin());
 176   uint8_t* p = start;
 177   while (iters--) {
 178     p = start;
 179     for (auto& v : gValues) {
 180       p += encodeVarint(v, p);
 181     }
 182   }
 183
 184   gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
 185 }
 186
 187 BENCHMARK(VarintDecoding, iters) {
 188   while (iters--) {
 189     size_t i = 0;
 190     ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
 191     while (!range.empty()) {
 192       gDecodedValues[i++] = decodeVarint(range);
 193     }
 194   }
 195 }
 196
 197 } // namespace
 198 } // namespace test
 199 } // namespace folly
 200
 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();
 206   if (ret == 0) {
 207     folly::test::generateRandomValues();
 208     folly::runBenchmarksOnFlag();
 209   }
 210   return ret;
 211 }