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