folly/test/VarintTest.cpp

   1 /*
   2  * Copyright 2015 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 #include <gtest/gtest.h>
  26
  27 #include <folly/Benchmark.h>
  28 #include <folly/Random.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 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));
 107
 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));
 113 }
 114
 115 namespace {
 116
 117 constexpr size_t kNumValues = 1000;
 118 std::vector<uint64_t> gValues;
 119 std::vector<uint64_t> gDecodedValues;
 120 std::vector<uint8_t> gEncoded;
 121
 122 void generateRandomValues() {
 123   LOG(INFO) << "Random seed is " << FLAGS_random_seed;
 124   std::mt19937 rng(FLAGS_random_seed);
 125
 126   // Approximation of power law
 127   std::uniform_int_distribution<int> numBytes(1, 8);
 128   std::uniform_int_distribution<int> byte(0, 255);
 129
 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);
 135     uint64_t val = 0;
 136     for (int j = 0; j < n; ++j) {
 137       val = (val << 8) + byte(rng);
 138     }
 139     gValues[i] = val;
 140   }
 141 }
 142
 143 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
 144 //
 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 // ============================================================================
 152 //
 153 // Disabling the "fast path" code in decodeVarint hurts performance:
 154 //
 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 // ============================================================================
 162
 163 BENCHMARK(VarintEncoding, iters) {
 164   uint8_t* start = &(*gEncoded.begin());
 165   uint8_t* p = start;
 166   while (iters--) {
 167     p = start;
 168     for (auto& v : gValues) {
 169       p += encodeVarint(v, p);
 170     }
 171   }
 172
 173   gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
 174 }
 175
 176 BENCHMARK(VarintDecoding, iters) {
 177   while (iters--) {
 178     size_t i = 0;
 179     ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
 180     while (!range.empty()) {
 181       gDecodedValues[i++] = decodeVarint(range);
 182     }
 183   }
 184 }
 185
 186 }  // namespace
 187
 188 }}  // namespaces
 189
 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();
 195   if (ret == 0) {
 196     folly::test::generateRandomValues();
 197     folly::runBenchmarksOnFlag();
 198   }
 199   return ret;
 200 }