From 589b6f75808cccac7d56abed56ed062a31fedb4b Mon Sep 17 00:00:00 2001 From: Giuseppe Ottaviano Date: Mon, 14 Sep 2015 14:07:26 -0700 Subject: [PATCH] Add benchmarks for SpookyHashV2 and constify SpookyHashV2::Final Summary: `Final` is idempotent, no reason for it not to be `const`. Checked with a benchmark that the new version does not affect performance. Reviewed By: @yfeldblum Differential Revision: D2397377 --- folly/SpookyHashV2.cpp | 6 +- folly/SpookyHashV2.h | 12 +-- folly/test/HashBenchmark.cpp | 145 +++++++++++++++++++++++++++++++++++ 3 files changed, 155 insertions(+), 8 deletions(-) create mode 100644 folly/test/HashBenchmark.cpp diff --git a/folly/SpookyHashV2.cpp b/folly/SpookyHashV2.cpp index 45f640ab..e2f665f2 100644 --- a/folly/SpookyHashV2.cpp +++ b/folly/SpookyHashV2.cpp @@ -323,7 +323,7 @@ void SpookyHashV2::Update(const void *message, size_t length) // report the hash for the concatenation of all message fragments so far -void SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2) +void SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2) const { // init the variables if (m_length < sc_bufSize) @@ -334,7 +334,9 @@ void SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2) return; } - const uint64_t *data = (const uint64_t *)m_data; + uint64_t buf[2*sc_numVars]; + memcpy(buf, m_data, sizeof(buf)); + uint64_t *data = buf; uint8_t remainder = m_remainder; uint64_t h0 = m_state[0]; diff --git a/folly/SpookyHashV2.h b/folly/SpookyHashV2.h index f32d8fe5..4c6f7f01 100644 --- a/folly/SpookyHashV2.h +++ b/folly/SpookyHashV2.h @@ -114,8 +114,8 @@ public: // all the pieces concatenated into one message. // void Final( - uint64_t *hash1, // out only: first 64 bits of hash value. - uint64_t *hash2); // out only: second 64 bits of hash value. + uint64_t *hash1, // out only: first 64 bits of hash value. + uint64_t *hash2) const; // out only: second 64 bits of hash value. // // left rotate a 64-bit value by k bytes @@ -282,13 +282,13 @@ private: uint64_t *hash2); // in/out: in the seed, out the hash value // number of uint64_t's in internal state - static const size_t sc_numVars = 12; + static constexpr size_t sc_numVars = 12; // size of the internal state - static const size_t sc_blockSize = sc_numVars*8; + static constexpr size_t sc_blockSize = sc_numVars*8; // size of buffer of unhashed data, in bytes - static const size_t sc_bufSize = 2*sc_blockSize; + static constexpr size_t sc_bufSize = 2*sc_blockSize; // // sc_const: a constant which: @@ -297,7 +297,7 @@ private: // * is a not-very-regular mix of 1's and 0's // * does not need any other special mathematical properties // - static const uint64_t sc_const = 0xdeadbeefdeadbeefLL; + static constexpr uint64_t sc_const = 0xdeadbeefdeadbeefLL; uint64_t m_data[2*sc_numVars]; // unhashed data, for partial messages uint64_t m_state[sc_numVars]; // internal state of the hash diff --git a/folly/test/HashBenchmark.cpp b/folly/test/HashBenchmark.cpp new file mode 100644 index 00000000..5cac80ad --- /dev/null +++ b/folly/test/HashBenchmark.cpp @@ -0,0 +1,145 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +namespace detail { + +std::vector randomBytes(size_t n) { + std::vector ret(n); + std::default_random_engine rng(1729); // Deterministic seed. + std::uniform_int_distribution dist(0, 255); + std::generate(ret.begin(), ret.end(), [&] () { return dist(rng); }); + return ret; +} + +std::vector benchData = randomBytes(1 << 20); // 1MiB, fits in cache. + +template +void bmHasher(Hasher hasher, size_t k, size_t iters) { + CHECK_LE(k, benchData.size()); + for (size_t i = 0, pos = 0; i < iters; ++i, ++pos) { + if (pos == benchData.size() - k + 1) { pos = 0; } + folly::doNotOptimizeAway(hasher(benchData.data() + pos, k)); + } +} + +template +void addHashBenchmark(const std::string& name) { + static std::deque names; + + for (size_t i = 0; i < 16; ++i) { + size_t k = 1 << i; + names.emplace_back(folly::sformat("{}: k=2^{}",name, i)); + folly::addBenchmark(__FILE__, names.back().c_str(), + [=] (unsigned iters) { + Hasher hasher; + bmHasher(hasher, k, iters); + return iters; + }); + } + + /* Draw line. */ + folly::addBenchmark(__FILE__, "-", [] () { return 0; }); +} + +struct SpookyHashV2 { + uint64_t operator()(const uint8_t* data, size_t size) const { + return folly::hash::SpookyHashV2::Hash64(data, size, 0); + } +}; + +struct FNV64 { + uint64_t operator()(const uint8_t* data, size_t size) const { + return folly::hash::fnv64_buf(data, size); + } +}; + +} + +int main(int argc, char** argv) { + gflags::ParseCommandLineFlags(&argc, &argv, true); + google::InitGoogleLogging(argv[0]); + + std::deque names; // Backing for benchmark names. + +#define BENCHMARK_HASH(HASHER) \ + detail::addHashBenchmark(FB_STRINGIZE(HASHER)); + + BENCHMARK_HASH(SpookyHashV2); + BENCHMARK_HASH(FNV64); + +#undef BENCHMARK_HASH + + folly::runBenchmarks(); + + return 0; +} + +#if 0 +Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz +$ hash_benchmark --bm_min_usec=100000 +============================================================================ +folly/test/HashBenchmark.cpp relative time/iter iters/s +============================================================================ +SpookyHashV2: k=2^0 11.67ns 85.66M +SpookyHashV2: k=2^1 12.49ns 80.07M +SpookyHashV2: k=2^2 11.87ns 84.22M +SpookyHashV2: k=2^3 12.36ns 80.89M +SpookyHashV2: k=2^4 21.47ns 46.58M +SpookyHashV2: k=2^5 22.21ns 45.02M +SpookyHashV2: k=2^6 31.47ns 31.78M +SpookyHashV2: k=2^7 49.86ns 20.05M +SpookyHashV2: k=2^8 69.56ns 14.38M +SpookyHashV2: k=2^9 102.99ns 9.71M +SpookyHashV2: k=2^10 153.72ns 6.51M +SpookyHashV2: k=2^11 271.43ns 3.68M +SpookyHashV2: k=2^12 498.85ns 2.00M +SpookyHashV2: k=2^13 961.55ns 1.04M +SpookyHashV2: k=2^14 1.88us 532.57K +SpookyHashV2: k=2^15 3.73us 268.42K +-------------------------------------------------------------------------- +FNV64: k=2^0 2.67ns 374.83M +FNV64: k=2^1 4.67ns 214.24M +FNV64: k=2^2 10.30ns 97.07M +FNV64: k=2^3 23.16ns 43.17M +FNV64: k=2^4 48.77ns 20.51M +FNV64: k=2^5 100.45ns 9.96M +FNV64: k=2^6 201.74ns 4.96M +FNV64: k=2^7 399.42ns 2.50M +FNV64: k=2^8 801.64ns 1.25M +FNV64: k=2^9 1.59us 627.32K +FNV64: k=2^10 3.19us 313.51K +FNV64: k=2^11 6.38us 156.80K +FNV64: k=2^12 12.75us 78.45K +FNV64: k=2^13 25.49us 39.23K +FNV64: k=2^14 50.98us 19.62K +FNV64: k=2^15 101.93us 9.81K +---------------------------------------------------------------------------- +============================================================================ +#endif -- 2.34.1