2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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>
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); });
41 std::vector<uint8_t> benchData = randomBytes(1 << 20); // 1MiB, fits in cache.
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));
52 template <class Hasher>
53 void addHashBenchmark(const std::string& name) {
54 static std::deque<std::string> names;
56 for (size_t i = 0; i < 16; ++i) {
58 names.emplace_back(folly::sformat("{}: k=2^{}",name, i));
59 folly::addBenchmark(__FILE__, names.back().c_str(),
60 [=] (unsigned iters) {
62 bmHasher(hasher, k, iters);
68 folly::addBenchmark(__FILE__, "-", [] () { return 0; });
72 uint64_t operator()(const uint8_t* data, size_t size) const {
73 return folly::hash::SpookyHashV2::Hash64(data, size, 0);
78 uint64_t operator()(const uint8_t* data, size_t size) const {
79 return folly::hash::fnv64_buf(data, size);
85 int main(int argc, char** argv) {
86 gflags::ParseCommandLineFlags(&argc, &argv, true);
87 google::InitGoogleLogging(argv[0]);
89 std::deque<std::string> names; // Backing for benchmark names.
91 #define BENCHMARK_HASH(HASHER) \
92 detail::addHashBenchmark<detail::HASHER>(FB_STRINGIZE(HASHER));
94 BENCHMARK_HASH(SpookyHashV2);
95 BENCHMARK_HASH(FNV64);
99 folly::runBenchmarks();
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 ============================================================================