1 | #include <iostream> |
2 | #include <iomanip> |
3 | #include <vector> |
4 | |
5 | #include <Common/Stopwatch.h> |
6 | |
7 | //#define DBMS_HASH_MAP_COUNT_COLLISIONS |
8 | #define DBMS_HASH_MAP_DEBUG_RESIZES |
9 | |
10 | #include <Core/Types.h> |
11 | #include <IO/ReadBufferFromFile.h> |
12 | #include <IO/ReadHelpers.h> |
13 | #include <Compression/CompressedReadBuffer.h> |
14 | #include <common/StringRef.h> |
15 | #include <Common/HashTable/HashMap.h> |
16 | #include <Interpreters/AggregationCommon.h> |
17 | |
18 | #ifdef __SSE4_1__ |
19 | #include <smmintrin.h> |
20 | #endif |
21 | |
22 | |
23 | /** Do this: |
24 | for file in MobilePhoneModel PageCharset Params URLDomain UTMSource Referer URL Title; do |
25 | for size in 30000 100000 300000 1000000 5000000; do |
26 | echo |
27 | BEST_METHOD=0 |
28 | BEST_RESULT=0 |
29 | for method in {1..12}; do |
30 | echo -ne $file $size $method ''; |
31 | TOTAL_ELEMS=0 |
32 | for i in {0..1000}; do |
33 | TOTAL_ELEMS=$(( $TOTAL_ELEMS + $size )) |
34 | if [[ $TOTAL_ELEMS -gt 25000000 ]]; then break; fi |
35 | ./hash_map_string_2 $size $method < ${file}.bin 2>&1 | |
36 | grep HashMap | grep -oE '[0-9\.]+ elem'; |
37 | done | awk -W interactive '{ if ($1 > x) { x = $1 }; printf(".") } END { print x }' | tee /tmp/hash_map_string_2_res; |
38 | CUR_RESULT=$(cat /tmp/hash_map_string_2_res | tr -d '.') |
39 | if [[ $CUR_RESULT -gt $BEST_RESULT ]]; then |
40 | BEST_METHOD=$method |
41 | BEST_RESULT=$CUR_RESULT |
42 | fi; |
43 | done; |
44 | echo Best: $BEST_METHOD - $BEST_RESULT |
45 | done; |
46 | done |
47 | */ |
48 | |
49 | |
50 | #define DefineStringRef(STRUCT) \ |
51 | \ |
52 | struct STRUCT : public StringRef {}; \ |
53 | \ |
54 | namespace ZeroTraits \ |
55 | { \ |
56 | template <> \ |
57 | inline bool check<STRUCT>(STRUCT x) { return 0 == x.size; } \ |
58 | \ |
59 | template <> \ |
60 | inline void set<STRUCT>(STRUCT & x) { x.size = 0; } \ |
61 | } \ |
62 | \ |
63 | template <> \ |
64 | struct DefaultHash<STRUCT> \ |
65 | { \ |
66 | size_t operator() (STRUCT x) const \ |
67 | { \ |
68 | return CityHash_v1_0_2::CityHash64(x.data, x.size); \ |
69 | } \ |
70 | }; |
71 | |
72 | DefineStringRef(StringRef_Compare1_Ptrs) |
73 | DefineStringRef(StringRef_Compare1_Index) |
74 | DefineStringRef(StringRef_CompareMemcmp) |
75 | DefineStringRef(StringRef_Compare8_1_byUInt64) |
76 | DefineStringRef(StringRef_Compare16_1_byMemcmp) |
77 | DefineStringRef(StringRef_Compare16_1_byUInt64_logicAnd) |
78 | DefineStringRef(StringRef_Compare16_1_byUInt64_bitAnd) |
79 | |
80 | #ifdef __SSE4_1__ |
81 | DefineStringRef(StringRef_Compare16_1_byIntSSE) |
82 | DefineStringRef(StringRef_Compare16_1_byFloatSSE) |
83 | DefineStringRef(StringRef_Compare16_1_bySSE4) |
84 | DefineStringRef(StringRef_Compare16_1_bySSE4_wide) |
85 | DefineStringRef(StringRef_Compare16_1_bySSE_wide) |
86 | #endif |
87 | |
88 | DefineStringRef(StringRef_CompareAlwaysTrue) |
89 | DefineStringRef(StringRef_CompareAlmostAlwaysTrue) |
90 | |
91 | |
92 | inline bool (StringRef_Compare1_Ptrs lhs, StringRef_Compare1_Ptrs rhs) |
93 | { |
94 | if (lhs.size != rhs.size) |
95 | return false; |
96 | |
97 | if (lhs.size == 0) |
98 | return true; |
99 | |
100 | const char * pos1 = lhs.data; |
101 | const char * pos2 = rhs.data; |
102 | |
103 | const char * end1 = pos1 + lhs.size; |
104 | |
105 | while (pos1 < end1) |
106 | { |
107 | if (*pos1 != *pos2) |
108 | return false; |
109 | |
110 | ++pos1; |
111 | ++pos2; |
112 | } |
113 | |
114 | return true; |
115 | } |
116 | |
117 | inline bool operator==(StringRef_Compare1_Index lhs, StringRef_Compare1_Index rhs) |
118 | { |
119 | if (lhs.size != rhs.size) |
120 | return false; |
121 | |
122 | if (lhs.size == 0) |
123 | return true; |
124 | |
125 | for (size_t i = 0; i < lhs.size; ++i) |
126 | if (lhs.data[i] != rhs.data[i]) |
127 | return false; |
128 | |
129 | return true; |
130 | } |
131 | |
132 | inline bool operator==(StringRef_CompareMemcmp lhs, StringRef_CompareMemcmp rhs) |
133 | { |
134 | if (lhs.size != rhs.size) |
135 | return false; |
136 | |
137 | if (lhs.size == 0) |
138 | return true; |
139 | |
140 | return 0 == memcmp(lhs.data, rhs.data, lhs.size); |
141 | } |
142 | |
143 | |
144 | inline bool operator==(StringRef_Compare8_1_byUInt64 lhs, StringRef_Compare8_1_byUInt64 rhs) |
145 | { |
146 | if (lhs.size != rhs.size) |
147 | return false; |
148 | |
149 | if (lhs.size == 0) |
150 | return true; |
151 | |
152 | const char * p1 = lhs.data; |
153 | const char * p2 = rhs.data; |
154 | size_t size = lhs.size; |
155 | |
156 | const char * p1_end = p1 + size; |
157 | const char * p1_end_8 = p1 + size / 8 * 8; |
158 | |
159 | while (p1 < p1_end_8) |
160 | { |
161 | if (reinterpret_cast<const UInt64 *>(p1)[0] != reinterpret_cast<const UInt64 *>(p2)[0]) |
162 | return false; |
163 | |
164 | p1 += 8; |
165 | p2 += 8; |
166 | } |
167 | |
168 | while (p1 < p1_end) |
169 | { |
170 | if (*p1 != *p2) |
171 | return false; |
172 | |
173 | ++p1; |
174 | ++p2; |
175 | } |
176 | |
177 | return true; |
178 | } |
179 | |
180 | |
181 | |
182 | inline bool compare_byMemcmp(const char * p1, const char * p2) |
183 | { |
184 | return 0 == memcmp(p1, p2, 16); |
185 | } |
186 | |
187 | inline bool compare_byUInt64_logicAnd(const char * p1, const char * p2) |
188 | { |
189 | return reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0] |
190 | && reinterpret_cast<const UInt64 *>(p1)[1] == reinterpret_cast<const UInt64 *>(p2)[1]; |
191 | } |
192 | |
193 | inline bool compare_byUInt64_bitAnd(const char * p1, const char * p2) |
194 | { |
195 | return (reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0]) |
196 | & (reinterpret_cast<const UInt64 *>(p1)[1] == reinterpret_cast<const UInt64 *>(p2)[1]); |
197 | } |
198 | |
199 | #ifdef __SSE4_1__ |
200 | |
201 | inline bool compare_byIntSSE(const char * p1, const char * p2) |
202 | { |
203 | return 0xFFFF == _mm_movemask_epi8(_mm_cmpeq_epi8( |
204 | _mm_loadu_si128(reinterpret_cast<const __m128i *>(p1)), |
205 | _mm_loadu_si128(reinterpret_cast<const __m128i *>(p2)))); |
206 | } |
207 | |
208 | inline bool compare_byFloatSSE(const char * p1, const char * p2) |
209 | { |
210 | return !_mm_movemask_ps(_mm_cmpneq_ps( /// Looks like incorrect while comparing subnormal floats. |
211 | _mm_loadu_ps(reinterpret_cast<const float *>(p1)), |
212 | _mm_loadu_ps(reinterpret_cast<const float *>(p2)))); |
213 | } |
214 | |
215 | #endif |
216 | |
217 | |
218 | template <bool compare(const char *, const char *)> |
219 | inline bool memequal(const char * p1, const char * p2, size_t size) |
220 | { |
221 | // const char * p1_end = p1 + size; |
222 | const char * p1_end_16 = p1 + size / 16 * 16; |
223 | |
224 | while (p1 < p1_end_16) |
225 | { |
226 | if (!compare(p1, p2)) |
227 | return false; |
228 | |
229 | p1 += 16; |
230 | p2 += 16; |
231 | } |
232 | |
233 | /* while (p1 < p1_end) |
234 | { |
235 | if (*p1 != *p2) |
236 | return false; |
237 | |
238 | ++p1; |
239 | ++p2; |
240 | }*/ |
241 | |
242 | switch (size % 16) |
243 | { |
244 | case 15: if (p1[14] != p2[14]) return false; [[fallthrough]]; |
245 | case 14: if (p1[13] != p2[13]) return false; [[fallthrough]]; |
246 | case 13: if (p1[12] != p2[12]) return false; [[fallthrough]]; |
247 | case 12: if (reinterpret_cast<const UInt32 *>(p1)[2] == reinterpret_cast<const UInt32 *>(p2)[2]) goto l8; else return false; |
248 | case 11: if (p1[10] != p2[10]) return false; [[fallthrough]]; |
249 | case 10: if (p1[9] != p2[9]) return false; [[fallthrough]]; |
250 | case 9: if (p1[8] != p2[8]) return false; |
251 | l8: [[fallthrough]]; |
252 | case 8: return reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0]; |
253 | case 7: if (p1[6] != p2[6]) return false; [[fallthrough]]; |
254 | case 6: if (p1[5] != p2[5]) return false; [[fallthrough]]; |
255 | case 5: if (p1[4] != p2[4]) return false; [[fallthrough]]; |
256 | case 4: return reinterpret_cast<const UInt32 *>(p1)[0] == reinterpret_cast<const UInt32 *>(p2)[0]; |
257 | case 3: if (p1[2] != p2[2]) return false; [[fallthrough]]; |
258 | case 2: return reinterpret_cast<const UInt16 *>(p1)[0] == reinterpret_cast<const UInt16 *>(p2)[0]; |
259 | case 1: if (p1[0] != p2[0]) return false; [[fallthrough]]; |
260 | case 0: break; |
261 | } |
262 | |
263 | return true; |
264 | } |
265 | |
266 | |
267 | #ifdef __SSE4_1__ |
268 | |
269 | inline bool memequal_sse41(const char * p1, const char * p2, size_t size) |
270 | { |
271 | // const char * p1_end = p1 + size; |
272 | const char * p1_end_16 = p1 + size / 16 * 16; |
273 | |
274 | __m128i zero16 = _mm_setzero_si128(); |
275 | |
276 | while (p1 < p1_end_16) |
277 | { |
278 | if (!_mm_testc_si128( |
279 | zero16, |
280 | _mm_xor_si128( |
281 | _mm_loadu_si128(reinterpret_cast<const __m128i *>(p1)), |
282 | _mm_loadu_si128(reinterpret_cast<const __m128i *>(p2))))) |
283 | return false; |
284 | |
285 | p1 += 16; |
286 | p2 += 16; |
287 | } |
288 | |
289 | /* while (p1 < p1_end) |
290 | { |
291 | if (*p1 != *p2) |
292 | return false; |
293 | |
294 | ++p1; |
295 | ++p2; |
296 | }*/ |
297 | |
298 | switch (size % 16) |
299 | { |
300 | case 15: if (p1[14] != p2[14]) return false; [[fallthrough]]; |
301 | case 14: if (p1[13] != p2[13]) return false; [[fallthrough]]; |
302 | case 13: if (p1[12] != p2[12]) return false; [[fallthrough]]; |
303 | case 12: if (reinterpret_cast<const UInt32 *>(p1)[2] == reinterpret_cast<const UInt32 *>(p2)[2]) goto l8; else return false; |
304 | case 11: if (p1[10] != p2[10]) return false; [[fallthrough]]; |
305 | case 10: if (p1[9] != p2[9]) return false; [[fallthrough]]; |
306 | case 9: if (p1[8] != p2[8]) return false; |
307 | l8: [[fallthrough]]; |
308 | case 8: return reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0]; |
309 | case 7: if (p1[6] != p2[6]) return false; [[fallthrough]]; |
310 | case 6: if (p1[5] != p2[5]) return false; [[fallthrough]]; |
311 | case 5: if (p1[4] != p2[4]) return false; [[fallthrough]]; |
312 | case 4: return reinterpret_cast<const UInt32 *>(p1)[0] == reinterpret_cast<const UInt32 *>(p2)[0]; |
313 | case 3: if (p1[2] != p2[2]) return false; [[fallthrough]]; |
314 | case 2: return reinterpret_cast<const UInt16 *>(p1)[0] == reinterpret_cast<const UInt16 *>(p2)[0]; |
315 | case 1: if (p1[0] != p2[0]) return false; [[fallthrough]]; |
316 | case 0: break; |
317 | } |
318 | |
319 | return true; |
320 | } |
321 | |
322 | |
323 | inline bool memequal_sse41_wide(const char * p1, const char * p2, size_t size) |
324 | { |
325 | __m128i zero16 = _mm_setzero_si128(); |
326 | // const char * p1_end = p1 + size; |
327 | |
328 | while (size >= 64) |
329 | { |
330 | if (_mm_testc_si128( |
331 | zero16, |
332 | _mm_xor_si128( |
333 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[0]), |
334 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[0]))) |
335 | && _mm_testc_si128( |
336 | zero16, |
337 | _mm_xor_si128( |
338 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[1]), |
339 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[1]))) |
340 | && _mm_testc_si128( |
341 | zero16, |
342 | _mm_xor_si128( |
343 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[2]), |
344 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[2]))) |
345 | && _mm_testc_si128( |
346 | zero16, |
347 | _mm_xor_si128( |
348 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[3]), |
349 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[3])))) |
350 | { |
351 | p1 += 64; |
352 | p2 += 64; |
353 | size -= 64; |
354 | } |
355 | else |
356 | return false; |
357 | } |
358 | |
359 | switch ((size % 64) / 16) |
360 | { |
361 | case 3: |
362 | if (!_mm_testc_si128( |
363 | zero16, |
364 | _mm_xor_si128( |
365 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[2]), |
366 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[2])))) |
367 | return false; |
368 | [[fallthrough]]; |
369 | case 2: |
370 | if (!_mm_testc_si128( |
371 | zero16, |
372 | _mm_xor_si128( |
373 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[1]), |
374 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[1])))) |
375 | return false; |
376 | [[fallthrough]]; |
377 | case 1: |
378 | if (!_mm_testc_si128( |
379 | zero16, |
380 | _mm_xor_si128( |
381 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[0]), |
382 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[0])))) |
383 | return false; |
384 | } |
385 | |
386 | p1 += (size % 64) / 16 * 16; |
387 | p2 += (size % 64) / 16 * 16; |
388 | |
389 | /* |
390 | |
391 | if (size >= 32) |
392 | { |
393 | if (_mm_testc_si128( |
394 | zero16, |
395 | _mm_xor_si128( |
396 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[0]), |
397 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[0]))) |
398 | & _mm_testc_si128( |
399 | zero16, |
400 | _mm_xor_si128( |
401 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[1]), |
402 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[1])))) |
403 | { |
404 | p1 += 32; |
405 | p2 += 32; |
406 | size -= 32; |
407 | } |
408 | else |
409 | return false; |
410 | } |
411 | |
412 | if (size >= 16) |
413 | { |
414 | if (_mm_testc_si128( |
415 | zero16, |
416 | _mm_xor_si128( |
417 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p1)[0]), |
418 | _mm_loadu_si128(&reinterpret_cast<const __m128i *>(p2)[0])))) |
419 | { |
420 | p1 += 16; |
421 | p2 += 16; |
422 | size -= 16; |
423 | } |
424 | else |
425 | return false; |
426 | }*/ |
427 | |
428 | switch (size % 16) |
429 | { |
430 | case 15: if (p1[14] != p2[14]) return false; [[fallthrough]]; |
431 | case 14: if (p1[13] != p2[13]) return false; [[fallthrough]]; |
432 | case 13: if (p1[12] != p2[12]) return false; [[fallthrough]]; |
433 | case 12: if (reinterpret_cast<const UInt32 *>(p1)[2] == reinterpret_cast<const UInt32 *>(p2)[2]) goto l8; else return false; |
434 | case 11: if (p1[10] != p2[10]) return false; [[fallthrough]]; |
435 | case 10: if (p1[9] != p2[9]) return false; [[fallthrough]]; |
436 | case 9: if (p1[8] != p2[8]) return false; |
437 | l8: [[fallthrough]]; |
438 | case 8: return reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0]; |
439 | case 7: if (p1[6] != p2[6]) return false; [[fallthrough]]; |
440 | case 6: if (p1[5] != p2[5]) return false; [[fallthrough]]; |
441 | case 5: if (p1[4] != p2[4]) return false; [[fallthrough]]; |
442 | case 4: return reinterpret_cast<const UInt32 *>(p1)[0] == reinterpret_cast<const UInt32 *>(p2)[0]; |
443 | case 3: if (p1[2] != p2[2]) return false; [[fallthrough]]; |
444 | case 2: return reinterpret_cast<const UInt16 *>(p1)[0] == reinterpret_cast<const UInt16 *>(p2)[0]; |
445 | case 1: if (p1[0] != p2[0]) return false; [[fallthrough]]; |
446 | case 0: break; |
447 | } |
448 | |
449 | return true; |
450 | } |
451 | |
452 | |
453 | inline bool memequal_sse_wide(const char * p1, const char * p2, size_t size) |
454 | { |
455 | while (size >= 64) |
456 | { |
457 | if ( compare_byIntSSE(p1, p2) |
458 | && compare_byIntSSE(p1 + 16, p2 + 16) |
459 | && compare_byIntSSE(p1 + 32, p2 + 32) |
460 | && compare_byIntSSE(p1 + 48, p2 + 48)) |
461 | { |
462 | p1 += 64; |
463 | p2 += 64; |
464 | size -= 64; |
465 | } |
466 | else |
467 | return false; |
468 | } |
469 | |
470 | switch ((size % 64) / 16) |
471 | { |
472 | case 3: if (!compare_byIntSSE(p1 + 32, p2 + 32)) return false; [[fallthrough]]; |
473 | case 2: if (!compare_byIntSSE(p1 + 16, p2 + 16)) return false; [[fallthrough]]; |
474 | case 1: if (!compare_byIntSSE(p1 , p2 )) return false; |
475 | } |
476 | |
477 | p1 += (size % 64) / 16 * 16; |
478 | p2 += (size % 64) / 16 * 16; |
479 | |
480 | switch (size % 16) |
481 | { |
482 | case 15: if (p1[14] != p2[14]) return false; [[fallthrough]]; |
483 | case 14: if (p1[13] != p2[13]) return false; [[fallthrough]]; |
484 | case 13: if (p1[12] != p2[12]) return false; [[fallthrough]]; |
485 | case 12: if (reinterpret_cast<const UInt32 *>(p1)[2] == reinterpret_cast<const UInt32 *>(p2)[2]) goto l8; else return false; |
486 | case 11: if (p1[10] != p2[10]) return false; [[fallthrough]]; |
487 | case 10: if (p1[9] != p2[9]) return false; [[fallthrough]]; |
488 | case 9: if (p1[8] != p2[8]) return false; |
489 | l8: [[fallthrough]]; |
490 | case 8: return reinterpret_cast<const UInt64 *>(p1)[0] == reinterpret_cast<const UInt64 *>(p2)[0]; |
491 | case 7: if (p1[6] != p2[6]) return false; [[fallthrough]]; |
492 | case 6: if (p1[5] != p2[5]) return false; [[fallthrough]]; |
493 | case 5: if (p1[4] != p2[4]) return false; [[fallthrough]]; |
494 | case 4: return reinterpret_cast<const UInt32 *>(p1)[0] == reinterpret_cast<const UInt32 *>(p2)[0]; |
495 | case 3: if (p1[2] != p2[2]) return false; [[fallthrough]]; |
496 | case 2: return reinterpret_cast<const UInt16 *>(p1)[0] == reinterpret_cast<const UInt16 *>(p2)[0]; |
497 | case 1: if (p1[0] != p2[0]) return false; [[fallthrough]]; |
498 | case 0: break; |
499 | } |
500 | |
501 | return true; |
502 | } |
503 | |
504 | #endif |
505 | |
506 | |
507 | #define Op(METHOD) \ |
508 | inline bool operator==(StringRef_Compare16_1_ ## METHOD lhs, StringRef_Compare16_1_ ## METHOD rhs) \ |
509 | { \ |
510 | if (lhs.size != rhs.size) \ |
511 | return false; \ |
512 | \ |
513 | if (lhs.size == 0) \ |
514 | return true; \ |
515 | \ |
516 | return memequal<compare_ ## METHOD>(lhs.data, rhs.data, lhs.size); \ |
517 | } |
518 | |
519 | Op(byMemcmp) |
520 | Op(byUInt64_logicAnd) |
521 | Op(byUInt64_bitAnd) |
522 | |
523 | #ifdef __SSE4_1__ |
524 | |
525 | Op(byIntSSE) |
526 | Op(byFloatSSE) |
527 | |
528 | |
529 | inline bool operator==(StringRef_Compare16_1_bySSE4 lhs, StringRef_Compare16_1_bySSE4 rhs) |
530 | { |
531 | if (lhs.size != rhs.size) |
532 | return false; |
533 | |
534 | if (lhs.size == 0) |
535 | return true; |
536 | |
537 | return memequal_sse41(lhs.data, rhs.data, lhs.size); |
538 | } |
539 | |
540 | inline bool operator==(StringRef_Compare16_1_bySSE4_wide lhs, StringRef_Compare16_1_bySSE4_wide rhs) |
541 | { |
542 | if (lhs.size != rhs.size) |
543 | return false; |
544 | |
545 | if (lhs.size == 0) |
546 | return true; |
547 | |
548 | return memequal_sse41_wide(lhs.data, rhs.data, lhs.size); |
549 | } |
550 | |
551 | inline bool operator==(StringRef_Compare16_1_bySSE_wide lhs, StringRef_Compare16_1_bySSE_wide rhs) |
552 | { |
553 | if (lhs.size != rhs.size) |
554 | return false; |
555 | |
556 | if (lhs.size == 0) |
557 | return true; |
558 | |
559 | return memequal_sse_wide(lhs.data, rhs.data, lhs.size); |
560 | } |
561 | |
562 | #endif |
563 | |
564 | |
565 | inline bool operator==(StringRef_CompareAlwaysTrue, StringRef_CompareAlwaysTrue) |
566 | { |
567 | return true; |
568 | } |
569 | |
570 | inline bool operator==(StringRef_CompareAlmostAlwaysTrue lhs, StringRef_CompareAlmostAlwaysTrue rhs) |
571 | { |
572 | if (lhs.size != rhs.size) |
573 | return false; |
574 | |
575 | return true; |
576 | } |
577 | |
578 | |
579 | |
580 | using Value = UInt64; |
581 | |
582 | |
583 | template <typename Key> |
584 | void NO_INLINE bench(const std::vector<StringRef> & data, const char * name) |
585 | { |
586 | Stopwatch watch; |
587 | |
588 | using Map = HashMapWithSavedHash<Key, Value, DefaultHash<Key>>; |
589 | |
590 | Map map; |
591 | typename Map::LookupResult it; |
592 | bool inserted; |
593 | |
594 | for (size_t i = 0, size = data.size(); i < size; ++i) |
595 | { |
596 | map.emplace(static_cast<const Key &>(data[i]), it, inserted); |
597 | if (inserted) |
598 | it->getMapped() = 0; |
599 | ++it->getMapped(); |
600 | } |
601 | |
602 | watch.stop(); |
603 | std::cerr << std::fixed << std::setprecision(2) |
604 | << "HashMap (" << name << "). Size: " << map.size() |
605 | << ", elapsed: " << watch.elapsedSeconds() |
606 | << " (" << data.size() / watch.elapsedSeconds() << " elem/sec.)" |
607 | #ifdef DBMS_HASH_MAP_COUNT_COLLISIONS |
608 | << ", collisions: " << map.getCollisions() |
609 | #endif |
610 | << std::endl; |
611 | } |
612 | |
613 | |
614 | int main(int argc, char ** argv) |
615 | { |
616 | if (argc < 3) |
617 | { |
618 | std::cerr << "Usage: program n m\n" ; |
619 | return 1; |
620 | } |
621 | |
622 | size_t n = atoi(argv[1]); |
623 | size_t m = atoi(argv[2]); |
624 | |
625 | DB::Arena pool; |
626 | std::vector<StringRef> data(n); |
627 | |
628 | std::cerr << "sizeof(Key) = " << sizeof(StringRef) << ", sizeof(Value) = " << sizeof(Value) << std::endl; |
629 | |
630 | { |
631 | Stopwatch watch; |
632 | DB::ReadBufferFromFileDescriptor in1(STDIN_FILENO); |
633 | DB::CompressedReadBuffer in2(in1); |
634 | |
635 | std::string tmp; |
636 | for (size_t i = 0; i < n && !in2.eof(); ++i) |
637 | { |
638 | DB::readStringBinary(tmp, in2); |
639 | data[i] = StringRef(pool.insert(tmp.data(), tmp.size()), tmp.size()); |
640 | } |
641 | |
642 | watch.stop(); |
643 | std::cerr << std::fixed << std::setprecision(2) |
644 | << "Vector. Size: " << n |
645 | << ", elapsed: " << watch.elapsedSeconds() |
646 | << " (" << n / watch.elapsedSeconds() << " elem/sec.)" |
647 | << std::endl; |
648 | } |
649 | |
650 | if (!m || m == 1) bench<StringRef_Compare1_Ptrs> (data, "StringRef_Compare1_Ptrs" ); |
651 | if (!m || m == 2) bench<StringRef_Compare1_Index> (data, "StringRef_Compare1_Index" ); |
652 | if (!m || m == 3) bench<StringRef_CompareMemcmp> (data, "StringRef_CompareMemcmp" ); |
653 | if (!m || m == 4) bench<StringRef_Compare8_1_byUInt64> (data, "StringRef_Compare8_1_byUInt64" ); |
654 | if (!m || m == 5) bench<StringRef_Compare16_1_byMemcmp> (data, "StringRef_Compare16_1_byMemcmp" ); |
655 | if (!m || m == 6) bench<StringRef_Compare16_1_byUInt64_logicAnd>(data, "StringRef_Compare16_1_byUInt64_logicAnd" ); |
656 | if (!m || m == 7) bench<StringRef_Compare16_1_byUInt64_bitAnd> (data, "StringRef_Compare16_1_byUInt64_bitAnd" ); |
657 | #ifdef __SSE4_1__ |
658 | if (!m || m == 8) bench<StringRef_Compare16_1_byIntSSE> (data, "StringRef_Compare16_1_byIntSSE" ); |
659 | if (!m || m == 9) bench<StringRef_Compare16_1_byFloatSSE> (data, "StringRef_Compare16_1_byFloatSSE" ); |
660 | if (!m || m == 10) bench<StringRef_Compare16_1_bySSE4> (data, "StringRef_Compare16_1_bySSE4" ); |
661 | if (!m || m == 11) bench<StringRef_Compare16_1_bySSE4_wide> (data, "StringRef_Compare16_1_bySSE4_wide" ); |
662 | if (!m || m == 12) bench<StringRef_Compare16_1_bySSE_wide> (data, "StringRef_Compare16_1_bySSE_wide" ); |
663 | #endif |
664 | if (!m || m == 100) bench<StringRef_CompareAlwaysTrue> (data, "StringRef_CompareAlwaysTrue" ); |
665 | if (!m || m == 101) bench<StringRef_CompareAlmostAlwaysTrue> (data, "StringRef_CompareAlmostAlwaysTrue" ); |
666 | |
667 | /// 10 > 8, 9 |
668 | /// 1, 2, 5 - bad |
669 | |
670 | |
671 | return 0; |
672 | } |
673 | |