folly/test/VarintTest.cpp

   1 /*
   2  * Copyright 2014 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, Simple) {
  69   testVarint(0, {0});
  70   testVarint(1, {1});
  71   testVarint(127, {127});
  72   testVarint(128, {0x80, 0x01});
  73   testVarint(300, {0xac, 0x02});
  74   testVarint(16383, {0xff, 0x7f});
  75   testVarint(16384, {0x80, 0x80, 0x01});
  76
  77   testVarint(static_cast<uint32_t>(-1),
  78              {0xff, 0xff, 0xff, 0xff, 0x0f});
  79   testVarint(static_cast<uint64_t>(-1),
  80              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01});
  81 }
  82
  83 TEST(ZigZag, Simple) {
  84   EXPECT_EQ(0, encodeZigZag(0));
  85   EXPECT_EQ(1, encodeZigZag(-1));
  86   EXPECT_EQ(2, encodeZigZag(1));
  87   EXPECT_EQ(3, encodeZigZag(-2));
  88   EXPECT_EQ(4, encodeZigZag(2));
  89
  90   EXPECT_EQ(0,  decodeZigZag(0));
  91   EXPECT_EQ(-1, decodeZigZag(1));
  92   EXPECT_EQ(1,  decodeZigZag(2));
  93   EXPECT_EQ(-2, decodeZigZag(3));
  94   EXPECT_EQ(2,  decodeZigZag(4));
  95 }
  96
  97 namespace {
  98
  99 constexpr size_t kNumValues = 1000;
 100 std::vector<uint64_t> gValues;
 101 std::vector<uint64_t> gDecodedValues;
 102 std::vector<uint8_t> gEncoded;
 103
 104 void generateRandomValues() {
 105   LOG(INFO) << "Random seed is " << FLAGS_random_seed;
 106   std::mt19937 rng(FLAGS_random_seed);
 107
 108   // Approximation of power law
 109   std::uniform_int_distribution<int> numBytes(1, 8);
 110   std::uniform_int_distribution<int> byte(0, 255);
 111
 112   gValues.resize(kNumValues);
 113   gDecodedValues.resize(kNumValues);
 114   gEncoded.resize(kNumValues * kMaxVarintLength64);
 115   for (size_t i = 0; i < kNumValues; ++i) {
 116     int n = numBytes(rng);
 117     uint64_t val = 0;
 118     for (size_t j = 0; j < n; ++j) {
 119       val = (val << 8) + byte(rng);
 120     }
 121     gValues[i] = val;
 122   }
 123 }
 124
 125 // Benchmark results (Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, Linux x86_64)
 126 //
 127 // I0814 19:13:14.466256  7504 VarintTest.cpp:146] Random seed is -1216518886
 128 // ============================================================================
 129 // folly/test/VarintTest.cpp                       relative  time/iter  iters/s
 130 // ============================================================================
 131 // VarintEncoding                                               6.69us  149.37K
 132 // VarintDecoding                                               6.85us  145.90K
 133 // ============================================================================
 134 //
 135 // Disabling the "fast path" code in decodeVarint hurts performance:
 136 //
 137 // I0814 19:15:13.871467  9550 VarintTest.cpp:156] Random seed is -1216518886
 138 // ============================================================================
 139 // folly/test/VarintTest.cpp                       relative  time/iter  iters/s
 140 // ============================================================================
 141 // VarintEncoding                                               6.75us  148.26K
 142 // VarintDecoding                                              12.60us   79.37K
 143 // ============================================================================
 144
 145 BENCHMARK(VarintEncoding, iters) {
 146   uint8_t* start = &(*gEncoded.begin());
 147   uint8_t* p = start;
 148   bool empty = (iters == 0);
 149   while (iters--) {
 150     p = start;
 151     for (auto& v : gValues) {
 152       p += encodeVarint(v, p);
 153     }
 154   }
 155
 156   gEncoded.erase(gEncoded.begin() + (p - start), gEncoded.end());
 157 }
 158
 159 BENCHMARK(VarintDecoding, iters) {
 160   while (iters--) {
 161     size_t i = 0;
 162     ByteRange range(&(*gEncoded.begin()), &(*gEncoded.end()));
 163     while (!range.empty()) {
 164       gDecodedValues[i++] = decodeVarint(range);
 165     }
 166   }
 167 }
 168
 169 }  // namespace
 170
 171 }}  // namespaces
 172
 173 int main(int argc, char *argv[]) {
 174   testing::InitGoogleTest(&argc, argv);
 175   gflags::ParseCommandLineFlags(&argc, &argv, true);
 176   google::InitGoogleLogging(argv[0]);
 177   int ret = RUN_ALL_TESTS();
 178   if (ret == 0) {
 179     folly::test::generateRandomValues();
 180     folly::runBenchmarksOnFlag();
 181   }
 182   return ret;
 183 }
 184