/root/doris/be/src/util/hash_util.hpp
Line | Count | Source (jump to first uncovered line) |
1 | | // Licensed to the Apache Software Foundation (ASF) under one |
2 | | // or more contributor license agreements. See the NOTICE file |
3 | | // distributed with this work for additional information |
4 | | // regarding copyright ownership. The ASF licenses this file |
5 | | // to you under the Apache License, Version 2.0 (the |
6 | | // "License"); you may not use this file except in compliance |
7 | | // with the License. You may obtain a copy of the License at |
8 | | // |
9 | | // http://www.apache.org/licenses/LICENSE-2.0 |
10 | | // |
11 | | // Unless required by applicable law or agreed to in writing, |
12 | | // software distributed under the License is distributed on an |
13 | | // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
14 | | // KIND, either express or implied. See the License for the |
15 | | // specific language governing permissions and limitations |
16 | | // under the License. |
17 | | // This file is copied from |
18 | | // https://github.com/apache/impala/blob/branch-2.9.0/be/src/util/hash-util.h |
19 | | // and modified by Doris |
20 | | |
21 | | #pragma once |
22 | | |
23 | | #include <gen_cpp/Types_types.h> |
24 | | #include <xxh3.h> |
25 | | #include <zlib.h> |
26 | | |
27 | | #include <functional> |
28 | | |
29 | | #include "common/compiler_util.h" // IWYU pragma: keep |
30 | | #include "gutil/hash/city.h" |
31 | | #include "runtime/define_primitive_type.h" |
32 | | #include "util/cpu_info.h" |
33 | | #include "util/murmur_hash3.h" |
34 | | #include "util/sse_util.hpp" |
35 | | |
36 | | namespace doris { |
37 | | |
38 | | // Utility class to compute hash values. |
39 | | class HashUtil { |
40 | | public: |
41 | 3.65M | static uint32_t zlib_crc_hash(const void* data, uint32_t bytes, uint32_t hash) { |
42 | 3.65M | return crc32(hash, (const unsigned char*)data, bytes); |
43 | 3.65M | } |
44 | | |
45 | | static uint32_t zlib_crc_hash_null(uint32_t hash) { |
46 | | // null is treat as 0 when hash |
47 | | static const int INT_VALUE = 0; |
48 | | return crc32(hash, (const unsigned char*)(&INT_VALUE), 4); |
49 | | } |
50 | | |
51 | | #if defined(__SSE4_2__) || defined(__aarch64__) |
52 | | // Compute the Crc32 hash for data using SSE4 instructions. The input hash parameter is |
53 | | // the current hash/seed value. |
54 | | // This should only be called if SSE is supported. |
55 | | // This is ~4x faster than Fnv/Boost Hash. |
56 | | // NOTE: DO NOT use this method for checksum! This does not generate the standard CRC32 checksum! |
57 | | // For checksum, use CRC-32C algorithm from crc32c.h |
58 | | // NOTE: Any changes made to this function need to be reflected in Codegen::GetHashFn. |
59 | | // TODO: crc32 hashes with different seeds do not result in different hash functions. |
60 | | // The resulting hashes are correlated. |
61 | 15.4k | static uint32_t crc_hash(const void* data, uint32_t bytes, uint32_t hash) { |
62 | 15.4k | if (!CpuInfo::is_supported(CpuInfo::SSE4_2)) { |
63 | 0 | return zlib_crc_hash(data, bytes, hash); |
64 | 0 | } |
65 | 15.4k | uint32_t words = bytes / sizeof(uint32_t); |
66 | 15.4k | bytes = bytes % sizeof(uint32_t); |
67 | | |
68 | 15.4k | const uint32_t* p = reinterpret_cast<const uint32_t*>(data); |
69 | | |
70 | 46.4k | while (words--) { |
71 | 31.0k | hash = _mm_crc32_u32(hash, *p); |
72 | 31.0k | ++p; |
73 | 31.0k | } |
74 | | |
75 | 15.4k | const uint8_t* s = reinterpret_cast<const uint8_t*>(p); |
76 | | |
77 | 15.5k | while (bytes--) { |
78 | 70 | hash = _mm_crc32_u8(hash, *s); |
79 | 70 | ++s; |
80 | 70 | } |
81 | | |
82 | | // The lower half of the CRC hash has has poor uniformity, so swap the halves |
83 | | // for anyone who only uses the first several bits of the hash. |
84 | 15.4k | hash = (hash << 16) | (hash >> 16); |
85 | 15.4k | return hash; |
86 | 15.4k | } |
87 | | |
88 | 0 | static uint64_t crc_hash64(const void* data, uint32_t bytes, uint64_t hash) { |
89 | 0 | uint32_t words = bytes / sizeof(uint32_t); |
90 | 0 | bytes = bytes % sizeof(uint32_t); |
91 | 0 |
|
92 | 0 | uint32_t h1 = hash >> 32; |
93 | 0 | uint32_t h2 = (hash << 32) >> 32; |
94 | 0 |
|
95 | 0 | const uint32_t* p = reinterpret_cast<const uint32_t*>(data); |
96 | 0 | while (words--) { |
97 | 0 | (words & 1) ? (h1 = _mm_crc32_u32(h1, *p)) : (h2 = _mm_crc32_u32(h2, *p)); |
98 | 0 | ++p; |
99 | 0 | } |
100 | 0 |
|
101 | 0 | const uint8_t* s = reinterpret_cast<const uint8_t*>(p); |
102 | 0 | while (bytes--) { |
103 | 0 | (bytes & 1) ? (h1 = _mm_crc32_u8(h1, *s)) : (h2 = _mm_crc32_u8(h2, *s)); |
104 | 0 | ++s; |
105 | 0 | } |
106 | 0 | union { |
107 | 0 | uint64_t u64; |
108 | 0 | uint32_t u32[2]; |
109 | 0 | } converter; |
110 | 0 | converter.u64 = hash; |
111 | 0 |
|
112 | 0 | h1 = (h1 << 16) | (h1 >> 16); |
113 | 0 | h2 = (h2 << 16) | (h2 >> 16); |
114 | 0 | converter.u32[0] = h1; |
115 | 0 | converter.u32[1] = h2; |
116 | 0 |
|
117 | 0 | return converter.u64; |
118 | 0 | } |
119 | | #else |
120 | | static uint32_t crc_hash(const void* data, uint32_t bytes, uint32_t hash) { |
121 | | return zlib_crc_hash(data, bytes, hash); |
122 | | } |
123 | | #endif |
124 | | |
125 | | // refer to https://github.com/apache/commons-codec/blob/master/src/main/java/org/apache/commons/codec/digest/MurmurHash3.java |
126 | | static const uint32_t MURMUR3_32_SEED = 104729; |
127 | | |
128 | | // modify from https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp |
129 | 20 | static uint32_t murmur_hash3_32(const void* key, int64_t len, uint32_t seed) { |
130 | 20 | uint32_t out = 0; |
131 | 20 | murmur_hash3_x86_32(key, len, seed, &out); |
132 | 20 | return out; |
133 | 20 | } |
134 | | |
135 | | static const int MURMUR_R = 47; |
136 | | |
137 | | // Murmur2 hash implementation returning 64-bit hashes. |
138 | 0 | static uint64_t murmur_hash2_64(const void* input, int len, uint64_t seed) { |
139 | 0 | uint64_t h = seed ^ (len * MURMUR_PRIME); |
140 | 0 |
|
141 | 0 | const uint64_t* data = reinterpret_cast<const uint64_t*>(input); |
142 | 0 | const uint64_t* end = data + (len / sizeof(uint64_t)); |
143 | 0 |
|
144 | 0 | while (data != end) { |
145 | 0 | uint64_t k = *data++; |
146 | 0 | k *= MURMUR_PRIME; |
147 | 0 | k ^= k >> MURMUR_R; |
148 | 0 | k *= MURMUR_PRIME; |
149 | 0 | h ^= k; |
150 | 0 | h *= MURMUR_PRIME; |
151 | 0 | } |
152 | 0 |
|
153 | 0 | const uint8_t* data2 = reinterpret_cast<const uint8_t*>(data); |
154 | 0 | switch (len & 7) { |
155 | 0 | case 7: |
156 | 0 | h ^= uint64_t(data2[6]) << 48; |
157 | 0 | [[fallthrough]]; |
158 | 0 | case 6: |
159 | 0 | h ^= uint64_t(data2[5]) << 40; |
160 | 0 | [[fallthrough]]; |
161 | 0 | case 5: |
162 | 0 | h ^= uint64_t(data2[4]) << 32; |
163 | 0 | [[fallthrough]]; |
164 | 0 | case 4: |
165 | 0 | h ^= uint64_t(data2[3]) << 24; |
166 | 0 | [[fallthrough]]; |
167 | 0 | case 3: |
168 | 0 | h ^= uint64_t(data2[2]) << 16; |
169 | 0 | [[fallthrough]]; |
170 | 0 | case 2: |
171 | 0 | h ^= uint64_t(data2[1]) << 8; |
172 | 0 | [[fallthrough]]; |
173 | 0 | case 1: |
174 | 0 | h ^= uint64_t(data2[0]); |
175 | 0 | h *= MURMUR_PRIME; |
176 | 0 | } |
177 | 0 |
|
178 | 0 | h ^= h >> MURMUR_R; |
179 | 0 | h *= MURMUR_PRIME; |
180 | 0 | h ^= h >> MURMUR_R; |
181 | 0 | return h; |
182 | 0 | } |
183 | | |
184 | | // default values recommended by http://isthe.com/chongo/tech/comp/fnv/ |
185 | | static const uint32_t FNV_PRIME = 0x01000193; // 16777619 |
186 | | static const uint32_t FNV_SEED = 0x811C9DC5; // 2166136261 |
187 | | static const uint64_t FNV64_PRIME = 1099511628211UL; |
188 | | static const uint64_t FNV64_SEED = 14695981039346656037UL; |
189 | | static const uint64_t MURMUR_PRIME = 0xc6a4a7935bd1e995ULL; |
190 | | static const uint32_t MURMUR_SEED = 0xadc83b19ULL; |
191 | | // Implementation of the Fowler–Noll–Vo hash function. This is not as performant |
192 | | // as boost's hash on int types (2x slower) but has bit entropy. |
193 | | // For ints, boost just returns the value of the int which can be pathological. |
194 | | // For example, if the data is <1000, 2000, 3000, 4000, ..> and then the mod of 1000 |
195 | | // is taken on the hash, all values will collide to the same bucket. |
196 | | // For string values, Fnv is slightly faster than boost. |
197 | 0 | static uint32_t fnv_hash(const void* data, uint32_t bytes, uint32_t hash) { |
198 | 0 | const uint8_t* ptr = reinterpret_cast<const uint8_t*>(data); |
199 | |
|
200 | 0 | while (bytes--) { |
201 | 0 | hash = (*ptr ^ hash) * FNV_PRIME; |
202 | 0 | ++ptr; |
203 | 0 | } |
204 | |
|
205 | 0 | return hash; |
206 | 0 | } |
207 | | |
208 | 0 | static uint64_t fnv_hash64(const void* data, uint32_t bytes, uint64_t hash) { |
209 | 0 | const uint8_t* ptr = reinterpret_cast<const uint8_t*>(data); |
210 | 0 |
|
211 | 0 | while (bytes--) { |
212 | 0 | hash = (*ptr ^ hash) * FNV64_PRIME; |
213 | 0 | ++ptr; |
214 | 0 | } |
215 | 0 |
|
216 | 0 | return hash; |
217 | 0 | } |
218 | | |
219 | | // Our hash function is MurmurHash2, 64 bit version. |
220 | | // It was modified in order to provide the same result in |
221 | | // big and little endian archs (endian neutral). |
222 | 67.8k | static uint64_t murmur_hash64A(const void* key, int64_t len, unsigned int seed) { |
223 | 67.8k | const uint64_t m = MURMUR_PRIME; |
224 | 67.8k | const int r = 47; |
225 | 67.8k | uint64_t h = seed ^ (len * m); |
226 | 67.8k | const uint8_t* data = (const uint8_t*)key; |
227 | 67.8k | const uint8_t* end = data + (len - (len & 7)); |
228 | | |
229 | 135k | while (data != end) { |
230 | 67.8k | uint64_t k; |
231 | | #if (BYTE_ORDER == BIG_ENDIAN) |
232 | | k = (uint64_t)data[0]; |
233 | | k |= (uint64_t)data[1] << 8; |
234 | | k |= (uint64_t)data[2] << 16; |
235 | | k |= (uint64_t)data[3] << 24; |
236 | | k |= (uint64_t)data[4] << 32; |
237 | | k |= (uint64_t)data[5] << 40; |
238 | | k |= (uint64_t)data[6] << 48; |
239 | | k |= (uint64_t)data[7] << 56; |
240 | | #else |
241 | 67.8k | k = *((uint64_t*)data); |
242 | 67.8k | #endif |
243 | | |
244 | 67.8k | k *= m; |
245 | 67.8k | k ^= k >> r; |
246 | 67.8k | k *= m; |
247 | 67.8k | h ^= k; |
248 | 67.8k | h *= m; |
249 | 67.8k | data += 8; |
250 | 67.8k | } |
251 | | |
252 | 67.8k | switch (len & 7) { |
253 | 0 | case 7: |
254 | 0 | h ^= (uint64_t)data[6] << 48; |
255 | 0 | [[fallthrough]]; |
256 | 0 | case 6: |
257 | 0 | h ^= (uint64_t)data[5] << 40; |
258 | 0 | [[fallthrough]]; |
259 | 0 | case 5: |
260 | 0 | h ^= (uint64_t)data[4] << 32; |
261 | 0 | [[fallthrough]]; |
262 | 3 | case 4: |
263 | 3 | h ^= (uint64_t)data[3] << 24; |
264 | 3 | [[fallthrough]]; |
265 | 3 | case 3: |
266 | 3 | h ^= (uint64_t)data[2] << 16; |
267 | 3 | [[fallthrough]]; |
268 | 3 | case 2: |
269 | 3 | h ^= (uint64_t)data[1] << 8; |
270 | 3 | [[fallthrough]]; |
271 | 6 | case 1: |
272 | 6 | h ^= (uint64_t)data[0]; |
273 | 6 | h *= m; |
274 | 67.8k | } |
275 | | |
276 | 67.8k | h ^= h >> r; |
277 | 67.8k | h *= m; |
278 | 67.8k | h ^= h >> r; |
279 | 67.8k | return h; |
280 | 67.8k | } |
281 | | |
282 | | // Computes the hash value for data. Will call either CrcHash or FnvHash |
283 | | // depending on hardware capabilities. |
284 | | // Seed values for different steps of the query execution should use different seeds |
285 | | // to prevent accidental key collisions. (See IMPALA-219 for more details). |
286 | 15.4k | static uint32_t hash(const void* data, uint32_t bytes, uint32_t seed) { |
287 | 15.4k | #ifdef __SSE4_2__ |
288 | | |
289 | 15.4k | if (LIKELY(CpuInfo::is_supported(CpuInfo::SSE4_2))) { |
290 | 15.4k | return crc_hash(data, bytes, seed); |
291 | 15.4k | } else { |
292 | 0 | return fnv_hash(data, bytes, seed); |
293 | 0 | } |
294 | | |
295 | | #else |
296 | | return fnv_hash(data, bytes, seed); |
297 | | #endif |
298 | 15.4k | } |
299 | | |
300 | 23.2k | static uint64_t hash64(const void* data, uint64_t bytes, uint64_t seed) { |
301 | | #ifdef _SSE4_2_ |
302 | | if (LIKELY(CpuInfo::is_supported(CpuInfo::SSE4_2))) { |
303 | | return crc_hash64(data, bytes, seed); |
304 | | |
305 | | } else { |
306 | | uint64_t hash = 0; |
307 | | murmur_hash3_x64_64(data, bytes, seed, &hash); |
308 | | return hash; |
309 | | } |
310 | | #else |
311 | 23.2k | uint64_t hash = 0; |
312 | 23.2k | murmur_hash3_x64_64(data, bytes, seed, &hash); |
313 | 23.2k | return hash; |
314 | 23.2k | #endif |
315 | 23.2k | } |
316 | | // hash_combine is the same with boost hash_combine, |
317 | | // except replace boost::hash with std::hash |
318 | | template <class T> |
319 | | static inline void hash_combine(std::size_t& seed, const T& v) { |
320 | | std::hash<T> hasher; |
321 | | seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); |
322 | | } |
323 | | |
324 | | #if defined(__clang__) |
325 | | #pragma clang diagnostic push |
326 | | #pragma clang diagnostic ignored "-Wused-but-marked-unused" |
327 | | #endif |
328 | | // xxHash function for a byte array. For convenience, a 64-bit seed is also |
329 | | // hashed into the result. The mapping may change from time to time. |
330 | | static xxh_u32 xxHash32WithSeed(const char* s, size_t len, xxh_u32 seed) { |
331 | | return XXH32(s, len, seed); |
332 | | } |
333 | | |
334 | | // same to the up function, just for null value |
335 | 0 | static xxh_u32 xxHash32NullWithSeed(xxh_u32 seed) { |
336 | 0 | static const int INT_VALUE = 0; |
337 | 0 | return XXH32(reinterpret_cast<const char*>(&INT_VALUE), sizeof(int), seed); |
338 | 0 | } |
339 | | |
340 | 18.1k | static xxh_u64 xxHash64WithSeed(const char* s, size_t len, xxh_u64 seed) { |
341 | 18.1k | return XXH3_64bits_withSeed(s, len, seed); |
342 | 18.1k | } |
343 | | |
344 | | // same to the up function, just for null value |
345 | | static xxh_u64 xxHash64NullWithSeed(xxh_u64 seed) { |
346 | | static const int INT_VALUE = 0; |
347 | | return XXH3_64bits_withSeed(reinterpret_cast<const char*>(&INT_VALUE), sizeof(int), seed); |
348 | | } |
349 | | |
350 | | #if defined(__clang__) |
351 | | #pragma clang diagnostic pop |
352 | | #endif |
353 | | }; |
354 | | |
355 | | } // namespace doris |
356 | | |
357 | | template <> |
358 | | struct std::hash<doris::TUniqueId> { |
359 | 7.52k | std::size_t operator()(const doris::TUniqueId& id) const { |
360 | 7.52k | std::size_t seed = 0; |
361 | 7.52k | seed = doris::HashUtil::hash(&id.lo, sizeof(id.lo), seed); |
362 | 7.52k | seed = doris::HashUtil::hash(&id.hi, sizeof(id.hi), seed); |
363 | 7.52k | return seed; |
364 | 7.52k | } |
365 | | }; |
366 | | |
367 | | template <> |
368 | | struct std::hash<doris::TNetworkAddress> { |
369 | | size_t operator()(const doris::TNetworkAddress& address) const { |
370 | | std::size_t seed = 0; |
371 | | seed = doris::HashUtil::hash(address.hostname.data(), address.hostname.size(), seed); |
372 | | seed = doris::HashUtil::hash(&address.port, 4, seed); |
373 | | return seed; |
374 | | } |
375 | | }; |
376 | | |
377 | | template <> |
378 | | struct std::hash<std::pair<doris::TUniqueId, int64_t>> { |
379 | 0 | size_t operator()(const std::pair<doris::TUniqueId, int64_t>& pair) const { |
380 | 0 | size_t seed = 0; |
381 | 0 | seed = doris::HashUtil::hash(&pair.first.lo, sizeof(pair.first.lo), seed); |
382 | 0 | seed = doris::HashUtil::hash(&pair.first.hi, sizeof(pair.first.hi), seed); |
383 | 0 | seed = doris::HashUtil::hash(&pair.second, sizeof(pair.second), seed); |
384 | 0 | return seed; |
385 | 0 | } |
386 | | }; |
387 | | |
388 | | template <class First, class Second> |
389 | | struct std::hash<std::pair<First, Second>> { |
390 | | size_t operator()(const pair<First, Second>& p) const { |
391 | | size_t h1 = std::hash<First>()(p.first); |
392 | | size_t h2 = std::hash<Second>()(p.second); |
393 | | return util_hash::HashLen16(h1, h2); |
394 | | } |
395 | | }; |