1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <string>
16 #include <type_traits>
17 #include <typeindex>
18 #include <utility>
19 #include <vector>
20
21 #include "absl/base/attributes.h"
22 #include "absl/hash/hash.h"
23 #include "absl/random/random.h"
24 #include "absl/strings/cord.h"
25 #include "absl/strings/cord_test_helpers.h"
26 #include "absl/strings/string_view.h"
27 #include "benchmark/benchmark.h"
28
29 namespace {
30
31 using absl::Hash;
32
33 template <template <typename> class H, typename T>
RunBenchmark(benchmark::State & state,T value)34 void RunBenchmark(benchmark::State& state, T value) {
35 H<T> h;
36 for (auto _ : state) {
37 benchmark::DoNotOptimize(value);
38 benchmark::DoNotOptimize(h(value));
39 }
40 }
41
42 } // namespace
43
44 template <typename T>
45 using AbslHash = absl::Hash<T>;
46
47 class TypeErasedInterface {
48 public:
49 virtual ~TypeErasedInterface() = default;
50
51 template <typename H>
AbslHashValue(H state,const TypeErasedInterface & wrapper)52 friend H AbslHashValue(H state, const TypeErasedInterface& wrapper) {
53 state = H::combine(std::move(state), std::type_index(typeid(wrapper)));
54 wrapper.HashValue(absl::HashState::Create(&state));
55 return state;
56 }
57
58 private:
59 virtual void HashValue(absl::HashState state) const = 0;
60 };
61
62 template <typename T>
63 struct TypeErasedAbslHash {
64 class Wrapper : public TypeErasedInterface {
65 public:
Wrapper(const T & value)66 explicit Wrapper(const T& value) : value_(value) {}
67
68 private:
HashValue(absl::HashState state) const69 void HashValue(absl::HashState state) const override {
70 absl::HashState::combine(std::move(state), value_);
71 }
72
73 const T& value_;
74 };
75
operator ()TypeErasedAbslHash76 size_t operator()(const T& value) {
77 return absl::Hash<Wrapper>{}(Wrapper(value));
78 }
79 };
80
81 template <typename FuncType>
ODRUseFunction(FuncType * ptr)82 inline FuncType* ODRUseFunction(FuncType* ptr) {
83 volatile FuncType* dummy = ptr;
84 return dummy;
85 }
86
FlatCord(size_t size)87 absl::Cord FlatCord(size_t size) {
88 absl::Cord result(std::string(size, 'a'));
89 result.Flatten();
90 return result;
91 }
92
FragmentedCord(size_t size)93 absl::Cord FragmentedCord(size_t size) {
94 const size_t orig_size = size;
95 std::vector<std::string> chunks;
96 size_t chunk_size = std::max<size_t>(1, size / 10);
97 while (size > chunk_size) {
98 chunks.push_back(std::string(chunk_size, 'a'));
99 size -= chunk_size;
100 }
101 if (size > 0) {
102 chunks.push_back(std::string(size, 'a'));
103 }
104 absl::Cord result = absl::MakeFragmentedCord(chunks);
105 (void) orig_size;
106 assert(result.size() == orig_size);
107 return result;
108 }
109
110 // Generates a benchmark and a codegen method for the provided types. The
111 // codegen method provides a well known entrypoint for dumping assembly.
112 #define MAKE_BENCHMARK(hash, name, ...) \
113 namespace { \
114 void BM_##hash##_##name(benchmark::State& state) { \
115 RunBenchmark<hash>(state, __VA_ARGS__); \
116 } \
117 BENCHMARK(BM_##hash##_##name); \
118 } \
119 size_t Codegen##hash##name(const decltype(__VA_ARGS__)& arg); \
120 size_t Codegen##hash##name(const decltype(__VA_ARGS__)& arg) { \
121 return hash<decltype(__VA_ARGS__)>{}(arg); \
122 } \
123 bool absl_hash_test_odr_use##hash##name = \
124 ODRUseFunction(&Codegen##hash##name);
125
126 MAKE_BENCHMARK(AbslHash, Int32, int32_t{});
127 MAKE_BENCHMARK(AbslHash, Int64, int64_t{});
128 MAKE_BENCHMARK(AbslHash, Double, 1.2);
129 MAKE_BENCHMARK(AbslHash, DoubleZero, 0.0);
130 MAKE_BENCHMARK(AbslHash, PairInt32Int32, std::pair<int32_t, int32_t>{});
131 MAKE_BENCHMARK(AbslHash, PairInt64Int64, std::pair<int64_t, int64_t>{});
132 MAKE_BENCHMARK(AbslHash, TupleInt32BoolInt64,
133 std::tuple<int32_t, bool, int64_t>{});
134 MAKE_BENCHMARK(AbslHash, String_0, std::string());
135 MAKE_BENCHMARK(AbslHash, String_10, std::string(10, 'a'));
136 MAKE_BENCHMARK(AbslHash, String_30, std::string(30, 'a'));
137 MAKE_BENCHMARK(AbslHash, String_90, std::string(90, 'a'));
138 MAKE_BENCHMARK(AbslHash, String_200, std::string(200, 'a'));
139 MAKE_BENCHMARK(AbslHash, String_5000, std::string(5000, 'a'));
140 MAKE_BENCHMARK(AbslHash, Cord_Flat_0, absl::Cord());
141 MAKE_BENCHMARK(AbslHash, Cord_Flat_10, FlatCord(10));
142 MAKE_BENCHMARK(AbslHash, Cord_Flat_30, FlatCord(30));
143 MAKE_BENCHMARK(AbslHash, Cord_Flat_90, FlatCord(90));
144 MAKE_BENCHMARK(AbslHash, Cord_Flat_200, FlatCord(200));
145 MAKE_BENCHMARK(AbslHash, Cord_Flat_5000, FlatCord(5000));
146 MAKE_BENCHMARK(AbslHash, Cord_Fragmented_200, FragmentedCord(200));
147 MAKE_BENCHMARK(AbslHash, Cord_Fragmented_5000, FragmentedCord(5000));
148 MAKE_BENCHMARK(AbslHash, VectorInt64_10, std::vector<int64_t>(10));
149 MAKE_BENCHMARK(AbslHash, VectorInt64_100, std::vector<int64_t>(100));
150 MAKE_BENCHMARK(AbslHash, VectorDouble_10, std::vector<double>(10, 1.1));
151 MAKE_BENCHMARK(AbslHash, VectorDouble_100, std::vector<double>(100, 1.1));
152 MAKE_BENCHMARK(AbslHash, PairStringString_0,
153 std::make_pair(std::string(), std::string()));
154 MAKE_BENCHMARK(AbslHash, PairStringString_10,
155 std::make_pair(std::string(10, 'a'), std::string(10, 'b')));
156 MAKE_BENCHMARK(AbslHash, PairStringString_30,
157 std::make_pair(std::string(30, 'a'), std::string(30, 'b')));
158 MAKE_BENCHMARK(AbslHash, PairStringString_90,
159 std::make_pair(std::string(90, 'a'), std::string(90, 'b')));
160 MAKE_BENCHMARK(AbslHash, PairStringString_200,
161 std::make_pair(std::string(200, 'a'), std::string(200, 'b')));
162 MAKE_BENCHMARK(AbslHash, PairStringString_5000,
163 std::make_pair(std::string(5000, 'a'), std::string(5000, 'b')));
164
165 MAKE_BENCHMARK(TypeErasedAbslHash, Int32, int32_t{});
166 MAKE_BENCHMARK(TypeErasedAbslHash, Int64, int64_t{});
167 MAKE_BENCHMARK(TypeErasedAbslHash, PairInt32Int32,
168 std::pair<int32_t, int32_t>{});
169 MAKE_BENCHMARK(TypeErasedAbslHash, PairInt64Int64,
170 std::pair<int64_t, int64_t>{});
171 MAKE_BENCHMARK(TypeErasedAbslHash, TupleInt32BoolInt64,
172 std::tuple<int32_t, bool, int64_t>{});
173 MAKE_BENCHMARK(TypeErasedAbslHash, String_0, std::string());
174 MAKE_BENCHMARK(TypeErasedAbslHash, String_10, std::string(10, 'a'));
175 MAKE_BENCHMARK(TypeErasedAbslHash, String_30, std::string(30, 'a'));
176 MAKE_BENCHMARK(TypeErasedAbslHash, String_90, std::string(90, 'a'));
177 MAKE_BENCHMARK(TypeErasedAbslHash, String_200, std::string(200, 'a'));
178 MAKE_BENCHMARK(TypeErasedAbslHash, String_5000, std::string(5000, 'a'));
179 MAKE_BENCHMARK(TypeErasedAbslHash, VectorDouble_10,
180 std::vector<double>(10, 1.1));
181 MAKE_BENCHMARK(TypeErasedAbslHash, VectorDouble_100,
182 std::vector<double>(100, 1.1));
183
184 // The latency benchmark attempts to model the speed of the hash function in
185 // production. When a hash function is used for hashtable lookups it is rarely
186 // used to hash N items in a tight loop nor on constant sized strings. Instead,
187 // after hashing there is a potential equality test plus a (usually) large
188 // amount of user code. To simulate this effectively we introduce a data
189 // dependency between elements we hash by using the hash of the Nth element as
190 // the selector of the N+1th element to hash. This isolates the hash function
191 // code much like in production. As a bonus we use the hash to generate strings
192 // of size [1,N] (instead of fixed N) to disable perfect branch predictions in
193 // hash function implementations.
194 namespace {
195 // 16kb fits in L1 cache of most CPUs we care about. Keeping memory latency low
196 // will allow us to attribute most time to CPU which means more accurate
197 // measurements.
198 static constexpr size_t kEntropySize = 16 << 10;
199 static char entropy[kEntropySize + 1024];
__anonb716e6d10302null200 ABSL_ATTRIBUTE_UNUSED static const bool kInitialized = [] {
201 absl::BitGen gen;
202 static_assert(sizeof(entropy) % sizeof(uint64_t) == 0, "");
203 for (int i = 0; i != sizeof(entropy); i += sizeof(uint64_t)) {
204 auto rand = absl::Uniform<uint64_t>(gen);
205 memcpy(&entropy[i], &rand, sizeof(uint64_t));
206 }
207 return true;
208 }();
209 } // namespace
210
211 template <class T>
212 struct PodRand {
213 static_assert(std::is_pod<T>::value, "");
214 static_assert(kEntropySize + sizeof(T) < sizeof(entropy), "");
215
GetPodRand216 T Get(size_t i) const {
217 T v;
218 memcpy(&v, &entropy[i % kEntropySize], sizeof(T));
219 return v;
220 }
221 };
222
223 template <size_t N>
224 struct StringRand {
225 static_assert(kEntropySize + N < sizeof(entropy), "");
226
GetStringRand227 absl::string_view Get(size_t i) const {
228 // This has a small bias towards small numbers. Because max N is ~200 this
229 // is very small and prefer to be very fast instead of absolutely accurate.
230 // Also we pass N = 2^K+1 so that mod reduces to a bitand.
231 size_t s = (i % (N - 1)) + 1;
232 return {&entropy[i % kEntropySize], s};
233 }
234 };
235
236 #define MAKE_LATENCY_BENCHMARK(hash, name, ...) \
237 namespace { \
238 void BM_latency_##hash##_##name(benchmark::State& state) { \
239 __VA_ARGS__ r; \
240 hash<decltype(r.Get(0))> h; \
241 size_t i = 871401241; \
242 for (auto _ : state) { \
243 benchmark::DoNotOptimize(i = h(r.Get(i))); \
244 } \
245 } \
246 BENCHMARK(BM_latency_##hash##_##name); \
247 } // namespace
248
249 MAKE_LATENCY_BENCHMARK(AbslHash, Int32, PodRand<int32_t>);
250 MAKE_LATENCY_BENCHMARK(AbslHash, Int64, PodRand<int64_t>);
251 MAKE_LATENCY_BENCHMARK(AbslHash, String9, StringRand<9>);
252 MAKE_LATENCY_BENCHMARK(AbslHash, String33, StringRand<33>);
253 MAKE_LATENCY_BENCHMARK(AbslHash, String65, StringRand<65>);
254 MAKE_LATENCY_BENCHMARK(AbslHash, String257, StringRand<257>);
255