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.
17 #include <folly/Hash.h>
25 #include <glog/logging.h>
27 #include <folly/Benchmark.h>
28 #include <folly/Format.h>
29 #include <folly/Preprocessor.h>
30 #include <folly/portability/GFlags.h>
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<uint8_t> dist(0, 255);
38 std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); });
42 std::vector<uint8_t> benchData = randomBytes(1 << 20); // 1MiB, fits in cache.
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));
53 template <class Hasher>
54 void addHashBenchmark(const std::string& name) {
55 static std::deque<std::string> names;
57 for (size_t i = 0; i < 16; ++i) {
59 names.emplace_back(folly::sformat("{}: k=2^{}",name, i));
60 folly::addBenchmark(__FILE__, names.back().c_str(),
61 [=] (unsigned iters) {
63 bmHasher(hasher, k, iters);
69 folly::addBenchmark(__FILE__, "-", [] () { return 0; });
73 uint64_t operator()(const uint8_t* data, size_t size) const {
74 return folly::hash::SpookyHashV2::Hash64(data, size, 0);
79 uint64_t operator()(const uint8_t* data, size_t size) const {
80 return folly::hash::fnv64_buf(data, size);
86 int main(int argc, char** argv) {
87 gflags::ParseCommandLineFlags(&argc, &argv, true);
88 google::InitGoogleLogging(argv[0]);
90 std::deque<std::string> names; // Backing for benchmark names.
92 #define BENCHMARK_HASH(HASHER) \
93 detail::addHashBenchmark<detail::HASHER>(FB_STRINGIZE(HASHER));
95 BENCHMARK_HASH(SpookyHashV2);
96 BENCHMARK_HASH(FNV64);
100 folly::runBenchmarks();
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 ============================================================================