folly/experimental/test/BitsBenchmark.cpp

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