folly/experimental/test/BitsBenchmark.cpp

   1 /*
   2  * Copyright 2017 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 #include <atomic>
  17 #include <glog/logging.h>
  18 #include <random>
  19 #include <memory>
  20
  21 #include <folly/Benchmark.h>
  22 #include <folly/experimental/Bits.h>
  23
  24 std::random_device rd;
  25
  26 const size_t kBufferSize = 1 << 10;
  27 std::vector<uint8_t> buffer(kBufferSize + 16);
  28
  29 template <class T>
  30 void benchmarkSet(size_t n, T) {
  31   size_t size = sizeof(T) * 6.9; // use 6.9 bits/byte
  32   const size_t k = 16;
  33   T values[k];
  34   BENCHMARK_SUSPEND {
  35     std::mt19937 gen(rd());
  36     T max, min;
  37     if (std::is_signed<T>::value) {
  38       max = (T(1) << (size - 1)) - 1;
  39       min = -(T(1) << (size - 1));
  40     } else {
  41       max = (T(1) << size) - 1;
  42       min = 0;
  43     }
  44     CHECK_LE(folly::findLastSet(max), size);
  45     CHECK_LE(folly::findLastSet(-min), size);
  46     std::uniform_int_distribution<T> dis(min, max);
  47     for (size_t i = 0; i < k; ++i) {
  48       values[i] = dis(gen);
  49     }
  50   }
  51
  52   for (size_t i = 0; i < n; ++i) {
  53     size_t bit = (i * 2973) % (kBufferSize * 8);
  54     size_t drop = i % size;
  55     folly::Bits<T>::set(reinterpret_cast<T *>(buffer.data()),
  56                         bit, size - drop, values[i % k] >> drop);
  57   }
  58
  59   folly::doNotOptimizeAway(
  60       folly::Bits<T>::test(reinterpret_cast<T *>(buffer.data()), 512));
  61 }
  62
  63 BENCHMARK_NAMED_PARAM(benchmarkSet, u16, uint16_t());
  64 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkSet, i16, int16_t());
  65 BENCHMARK_NAMED_PARAM(benchmarkSet, u32, uint32_t());
  66 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkSet, i32, int32_t());
  67 BENCHMARK_NAMED_PARAM(benchmarkSet, u64, uint64_t());
  68 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkSet, i64, int64_t());
  69
  70 BENCHMARK_DRAW_LINE();
  71
  72 std::atomic<int64_t> sum(0);
  73
  74 template <class T>
  75 void benchmarkGet(size_t n, T x) {
  76   size_t size = sizeof(T) * 6.9; // use 6.9 bits/byte
  77   for (size_t i = 0; i < n; ++i) {
  78     size_t bit = (i * 2973) % (kBufferSize * 8);
  79     size_t drop = i % size;
  80     x += folly::Bits<T>::get(
  81         reinterpret_cast<T *>(buffer.data()), bit, size - drop);
  82   }
  83   folly::doNotOptimizeAway(x);
  84 }
  85
  86 BENCHMARK_NAMED_PARAM(benchmarkGet, u16, uint16_t(0));
  87 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkGet, i16, int16_t(0));
  88 BENCHMARK_NAMED_PARAM(benchmarkGet, u32, uint32_t(0));
  89 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkGet, i32, int32_t(0));
  90 BENCHMARK_NAMED_PARAM(benchmarkGet, u64, uint64_t(0));
  91 BENCHMARK_RELATIVE_NAMED_PARAM(benchmarkGet, i64, int64_t(0));
  92
  93 #if 0
  94 ============================================================================
  95 folly/experimental/test/BitsBenchmark.cpp       relative  time/iter  iters/s
  96 ============================================================================
  97 benchmarkSet(u16)                                            8.58ns  116.59M
  98 benchmarkSet(i16)                                 88.42%     9.70ns  103.08M
  99 benchmarkSet(u32)                                            8.37ns  119.45M
 100 benchmarkSet(i32)                                 88.23%     9.49ns  105.39M
 101 benchmarkSet(u64)                                            9.23ns  108.34M
 102 benchmarkSet(i64)                                 82.77%    11.15ns   89.68M
 103 ----------------------------------------------------------------------------
 104 benchmarkGet(u16)                                            6.32ns  158.13M
 105 benchmarkGet(i16)                                 80.40%     7.87ns  127.14M
 106 benchmarkGet(u32)                                            6.34ns  157.65M
 107 benchmarkGet(i32)                                 84.61%     7.50ns  133.39M
 108 benchmarkGet(u64)                                            7.32ns  136.58M
 109 benchmarkGet(i64)                                 85.78%     8.53ns  117.16M
 110 ============================================================================
 111 #endif
 112
 113 int main(int argc, char *argv[]) {
 114   gflags::ParseCommandLineFlags(&argc, &argv, true);
 115   folly::runBenchmarks();
 116   return sum.load();
 117 }