folly/test/HashBenchmark.cpp

   1 /*
   2  * Copyright 2016 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/Hash.h>
  18
  19 #include <stdint.h>
  20 #include <deque>
  21 #include <random>
  22 #include <string>
  23 #include <vector>
  24
  25 #include <glog/logging.h>
  26
  27 #include <folly/Benchmark.h>
  28 #include <folly/Format.h>
  29 #include <folly/Preprocessor.h>
  30 #include <folly/portability/GFlags.h>
  31
  32 namespace detail {
  33
  34 std::vector<uint8_t> randomBytes(size_t n) {
  35   std::vector<uint8_t> ret(n);
  36   std::default_random_engine rng(1729);  // Deterministic seed.
  37   std::uniform_int_distribution<uint16_t> dist(0, 255);
  38   std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); });
  39   return ret;
  40 }
  41
  42 std::vector<uint8_t> benchData = randomBytes(1 << 20);  // 1MiB, fits in cache.
  43
  44 template <class Hasher>
  45 void bmHasher(Hasher hasher, size_t k, size_t iters) {
  46   CHECK_LE(k, benchData.size());
  47   for (size_t i = 0, pos = 0; i < iters; ++i, ++pos) {
  48     if (pos == benchData.size() - k + 1) { pos = 0; }
  49     folly::doNotOptimizeAway(hasher(benchData.data() + pos, k));
  50   }
  51 }
  52
  53 template <class Hasher>
  54 void addHashBenchmark(const std::string& name) {
  55   static std::deque<std::string> names;
  56
  57   for (size_t i = 0; i < 16; ++i) {
  58     auto k = size_t(1) << i;
  59     names.emplace_back(folly::sformat("{}: k=2^{}",name, i));
  60     folly::addBenchmark(__FILE__, names.back().c_str(),
  61                         [=] (unsigned iters) {
  62                           Hasher hasher;
  63                           bmHasher(hasher, k, iters);
  64                           return iters;
  65                         });
  66   }
  67
  68   /* Draw line. */
  69   folly::addBenchmark(__FILE__, "-", [] () { return 0; });
  70 }
  71
  72 struct SpookyHashV2 {
  73   uint64_t operator()(const uint8_t* data, size_t size) const {
  74     return folly::hash::SpookyHashV2::Hash64(data, size, 0);
  75   }
  76 };
  77
  78 struct FNV64 {
  79   uint64_t operator()(const uint8_t* data, size_t size) const {
  80     return folly::hash::fnv64_buf(data, size);
  81   }
  82 };
  83
  84 }
  85
  86 int main(int argc, char** argv) {
  87   gflags::ParseCommandLineFlags(&argc, &argv, true);
  88   google::InitGoogleLogging(argv[0]);
  89
  90   std::deque<std::string> names;  // Backing for benchmark names.
  91
  92 #define BENCHMARK_HASH(HASHER) \
  93   detail::addHashBenchmark<detail::HASHER>(FB_STRINGIZE(HASHER));
  94
  95   BENCHMARK_HASH(SpookyHashV2);
  96   BENCHMARK_HASH(FNV64);
  97
  98 #undef BENCHMARK_HASH
  99
 100   folly::runBenchmarks();
 101
 102   return 0;
 103 }
 104
 105 #if 0
 106 Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz
 107 $ hash_benchmark --bm_min_usec=100000
 108 ============================================================================
 109 folly/test/HashBenchmark.cpp                    relative  time/iter  iters/s
 110 ============================================================================
 111 SpookyHashV2: k=2^0                                         11.67ns   85.66M
 112 SpookyHashV2: k=2^1                                         12.49ns   80.07M
 113 SpookyHashV2: k=2^2                                         11.87ns   84.22M
 114 SpookyHashV2: k=2^3                                         12.36ns   80.89M
 115 SpookyHashV2: k=2^4                                         21.47ns   46.58M
 116 SpookyHashV2: k=2^5                                         22.21ns   45.02M
 117 SpookyHashV2: k=2^6                                         31.47ns   31.78M
 118 SpookyHashV2: k=2^7                                         49.86ns   20.05M
 119 SpookyHashV2: k=2^8                                         69.56ns   14.38M
 120 SpookyHashV2: k=2^9                                        102.99ns    9.71M
 121 SpookyHashV2: k=2^10                                       153.72ns    6.51M
 122 SpookyHashV2: k=2^11                                       271.43ns    3.68M
 123 SpookyHashV2: k=2^12                                       498.85ns    2.00M
 124 SpookyHashV2: k=2^13                                       961.55ns    1.04M
 125 SpookyHashV2: k=2^14                                         1.88us  532.57K
 126 SpookyHashV2: k=2^15                                         3.73us  268.42K
 127 --------------------------------------------------------------------------
 128 FNV64: k=2^0                                                 2.67ns  374.83M
 129 FNV64: k=2^1                                                 4.67ns  214.24M
 130 FNV64: k=2^2                                                10.30ns   97.07M
 131 FNV64: k=2^3                                                23.16ns   43.17M
 132 FNV64: k=2^4                                                48.77ns   20.51M
 133 FNV64: k=2^5                                               100.45ns    9.96M
 134 FNV64: k=2^6                                               201.74ns    4.96M
 135 FNV64: k=2^7                                               399.42ns    2.50M
 136 FNV64: k=2^8                                               801.64ns    1.25M
 137 FNV64: k=2^9                                                 1.59us  627.32K
 138 FNV64: k=2^10                                                3.19us  313.51K
 139 FNV64: k=2^11                                                6.38us  156.80K
 140 FNV64: k=2^12                                               12.75us   78.45K
 141 FNV64: k=2^13                                               25.49us   39.23K
 142 FNV64: k=2^14                                               50.98us   19.62K
 143 FNV64: k=2^15                                              101.93us    9.81K
 144 ----------------------------------------------------------------------------
 145 ============================================================================
 146 #endif