rurban
commented
4 years ago sure I'll check, but only in about 2 weeks or so. thanks
Closed Sanmayce closed 4 years ago
rurban
commented
4 years ago sure I'll check, but only in about 2 weeks or so. thanks
Sanmayce
commented
4 years ago Reini, had time to play with it and realized it is causa perduta, so ... so long 32bit, here comes fastest known to me lookuper:
#include <stdint.h> // uint8_t needed
#define _PADr_KAZE(x, n) ( ((x) << (n))>>(n) )
#define ROLInBits 27 // 5 in r.1; Caramba: it should be ROR by 5 not ROL, from the very beginning the idea was to mix two bytes by shifting/masking the first 5 'noisy' bits (ASCII 0-31 symbols).
// CAUTION: Add 8 more bytes to the buffer being hashed, usually malloc(...+8) - to prevent out of boundary reads!
#define _rotl64_KAZE(x, n) (((x) << (n)) | ((x) >> (64-(n))))
uint32_t FNV1A_Hash_Totenschiff_v1(const char *str, uint32_t wrdlen)
{
const uint32_t PRIME = 591798841;
uint32_t hash32 = 2166136261;
uint64_t hash64 = 14695981039346656037;//2166136261;
const char *p = str;
uint64_t PADDEDby8;
for(; wrdlen > 2*sizeof(uint32_t); wrdlen -= 2*sizeof(uint32_t), p += 2*sizeof(uint32_t)) {
PADDEDby8 = *(uint64_t *)(p+0);
hash64 = ( hash64 ^ PADDEDby8 ) * PRIME;
}
// Here 'wrdlen' is 1..8
PADDEDby8 = _PADr_KAZE(*(uint64_t *)(p+0), (8-wrdlen)<<3); // when (8-8) the QWORD remains intact
hash64 = ( hash64 ^ PADDEDby8 ) * PRIME;
hash32 = (uint32_t)(hash64 ^ (hash64>>32));
return hash32 ^ (hash32 >> 16);
}I did what I could. I believe, FNV1A-Totenschiff dominates whenever small keys are to be hashed for lookup tables.
rurban
commented
4 years ago This is a very bad hash. It fails the AppendedZeroesTest, which makes it trivial to exploit (just add \0's somewhere in the key, and it will collide), it's slower than FNV1a-YoshimitsuTRIAD, and it's a poor version of my FNV2.
$ for h in FNV1A_Totenschiff FNV1a_YT FNV2; do build/SMHasher --test=Sanity,Speed $h; done
-------------------------------------------------------------------------------
--- Testing FNV1A_Totenschiff "FNV1A_Totenschiff_v1 64-bit sanmayce" POOR
[[[ Sanity Tests ]]]
Verification value 0x95D95ACF ....... PASS
Running sanity check 1 .......... PASS
Running AppendedZeroesTest . FAIL !!!!!
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 7 - 2.185 bytes/cycle - 6250.04 MiB/sec @ 3 ghz
Alignment 6 - 2.185 bytes/cycle - 6250.02 MiB/sec @ 3 ghz
Alignment 5 - 2.185 bytes/cycle - 6250.01 MiB/sec @ 3 ghz
Alignment 4 - 2.185 bytes/cycle - 6249.90 MiB/sec @ 3 ghz
Alignment 3 - 2.185 bytes/cycle - 6249.91 MiB/sec @ 3 ghz
Alignment 2 - 2.153 bytes/cycle - 6158.71 MiB/sec @ 3 ghz
Alignment 1 - 2.184 bytes/cycle - 6249.90 MiB/sec @ 3 ghz
Alignment 0 - 2.214 bytes/cycle - 6333.18 MiB/sec @ 3 ghz
Average - 2.184 bytes/cycle - 6248.96 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 32.00 cycles/hash
Small key speed test - 2-byte keys - 32.00 cycles/hash
Small key speed test - 3-byte keys - 32.00 cycles/hash
Small key speed test - 4-byte keys - 32.00 cycles/hash
Small key speed test - 5-byte keys - 32.00 cycles/hash
Small key speed test - 6-byte keys - 32.00 cycles/hash
Small key speed test - 7-byte keys - 32.00 cycles/hash
Small key speed test - 8-byte keys - 32.67 cycles/hash
Small key speed test - 9-byte keys - 36.00 cycles/hash
Small key speed test - 10-byte keys - 36.00 cycles/hash
Small key speed test - 11-byte keys - 36.00 cycles/hash
Small key speed test - 12-byte keys - 36.00 cycles/hash
Small key speed test - 13-byte keys - 36.00 cycles/hash
Small key speed test - 14-byte keys - 36.00 cycles/hash
Small key speed test - 15-byte keys - 36.00 cycles/hash
Small key speed test - 16-byte keys - 35.71 cycles/hash
Small key speed test - 17-byte keys - 39.00 cycles/hash
Small key speed test - 18-byte keys - 39.00 cycles/hash
Small key speed test - 19-byte keys - 39.00 cycles/hash
Small key speed test - 20-byte keys - 39.00 cycles/hash
Small key speed test - 21-byte keys - 39.00 cycles/hash
Small key speed test - 22-byte keys - 39.00 cycles/hash
Small key speed test - 23-byte keys - 39.00 cycles/hash
Small key speed test - 24-byte keys - 39.00 cycles/hash
Small key speed test - 25-byte keys - 43.00 cycles/hash
Small key speed test - 26-byte keys - 43.00 cycles/hash
Small key speed test - 27-byte keys - 43.00 cycles/hash
Small key speed test - 28-byte keys - 43.00 cycles/hash
Small key speed test - 29-byte keys - 43.00 cycles/hash
Small key speed test - 30-byte keys - 43.00 cycles/hash
Small key speed test - 31-byte keys - 43.00 cycles/hash
Average 37.335 cycles/hash
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 16.447822 seconds
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
--- Testing FNV1a_YT "FNV1a-YoshimitsuTRIAD 32-bit sanmayce" POOR
[[[ Sanity Tests ]]]
Verification value 0xD8AFFD71 ....... PASS
Running sanity check 1 .......... PASS
Running AppendedZeroesTest .......... PASS
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 7 - 2.986 bytes/cycle - 8544.33 MiB/sec @ 3 ghz
Alignment 6 - 2.986 bytes/cycle - 8541.67 MiB/sec @ 3 ghz
Alignment 5 - 2.986 bytes/cycle - 8544.02 MiB/sec @ 3 ghz
Alignment 4 - 3.116 bytes/cycle - 8916.09 MiB/sec @ 3 ghz
Alignment 3 - 3.022 bytes/cycle - 8645.94 MiB/sec @ 3 ghz
Alignment 2 - 3.022 bytes/cycle - 8646.86 MiB/sec @ 3 ghz
Alignment 1 - 3.022 bytes/cycle - 8645.74 MiB/sec @ 3 ghz
Alignment 0 - 3.116 bytes/cycle - 8913.68 MiB/sec @ 3 ghz
Average - 3.032 bytes/cycle - 8674.79 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 22.00 cycles/hash
Small key speed test - 2-byte keys - 22.00 cycles/hash
Small key speed test - 3-byte keys - 26.00 cycles/hash
Small key speed test - 4-byte keys - 24.76 cycles/hash
Small key speed test - 5-byte keys - 26.00 cycles/hash
Small key speed test - 6-byte keys - 26.00 cycles/hash
Small key speed test - 7-byte keys - 30.00 cycles/hash
Small key speed test - 8-byte keys - 22.00 cycles/hash
Small key speed test - 9-byte keys - 26.00 cycles/hash
Small key speed test - 10-byte keys - 26.00 cycles/hash
Small key speed test - 11-byte keys - 30.00 cycles/hash
Small key speed test - 12-byte keys - 26.00 cycles/hash
Small key speed test - 13-byte keys - 30.00 cycles/hash
Small key speed test - 14-byte keys - 30.00 cycles/hash
Small key speed test - 15-byte keys - 34.00 cycles/hash
Small key speed test - 16-byte keys - 22.24 cycles/hash
Small key speed test - 17-byte keys - 25.82 cycles/hash
Small key speed test - 18-byte keys - 25.00 cycles/hash
Small key speed test - 19-byte keys - 29.00 cycles/hash
Small key speed test - 20-byte keys - 25.00 cycles/hash
Small key speed test - 21-byte keys - 29.00 cycles/hash
Small key speed test - 22-byte keys - 29.00 cycles/hash
Small key speed test - 23-byte keys - 33.00 cycles/hash
Small key speed test - 24-byte keys - 27.00 cycles/hash
Small key speed test - 25-byte keys - 30.58 cycles/hash
Small key speed test - 26-byte keys - 30.00 cycles/hash
Small key speed test - 27-byte keys - 34.00 cycles/hash
Small key speed test - 28-byte keys - 30.59 cycles/hash
Small key speed test - 29-byte keys - 34.00 cycles/hash
Small key speed test - 30-byte keys - 34.00 cycles/hash
Small key speed test - 31-byte keys - 38.00 cycles/hash
Average 28.290 cycles/hash
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 14.264823 seconds
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
--- Testing FNV2 "wordwise FNV" POOR
[[[ Sanity Tests ]]]
Verification value 0x1967C625 ....... PASS
Running sanity check 1 .......... PASS
Running AppendedZeroesTest .......... PASS
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 7 - 2.185 bytes/cycle - 6250.08 MiB/sec @ 3 ghz
Alignment 6 - 2.185 bytes/cycle - 6250.08 MiB/sec @ 3 ghz
Alignment 5 - 2.185 bytes/cycle - 6250.08 MiB/sec @ 3 ghz
Alignment 4 - 2.185 bytes/cycle - 6250.04 MiB/sec @ 3 ghz
Alignment 3 - 2.185 bytes/cycle - 6250.00 MiB/sec @ 3 ghz
Alignment 2 - 2.185 bytes/cycle - 6250.05 MiB/sec @ 3 ghz
Alignment 1 - 2.185 bytes/cycle - 6250.03 MiB/sec @ 3 ghz
Alignment 0 - 2.214 bytes/cycle - 6332.90 MiB/sec @ 3 ghz
Average - 2.188 bytes/cycle - 6260.41 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 15.00 cycles/hash
Small key speed test - 2-byte keys - 19.00 cycles/hash
Small key speed test - 3-byte keys - 22.00 cycles/hash
Small key speed test - 4-byte keys - 26.00 cycles/hash
Small key speed test - 5-byte keys - 29.76 cycles/hash
Small key speed test - 6-byte keys - 33.00 cycles/hash
Small key speed test - 7-byte keys - 37.00 cycles/hash
Small key speed test - 8-byte keys - 26.00 cycles/hash
Small key speed test - 9-byte keys - 29.00 cycles/hash
Small key speed test - 10-byte keys - 35.00 cycles/hash
Small key speed test - 11-byte keys - 39.61 cycles/hash
Small key speed test - 12-byte keys - 40.33 cycles/hash
Small key speed test - 13-byte keys - 43.00 cycles/hash
Small key speed test - 14-byte keys - 47.00 cycles/hash
Small key speed test - 15-byte keys - 50.39 cycles/hash
Small key speed test - 16-byte keys - 29.00 cycles/hash
Small key speed test - 17-byte keys - 32.00 cycles/hash
Small key speed test - 18-byte keys - 36.00 cycles/hash
Small key speed test - 19-byte keys - 39.46 cycles/hash
Small key speed test - 20-byte keys - 43.00 cycles/hash
Small key speed test - 21-byte keys - 47.00 cycles/hash
Small key speed test - 22-byte keys - 50.00 cycles/hash
Small key speed test - 23-byte keys - 54.00 cycles/hash
Small key speed test - 24-byte keys - 33.00 cycles/hash
Small key speed test - 25-byte keys - 36.00 cycles/hash
Small key speed test - 26-byte keys - 39.00 cycles/hash
Small key speed test - 27-byte keys - 43.00 cycles/hash
Small key speed test - 28-byte keys - 47.60 cycles/hash
Small key speed test - 29-byte keys - 50.56 cycles/hash
Small key speed test - 30-byte keys - 54.00 cycles/hash
Small key speed test - 31-byte keys - 57.00 cycles/hash
Average 38.152 cycles/hash
Input vcode 0x00000001, Output vcode 0x00000001, Result vcode 0x00000001
Verification value is 0x00000001 - Testing took 16.521330 secondsThank you for running it against SMHASHER, but saying:
This is a very bad hash. Is true only within this synthetic tester, which is too strict and actually discards the best practical hashers for real usecase scenarios, like English n-grams.
(just add \0's somewhere in the key, and it will collide), Hm, I don't follow, maybe you meant at the end?! This is easily fixable (I was aware of it) with adding the KEYLENGTH to the hash value at the very end.
37.335 cycles/hash It only proves how synthetic these values are, in practice, I showed it is irrelevant. QWORD fetching is around the corner...
By the way, what CPU were you using?
rurban
commented
4 years ago Sanmayce notifications@github.com schrieb am Di., 15. Okt. 2019, 13:09:
Thank you for running it against SMHASHER, but saying:
This is a very bad hash.
Is true only within this synthetic tester, which is too strict and actually discards the best practical hashers for real usecase scenarios, like English n-grams.
Agreed. In fast hash tables I still use FNV1a, which is similarly bad but beats all others.
(just add \0's somewhere in the key, and it will collide),
Hm, I don't follow, maybe you meant at the end?! This is easily fixable (I was aware of it) with adding the KEYLENGTH to the hash value at the very end.
\0 could also be in the middle. It's the multiplication by 0. I fixed it in some FNV variants.
37.335 cycles/hash
It only proves how synthetic these values are, in practice, I showed it is
irrelevant. QWORD fetching is around the corner...
By the way, what CPU were you using?
Currently a bad one, an old i5, but the problem are the recent kernel mitigations. Twice as slow as last year.
Sanmayce
commented
4 years ago Thank you once more for all the testing, it takes time.
The results are unexpectedly low as if the SMHASHER was 32bit code!
Saying FNV1A-Totenschiff is bad is funny to me, it is the fastest practical hasher for table lookups known to me, straight up. To challenge my statement, please provide a set of keys, corpus or whatever and a methodology of your choice, I will run it using Intel v19.0 and GCC 7.3.0 both on Ivy Bridge and Kaby Lake.
Regarding 37.335 cycles/hash, I have a question, what is your understanding of ALL my benchmarks outspeeding WYHASH (while keeping collisions on par) which features half the cycles?!
Allow me few remarks:
Don't you see that we need PRACTICAL speeds measured, I am open to hear what you can say about making a proper speed measuring, what methodology you prefer. For now, my choice (in Lookuperorama r.4) is to punish heavily hashers that tend to stack hashes onto certain slots by building in each slot a B-tree - the more collisions the more time penalties. In contrast, if the most basic benchmark is to be employed (hashing in small cycle all the positions of a given file and counting the collisions) then we CANNOT punish the worse dispersion - the speed will be a constant while not taking into account THE REAL-WORLD needs for evenly filled hash-table.
Let's see a file full with \0s:
First 512 bytes of: '(Dictionary_Specification_Language_..)_Hanyu_Cihai_new_Sea-of-Words_(Zho-Zho).dsl' 42,920,232 bytes:
0000 ff fe 23 00 4e 00 41 00 4d 00 45 00 09 00 22 00 48 00 61 00 6e 00 79 00 75 00 20 00 43 00 69 00 ..#.N.A.M.E...".H.a.n.y.u. .C.i.
0020 68 00 61 00 69 00 20 00 2c 00 20 00 53 00 69 00 6d 00 70 00 20 00 28 00 43 00 68 00 2d 00 43 00 h.a.i. .,. .S.i.m.p. .(.C.h.-.C.
0040 68 00 29 00 22 00 0d 00 0a 00 23 00 49 00 4e 00 44 00 45 00 58 00 5f 00 4c 00 41 00 4e 00 47 00 h.).".....#.I.N.D.E.X._.L.A.N.G.
0060 55 00 41 00 47 00 45 00 09 00 22 00 43 00 68 00 69 00 6e 00 65 00 73 00 65 00 22 00 0d 00 0a 00 U.A.G.E...".C.h.i.n.e.s.e.".....
0080 23 00 43 00 4f 00 4e 00 54 00 45 00 4e 00 54 00 53 00 5f 00 4c 00 41 00 4e 00 47 00 55 00 41 00 #.C.O.N.T.E.N.T.S._.L.A.N.G.U.A.
00a0 47 00 45 00 09 00 22 00 43 00 68 00 69 00 6e 00 65 00 73 00 65 00 22 00 0d 00 0a 00 23 00 49 00 G.E...".C.h.i.n.e.s.e.".....#.I.
00c0 43 00 4f 00 4e 00 5f 00 46 00 49 00 4c 00 45 00 09 00 22 00 43 00 3a 00 5c 00 5c 00 55 00 73 00 C.O.N._.F.I.L.E...".C.:.\.\.U.s.
00e0 65 00 72 00 73 00 5c 00 5c 00 53 00 61 00 62 00 69 00 72 00 6a 00 61 00 6e 00 5c 00 5c 00 44 00 e.r.s.\.\.S.a.b.i.r.j.a.n.\.\.D.
0100 65 00 73 00 6b 00 74 00 6f 00 70 00 5c 00 5c 00 48 00 61 00 6e 00 79 00 75 00 20 00 43 00 69 00 e.s.k.t.o.p.\.\.H.a.n.y.u. .C.i.
0120 68 00 61 00 69 00 5c 00 5c 00 48 00 61 00 6e 00 79 00 75 00 5f 00 43 00 69 00 68 00 61 00 69 00 h.a.i.\.\.H.a.n.y.u._.C.i.h.a.i.
0140 5f 00 6e 00 65 00 77 00 2e 00 62 00 6d 00 70 00 22 00 0d 00 0a 00 0d 00 0a 00 b1 03 04 5c bf 7e _.n.e.w...b.m.p."............\.~
0160 0d 00 0a 00 09 00 5b 00 74 00 72 00 6e 00 5d 00 b1 03 20 00 73 00 68 00 e8 00 20 00 78 00 69 00 ......[.t.r.n.]... .s.h... .x.i.
0180 e0 00 6e 00 0d 00 0a 00 09 00 73 53 1a ff 3f 96 14 5c d5 6c 04 5c bf 7e 02 30 3e 65 04 5c 27 60 ..n.......sS..?..\.l.\.~.0>e.\'`
01a0 69 72 28 8d 70 88 d8 53 f6 65 3e 65 04 5c fa 51 65 67 84 76 32 75 cd 79 92 7c 50 5b 41 6d 02 30 ir(.p..S.e>e.\.Qeg.v2u.y.|P[Am.0
01c0 5f 4e eb 53 1c 20 32 75 cd 79 04 5c bf 7e 1d 20 02 30 5b 00 2f 00 74 00 72 00 6e 00 5d 00 0d 00 _N.S. 2u.y.\.~. .0[./.t.r.n.]...
01e0 0a 00 b1 03 92 7c 50 5b 0d 00 0a 00 09 00 5b 00 74 00 72 00 6e 00 5d 00 b1 03 20 00 6c 00 ec 00 .....|P[......[.t.r.n.]... .l...The benchmark needs 32GB (18GB for putting CIHAI into B-trees), I did it using SSD RAM and once again FNV1A-Totenschiff was faster than WYHASH:
-------------------------------------------------------------------------------------------------------------------------------------------------
| Hasher | Number Of Hash Collisions = | Number Of Trees, | Number Of LEAFs, (littler THE BETTER) |
| | (Distinct KEYs - Number Of Trees) | (GREATER THE BETTER) | not counting ROOT LEAFs |
-------------------------------------------------------------------------------------------------------------------------------------------------
| Lookuperorama_ICC_WY.exe, 24bit | 111,682,513 | 112,117,444 | 63,925,202 |
| Lookuperorama_ICC_Totenschiff.exe, 24bit | 111,833,260 | 111,966,697 | 64,085,673 |
-------------------------------------------------------------------------------------------------------------------------------------------------
| Lookuperorama_ICC_WY.exe, 25bit | 71,345,349 | 152,454,608 | 29,983,843 |
| Lookuperorama_ICC_Totenschiff.exe, 25bit | 71,536,395 | 152,263,562 | 30,180,703 |
-------------------------------------------------------------------------------------------------------------------------------------------------
| Lookuperorama_ICC_WY.exe, 26bit | 41,105,637 | 182,694,320 | 10,761,252 |
| Lookuperorama_ICC_Totenschiff.exe, 26bit | 41,265,947 | 182,534,010 | 10,874,209 |
-------------------------------------------------------------------------------------------------------------------------------------------------You are right. The measurement results are misleading for many practical use cases, esp. we'd need to test more common keys, and the I-cache effects. Used in hashtables, FNV or other simple mult. hashes are far better than the big and good hash functions. They should only be used in databased or file digests. I don't use wyhash or t1ha0, rather the simpliest FNV1. java similar. E.g. Spooky is esp. good avoiding collisions with common keys. But that's already described in the docs. I thought about adding a better practical test, and the codesize.
Being bad means that it fails all of the smhasher tests. Esp. the security relevant ones.
dumblob
commented
4 years ago @Sanmayce I can't agree with some of the preconditions you mentioned (e.g. that the performance on mainstream CPUs doesn't matter much or that performance/latency on keys of e.g. 33 or more bytes doesn't matter either), but I fully agree, that SMhasher doesn't show anything else then collision quality (yeah, SMhasher doesn't show anything meaningful regarding speed & latency).
@Sanmayce please be so kind and take a thorough look at http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html presenting in my opinion the currently best hash algorithm in the world and run the full benchmark suite (available under https://github.com/Cyan4973/xxHash/tree/dev/tests/bench ) as well as the updated SMhasher https://github.com/Cyan4973/smhasher (it's actually already merged in this repo, but just for case there are some newer differences) on all your computers.
Then I'm really interested whether FNV1A_Yorikke (or its variants) is at least 1.1x better than XXH3 for keys larger or equal to 3 bytes (smaller keys don't make much sense - you're better off building a fixed-size data structure like an array).
rurban
commented
4 years ago Nice, didn't know of these benchmark improvements. (or forgot) I only know of demerq's test improvements with gsl. Will have a look.
erthink
commented
4 years ago rurban
commented
4 years ago @leo-yuriev: OMG, benchmarking is really hard! mera looks good
Sanmayce
commented
4 years ago @rurban
That's right. You nailed it. I challenge all coders to outspeed FNV1A-Totenschiff, if they do, we all can enjoy a better understanding, function and benchmark experience. To me playing with lookup-table hashers is all about fun and finding higher granularities of that simple code that inherently makes FNV superb.
@dumblob
e.g. that the performance on mainstream CPUs doesn't matter much or that performance/latency on keys of e.g. 33 or more bytes doesn't matter either
I stand corrected a bit, as always I am a bit marginal, I just hate having a 64bit architecture and be "awarded" with penalties for fething with its native order :( What I really want to see is an English n-gram hasher able to hash in FASTEST mode billions of keys like: 1-gram: word1 2-gram: word1_word2 ... 9-gram: word1_word2_word3_word4_word5_word6_word7_word8_word9
Being in range 1..100 bytes.
Then I'm really interested whether FNV1A_Yorikke (or its variants) is at least 1.1x better than XXH3 for keys larger or equal to 3 bytes (smaller keys don't make much sense - you're better off building a fixed-size data structure like an array).
That's the idea, to throw Yorikke and Totenschiff against best hashers and measure MOSTLY speed and dispersion, for small keys. Thank you for Yann's bench folder, didn't know of it. I am reluctant to use his bench or hashes just because he could do it as it should, I would probably mess or misuse something. His latest v3 (AFAIU targeting small keys) is in some development stage which adds to that fact - my wish Yann or another professional is to include FNV1A-Totenschiff (targeting small keys) into their bench suites. It would be an interesting showdown.
Guys, thank you for sharing your views, I always enjoy seeing things from different angles, let me tell you what I intend to write at the end of the week (no time atm). Will add a simple section before current one that uses each slot for a root of a B-tree, in Lookuperorama r.5 we will have two approaches being run back-to-back - for a given file and a hashtable size, will do one pass to determine Collisions while also reporting the slot containing MAX collisions, after that will run again for each position WYHASH and Totenschiff, 5 times without touching the slots (to avoid random, heh-heh, RAM accesses) - only hashing. Will add resultant hashes to a DUMMY variable, you know. Will report the MIN value of clocks elapsed. I intend to do it for all keys in range 1..64, or 64 reporting lines as these, for '1001 Nights':
24bit, RAW Hashing ~15,000,000 keys of size 01 ... [Collisions] [MAX Collisions at some slot] time1 time2 time3 time4 time5 [MIN time in clocks] [Keys-per-second]
...
24bit, RAW Hashing ~15,000,000 keys of size 64 ... [Collisions] [MAX Collisions at some slot] time1 time2 time3 time4 time5 [MIN time in clocks] [Keys-per-second]It is 20 minutes away to write it, but I need time also to benchmark Shakespeare, 1001 Nights, CIHAI_Sea-Of-Words, enwik8, also @dumblob in order to amend my mistake I intend to make a roster with three columns:
27bit hashtable, testfile: enwik8 (100,000,000 bytes)
-------------------------------------
| RAW Hashing Speed, in Keys/s on: |
-------------------------------------
| i5-2430M | i7-3630QM | i5-7200U |
-----------------------------------------------------
Keys 01 bytes | xx,xxx,xxx |
... |
Keys 64 bytes |
-----------------------------------------------------@Sanmayce wrote:
I am reluctant to use his bench or hashes just because he could do it as it should, I would probably mess or misuse something.
No, you wouldn't mess anything. It's super easy to use his benchmarks and they're very objective and really do test hashing "at scale" (I really liked the "latency" tests as they're how hashing is being used in majority of cases). By default it uses randomly pre-generated dictionaries, but hey, it's super easy to add arbitrary n-gram dictionaries for many languages (French, German, English, Czech, Polish, Chinese, etc.). I bet it's easier to modify his benchmark then writing your own benchmark (which'll likely have some flaws as benchmarking is really hard - see some points in mera and in the blog post.
And by the way, XXH3 seems functionally pretty stable now, though still without the guarantee of exact same hash outputs across different releases. So don't let yourself go astray and do the fair comparison. We're really eager to see the comparable benchmarking results.
Sanmayce
commented
4 years ago Thank you @dumblob, I will include XXH3 into Lookuperorama r.6, until then I want to enrich my own reporting versatility... As for using Leo's or/and Yann's benches, still don't want to mess with them, as the ancient Chinese proverb goes, I prefer to play "guest" instead of "host".
As I announced in my latest PDF booklets, I expected Totenschiff to be beaten by dualheading it, in Yoshimura fashion, the result is FNV1A-Pippip - the fastest known to me lookuper.
UINT Hash_Pippip(const char *str, SIZE_T wrdlen)
{
const UINT PRIME = 591798841;
UINT hash32 = 2166136261;
long long hash64 = 14695981039346656037;//2166136261;
const char *p = str;
int i, Cycles, NDhead;
if (wrdlen >8) {
Cycles = ((wrdlen - 1)>>4) + 1;
NDhead = wrdlen - (Cycles<<3);
for(i=0; i<Cycles; i++) {
hash64 = ( hash64 ^ (*(long long *)(p)) ) * PRIME;
hash64 = ( hash64 ^ (*(long long *)(p+NDhead)) ) * PRIME;
p += 8;
}
} else
hash64 = ( hash64 ^ _PADr_KAZE(*(long long *)(p+0), (8-wrdlen)<<3) ) * PRIME;
hash32 = (UINT)(hash64 ^ (hash64>>32));
return hash32 ^ (hash32 >> 16);
}And some visualization:
/*
kl= 9..16 Cycles= (kl-1)/16+1=1; MARGINAL CASES:
2nd head starts at 9-1*8=1 or:
012345678
Head1: [Q-WORD]
Head2: [Q-WORD]
2nd head starts at 16-1*8=8 or:
0123456789012345
Head1: [Q-WORD]
Head2: [Q-WORD]
kl=17..24 Cycles= (kl-1)/16+1=2; MARGINAL CASES:
2nd head starts at 17-2*8=1 or:
01234567890123456
Head1: [Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD]
2nd head starts at 24-2*8=8 or:
012345678901234567890123
Head1: [Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD]
kl=25..32 Cycles= (kl-1)/16+1=2; MARGINAL CASES:
2nd head starts at 25-2*8=9 or:
0123456789012345678901234
Head1: [Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD]
2nd head starts at 32-2*8=16 or:
01234567890123456789012345678901
Head1: [Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD]
kl=33..40 Cycles= (kl-1)/16+1=3; MARGINAL CASES:
2nd head starts at 33-3*8=9 or:
012345678901234567890123456789012
Head1: [Q-WORD][Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD][Q-WORD]
2nd head starts at 40-3*8=16 or:
0123456789012345678901234567890123456789
Head1: [Q-WORD][Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD][Q-WORD]
kl=41..48 Cycles= (kl-1)/16+1=3; MARGINAL CASES:
2nd head starts at 41-3*8=17 or:
01234567890123456789012345678901234567890
Head1: [Q-WORD][Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD][Q-WORD]
2nd head starts at 48-3*8=24 or:
012345678901234567890123456789012345678901234567
Head1: [Q-WORD][Q-WORD][Q-WORD]
Head2: [Q-WORD][Q-WORD][Q-WORD]
*/Pippip is the main character in the 'Das Totenschiff' roman, actually the B.Traven himself, his real name was Hermann Albert Otto Maksymilian Feige.
The quick overview on i7-3630QM using Intel v15.0 64bit:
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_IPS_(3_million_IPs_dot_format).TXT"
2995394 lines read
8388608 elements in the table (23 bits)
Jesteress: 560466 [691369]
Meiyan: 547413 [593723]
Pippip: 478514 [476410]
Totenschiff: 558825 [476467]
Yorikke: 629444 [506954]
Yoshimura: 487776 [476699]
wyhash: 618294 [476412]
YoshimitsuTRIAD: 547195 [476699]
FNV-1a: 686416 [477067]
Larson: 674886 [475575]
CRC-32: 665523 [472854]
Murmur2: 652045 [476330]
Murmur3: 643288 [476845]
XXHfast32: 689423 [476358]
XXHstrong32: 698049 [476358]
iSCSI CRC: 408198 [479542]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_Word-list_12,561,874_wikipedia-en-html.tar.wrd"
12561874 lines read
33554432 elements in the table (25 bits)
Jesteress: 2529483 [2121868]
Meiyan: 2569892 [2111271]
Pippip: 2180057 [2084750]
Totenschiff: 2400019 [2084381]
Yorikke: 2527984 [2099673]
Yoshimura: 2316988 [2086155]
wyhash: 2847411 [2081865]
YoshimitsuTRIAD: 2604040 [2084931]
FNV-1a: 3089878 [2081195]
Larson: 2968283 [2080111]
CRC-32: 3150877 [2075088]
Murmur2: 3054371 [2081476]
Murmur3: 2842999 [2082084]
XXHfast32: 3158531 [2084164]
XXHstrong32: 3203936 [2084514]
iSCSI CRC: 2080711 [2077725]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_www.byronknoll.com_cmix-v18.zip_english.dic"
44880 lines read
131072 elements in the table (17 bits)
Jesteress: 3976 3433 3452 3418 3340 3350 3418 3411 3465 3401| 3340 [ 6721]
Meiyan: 3668 3611 3484 3476 3477 3484 3482 3483 3483 3481| 3476 [ 6923]
Pippip: 2179 2168 2220 2162 2163 2161 2162 2160 2399 2213| 2160 [ 6822]
Totenschiff: 2324 2303 2303 2304 2301 2306 2308 2303 2301 2292| 2292 [ 6818]
Yorikke: 2412 2410 2487 2765 2521 2539 2481 2409 2514 2520| 2409 [ 6883]
Yoshimura: 3317 3275 3215 3192 3116 3235 3195 3194 3112 3161| 3112 [ 7013]
wyhash: 3812 3777 3782 3745 3995 3835 3847 3776 3770 3807| 3745 [ 6812]
YoshimitsuTRIAD: 3593 3579 3576 3511 3576 3518 3554 3596 3569 3864| 3511 [ 7006]
FNV-1a: 3682 3665 3628 3736 3670 3624 3672 3617 3609 3605| 3605 [ 6833]
Larson: 3660 3624 3724 3699 3767 3663 3623 3623 3626 3645| 3623 [ 6830]
CRC-32: 3855 3807 3774 3781 3808 3806 3806 3809 3993 3839| 3774 [ 6891]
Murmur2: 4009 4033 3932 3992 3916 3914 3907 3889 3879 3878| 3878 [ 6820]
Murmur3: 3685 3680 3896 3723 3760 3680 3756 3662 3626 3664| 3626 [ 6874]
XXHfast32: 4121 4100 4088 4109 4033 4024 4403 4161 4130 4093| 4024 [ 6812]
XXHstrong32: 4157 4188 4166 4132 4057 4057 4101 4111 4101 4333| 4057 [ 6819]
iSCSI CRC: 3079 3030 2996 2994 2996 3032 2991 2994 2989 2989| 2989 [ 6785]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_www.gutenberg.org_ebooks_100.txt"
138578 lines read
524288 elements in the table (19 bits)
Jesteress: 22806 [31211]
Meiyan: 23530 [31116]
Pippip: 17974 [31196]
Totenschiff: 20903 [31134]
Yorikke: 24855 [31139]
Yoshimura: 19364 [31245]
wyhash: 27685 [31260]
YoshimitsuTRIAD: 27367 [31316]
FNV-1a: 44494 [31178]
Larson: 42414 [31406]
CRC-32: 40815 [31210]
Murmur2: 29510 [31203]
Murmur3: 29077 [31308]
XXHfast32: 24227 [31146]
XXHstrong32: 27233 [31118]
iSCSI CRC: 20156 [31248]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_www.maximumcompression.com_english.dic"
354951 lines read
1048576 elements in the table (20 bits)
Jesteress: 53770 [53809]
Meiyan: 54079 [54013]
Pippip: 43883 [53393]
Totenschiff: 49029 [53546]
Yorikke: 51853 [53782]
Yoshimura: 48192 [53768]
wyhash: 60654 [53996]
YoshimitsuTRIAD: 54965 [53658]
FNV-1a: 64787 [53896]
Larson: 63786 [54076]
CRC-32: 66778 [54020]
Murmur2: 65227 [53857]
Murmur3: 60770 [53983]
XXHfast32: 67921 [53411]
XXHstrong32: 68886 [53391]
iSCSI CRC: 43381 [53915]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash "KAZE_google-10000-english-no-swears.txt"
9894 lines read
32768 elements in the table (15 bits)
Jesteress: 746 [ 1345]
Meiyan: 768 [ 1373]
Pippip: 409 [ 1335]
Totenschiff: 424 [ 1377]
Yorikke: 425 [ 1371]
Yoshimura: 685 [ 1367]
wyhash: 798 [ 1397]
YoshimitsuTRIAD: 765 [ 1365]
FNV-1a: 734 [ 1336]
Larson: 733 [ 1388]
CRC-32: 782 [ 1310]
Murmur2: 812 [ 1311]
Murmur3: 769 [ 1374]
XXHfast32: 866 [ 1320]
XXHstrong32: 871 [ 1320]
iSCSI CRC: 641 [ 1344]
G:\PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Yorikke-v4>hash enwiki-20190920-pages-articles.xml.SORTED.wrd /s26
42206534 lines read
67108864 elements in the table (26 bits)
Jesteress: 9923330 [10951272]
Meiyan: 10187692 [10882580]
Pippip: 8722431 [10877849]
Totenschiff: 9467037 [10879917]
Yorikke: 9835901 [10901270]
Yoshimura: 9323442 [10880141]
wyhash: 11455649 [10880658]
YoshimitsuTRIAD: 10591426 [10880607]
FNV-1a: 11977002 [10869907]
Larson: 11268528 [10784384]
CRC-32: 12215826 [10660795]
Murmur2: 12042906 [10878271]
Murmur3: 11232405 [10877179]
XXHfast32: 12428356 [10891559]
XXHstrong32: 12590645 [10891549]
iSCSI CRC: 8210652 [10693843]I fully expect Pippip to better significantly Totenschiff's results in Lookuperorama...
Sanmayce
commented
4 years ago Okay, wanted to quickly share results from Peter's benchmark before full embarking. Currently, 18 testfiles in use, will share them in a .ZIP package later on, when all is done. The executable, produced with latest Intel v19.0 compiler, 64bit. The testmachines used, my main one - 'Compressionette' with i5-7200U @3.1GHz and her sidekick - 'Ragella' with i7-3630QM @3.4GHz:
Kaby Lake in action:
dic_common_words.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 15 [ 110]
Meiyan: 13 [ 102]
Pippip: 13 [ 110] ! On par with iSCSI CRC !
Totenschiff: 15 [ 105]
Yorikke: 15 [ 106]
Yoshimura: 14 [ 109]
wyhash: 40 [ 110]
YoshimitsuTRIAD: 19 [ 108]
FNV-1a: 21 [ 124]
Larson: 27 [ 99]
CRC-32: 18 [ 101]
Murmur2: 23 [ 103]
Murmur3: 19 [ 101]
XXHfast32: 23 [ 110]
XXHstrong32: 23 [ 109]
iSCSI CRC: 13 [ 105]
dic_fr.txt:
13408 lines read
32768 elements in the table (15 bits)
Jesteress: 1124 [ 2427]
Meiyan: 1138 [ 2377]
Pippip: 740 [ 2421] ! We all love France !
Totenschiff: 776 [ 2377]
Yorikke: 800 [ 2412]
Yoshimura: 1169 [ 2392]
wyhash: 1286 [ 2366]
YoshimitsuTRIAD: 1206 [ 2392]
FNV-1a: 1271 [ 2446]
Larson: 1288 [ 2447]
CRC-32: 1292 [ 2400]
Murmur2: 1305 [ 2399]
Murmur3: 1294 [ 2376]
XXHfast32: 1399 [ 2494]
XXHstrong32: 1428 [ 2496]
iSCSI CRC: 1089 [ 2388]
dic_ip.txt:
3925 lines read
8192 elements in the table (13 bits)
Jesteress: 169 [ 819]
Meiyan: 169 [ 807]
Pippip: 148 [ 856] ! Eh, the power of ARGUS Gold deep-metallic-green beer cans !
Totenschiff: 156 [ 803]
Yorikke: 165 [ 791]
Yoshimura: 179 [ 821]
wyhash: 243 [ 793]
YoshimitsuTRIAD: 203 [ 821]
FNV-1a: 305 [ 796]
Larson: 298 [ 789]
CRC-32: 258 [ 802]
Murmur2: 250 [ 825]
Murmur3: 252 [ 818]
XXHfast32: 309 [ 829]
XXHstrong32: 316 [ 829]
iSCSI CRC: 167 [ 795]
dic_numbers.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 17 [ 300]
Meiyan: 14 [ 125]
Pippip: 13 [ 116] ! iSCSI CRC is no slouch !
Totenschiff: 14 [ 116]
Yorikke: 14 [ 82]
Yoshimura: 16 [ 86]
wyhash: 23 [ 120]
YoshimitsuTRIAD: 19 [ 86]
FNV-1a: 16 [ 108]
Larson: 14 [ 16]
CRC-32: 14 [ 64]
Murmur2: 17 [ 104]
Murmur3: 17 [ 104]
XXHfast32: 23 [ 102]
XXHstrong32: 24 [ 102]
iSCSI CRC: 12 [ 112]
dic_postfix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 20 [ 106]
Meiyan: 19 [ 112]
Pippip: 19 [ 115]
Totenschiff: 20 [ 100]
Yorikke: 26 [ 100]
Yoshimura: 20 [ 112]
wyhash: 46 [ 103]
YoshimitsuTRIAD: 23 [ 103]
FNV-1a: 82 [ 105]
Larson: 83 [ 105]
CRC-32: 53 [ 94]
Murmur2: 36 [ 111]
Murmur3: 38 [ 105]
XXHfast32: 29 [ 106]
XXHstrong32: 33 [ 112]
iSCSI CRC: 25 [ 92]
dic_prefix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 21 [ 102]
Meiyan: 18 [ 106]
Pippip: 18 [ 110]
Totenschiff: 20 [ 98]
Yorikke: 25 [ 92]
Yoshimura: 19 [ 109]
wyhash: 45 [ 109]
YoshimitsuTRIAD: 23 [ 101]
FNV-1a: 81 [ 94]
Larson: 83 [ 99]
CRC-32: 54 [ 107]
Murmur2: 35 [ 106]
Murmur3: 40 [ 103]
XXHfast32: 29 [ 103]
XXHstrong32: 34 [ 102]
iSCSI CRC: 25 [ 106]
dic_Shakespeare.txt:
3228 lines read
8192 elements in the table (13 bits)
Jesteress: 228 [ 585]
Meiyan: 228 [ 588]
Pippip: 108 [ 577] ! Pippip is a Shakespearian, after calling an Olympic favorite - an Olympian !
Totenschiff: 112 [ 589]
Yorikke: 114 [ 536]
Yoshimura: 221 [ 552]
wyhash: 270 [ 599]
YoshimitsuTRIAD: 239 [ 552]
FNV-1a: 232 [ 555]
Larson: 251 [ 583]
CRC-32: 241 [ 563]
Murmur2: 259 [ 566]
Murmur3: 239 [ 555]
XXHfast32: 252 [ 491]
XXHstrong32: 263 [ 491]
iSCSI CRC: 205 [ 584]
dic_variables.txt:
1842 lines read
4096 elements in the table (12 bits)
Jesteress: 139 [ 366]
Meiyan: 140 [ 350]
Pippip: 84 [ 357] ! Hm, no idea why Totenschiff is ahead !
Totenschiff: 82 [ 366]
Yorikke: 95 [ 350]
Yoshimura: 142 [ 356]
wyhash: 163 [ 372]
YoshimitsuTRIAD: 156 [ 361]
FNV-1a: 163 [ 374]
Larson: 178 [ 366]
CRC-32: 164 [ 338]
Murmur2: 168 [ 383]
Murmur3: 164 [ 334]
XXHfast32: 169 [ 347]
XXHstrong32: 173 [ 355]
iSCSI CRC: 144 [ 368]
KAZE_www.byronknoll.com_cmix-v18.zip_english.dic:
44880 lines read
131072 elements in the table (17 bits)
Jesteress: 3717 [ 6721]
Meiyan: 3765 [ 6923]
Pippip: 2463 [ 6822] ! Screaming speed !
Totenschiff: 2619 [ 6818]
Yorikke: 2674 [ 6883]
Yoshimura: 3868 [ 7013]
wyhash: 4371 [ 6812]
YoshimitsuTRIAD: 4035 [ 7006]
FNV-1a: 4283 [ 6833]
Larson: 4297 [ 6830]
CRC-32: 4342 [ 6891]
Murmur2: 4393 [ 6820]
Murmur3: 4320 [ 6874]
XXHfast32: 4573 [ 6812]
XXHstrong32: 4660 [ 6819]
iSCSI CRC: 3600 [ 6785]
KAZE_3333_Latin_Powers.TXT:
3333 lines read
8192 elements in the table (13 bits)
Jesteress: 200 [ 576]
Meiyan: 193 [ 583]
Pippip: 142 [ 560] ! Fun fact, this list I created thanks to the FNV co-creator Landon Curt Noll, he taught me to count to 1000^3333 !
Totenschiff: 163 [ 602]
Yorikke: 195 [ 573]
Yoshimura: 148 [ 593]
wyhash: 271 [ 595]
YoshimitsuTRIAD: 215 [ 615]
FNV-1a: 545 [ 604]
Larson: 538 [ 581]
CRC-32: 404 [ 613]
Murmur2: 274 [ 600]
Murmur3: 304 [ 583]
XXHfast32: 219 [ 596]
XXHstrong32: 251 [ 571]
iSCSI CRC: 216 [ 594]
"KAZE_IPS_(3_million_IPs_dot_format).TXT":
2995394 lines read
8388608 elements in the table (23 bits)
Jesteress: 474679 [691369]
Meiyan: 462598 [593723]
Pippip: 448245 [476410] ! Second-best and IP-friendly, yet, iSCSI CRC dominates !
Totenschiff: 512067 [476467]
Yorikke: 530303 [506954]
Yoshimura: 458850 [476699]
wyhash: 551987 [476412]
YoshimitsuTRIAD: 487543 [476699]
FNV-1a: 714983 [477067]
Larson: 700898 [475575]
CRC-32: 601263 [472854]
Murmur2: 584166 [476330]
Murmur3: 577785 [476845]
XXHfast32: 672860 [476358]
XXHstrong32: 691955 [476358]
iSCSI CRC: 397506 [479542]
"KAZE_Word-list_12,561,874_wikipedia-en-html.tar.wrd":
12561874 lines read
33554432 elements in the table (25 bits)
Jesteress: 2329533 [2121868]
Meiyan: 2370754 [2111271]
Pippip: 2143388 [2084750] ! iSCSI CRC in the mirror, are you kidding me, what a beautiful brutality !
Totenschiff: 2300133 [2084381]
Yorikke: 2367380 [2099673]
Yoshimura: 2387889 [2086155]
wyhash: 2790935 [2081865]
YoshimitsuTRIAD: 2517971 [2084931]
FNV-1a: 3119297 [2081195]
Larson: 3017590 [2080111]
CRC-32: 2976146 [2075088]
Murmur2: 2858856 [2081476]
Murmur3: 2864098 [2082084]
XXHfast32: 3084063 [2084164]
XXHstrong32: 3191575 [2084514]
iSCSI CRC: 2155141 [2077725]
KAZE_www.gutenberg.org_ebooks_100.txt:
138578 lines read
524288 elements in the table (19 bits)
Jesteress: 24068 [31211]
Meiyan: 24292 [31116]
Pippip: 18195 [31196] ! Commentless I am !
Totenschiff: 20313 [31134]
Yorikke: 23758 [31139]
Yoshimura: 19469 [31245]
wyhash: 28252 [31260]
YoshimitsuTRIAD: 27014 [31316]
FNV-1a: 49282 [31178]
Larson: 48770 [31406]
CRC-32: 41691 [31210]
Murmur2: 31558 [31203]
Murmur3: 31336 [31308]
XXHfast32: 24637 [31146]
XXHstrong32: 27266 [31118]
iSCSI CRC: 22487 [31248]
KAZE_www.maximumcompression.com_english.dic:
354951 lines read
1048576 elements in the table (20 bits)
Jesteress: 49889 [53809]
Meiyan: 50868 [54013]
Pippip: 44669 [53393] ! Fastest on all major English words, a tear is falling !
Totenschiff: 48633 [53546]
Yorikke: 49951 [53782]
Yoshimura: 51929 [53768]
wyhash: 61668 [53996]
YoshimitsuTRIAD: 54825 [53658]
FNV-1a: 68106 [53896]
Larson: 67358 [54076]
CRC-32: 64756 [54020]
Murmur2: 62863 [53857]
Murmur3: 62782 [53983]
XXHfast32: 68146 [53411]
XXHstrong32: 70334 [53391]
iSCSI CRC: 46122 [53915]
KAZE_enwiki-20190920-pages-articles.xml.SORTED.wrd:
42206534 lines read
134217728 elements in the table (27 bits)
Jesteress: 9146818 [6011292]
Meiyan: 9366734 [5985680]
Pippip: 8738860 [5996107] ! Sometimes everything is not enough, iSCSI CRC beats Pippip here !
Totenschiff: 9247267 [5996598]
Yorikke: 9259923 [6011605]
Yoshimura: 9615957 [5991798]
wyhash: 11266553 [5991525]
YoshimitsuTRIAD: 10128023 [5992635]
FNV-1a: 11971535 [5980248]
Larson: 10988784 [5937238]
CRC-32: 11521822 [5843653]
Murmur2: 11335924 [5991065]
Murmur3: 11310589 [5992379]
XXHfast32: 12003125 [6008154]
XXHstrong32: 12378082 [6007552]
iSCSI CRC: 8424769 [5803092]And for good measure Ivy Bridge's results:
dic_common_words.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 15 [ 110]
Meiyan: 18 [ 102]
Pippip: 17 [ 110] ! Grmbl, Kaby Lake favors Pippip !
Totenschiff: 16 [ 105]
Yorikke: 16 [ 106]
Yoshimura: 18 [ 109]
wyhash: 36 [ 110]
YoshimitsuTRIAD: 22 [ 108]
FNV-1a: 22 [ 124]
Larson: 29 [ 99]
CRC-32: 21 [ 101]
Murmur2: 19 [ 103]
Murmur3: 20 [ 101]
XXHfast32: 27 [ 110]
XXHstrong32: 25 [ 109]
iSCSI CRC: 14 [ 105]
dic_fr.txt:
13408 lines read
32768 elements in the table (15 bits)
Jesteress: 884 [ 2427]
Meiyan: 898 [ 2377]
Pippip: 649 [ 2421] ! The nice one !
Totenschiff: 663 [ 2377]
Yorikke: 690 [ 2412]
Yoshimura: 935 [ 2392]
wyhash: 1101 [ 2366]
YoshimitsuTRIAD: 973 [ 2392]
FNV-1a: 1064 [ 2446]
Larson: 1097 [ 2447]
CRC-32: 1068 [ 2400]
Murmur2: 1056 [ 2399]
Murmur3: 1051 [ 2376]
XXHfast32: 1172 [ 2494]
XXHstrong32: 1144 [ 2496]
iSCSI CRC: 873 [ 2388]
dic_ip.txt:
3925 lines read
8192 elements in the table (13 bits)
Jesteress: 161 [ 819]
Meiyan: 169 [ 807]
Pippip: 150 [ 856] ! Hm, no idea why Totenschiff is ahead !
Totenschiff: 149 [ 803]
Yorikke: 161 [ 791]
Yoshimura: 179 [ 821]
wyhash: 243 [ 793]
YoshimitsuTRIAD: 202 [ 821]
FNV-1a: 282 [ 796]
Larson: 281 [ 789]
CRC-32: 264 [ 802]
Murmur2: 223 [ 825]
Murmur3: 239 [ 818]
XXHfast32: 280 [ 829]
XXHstrong32: 280 [ 829]
iSCSI CRC: 160 [ 795]
dic_numbers.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 19 [ 300]
Meiyan: 17 [ 125]
Pippip: 15 [ 116] ! Yorikke is ahead a bit !
Totenschiff: 15 [ 116]
Yorikke: 14 [ 82]
Yoshimura: 19 [ 86]
wyhash: 26 [ 120]
YoshimitsuTRIAD: 22 [ 86]
FNV-1a: 16 [ 108]
Larson: 15 [ 16]
CRC-32: 17 [ 64]
Murmur2: 18 [ 104]
Murmur3: 18 [ 104]
XXHfast32: 23 [ 102]
XXHstrong32: 23 [ 102]
iSCSI CRC: 15 [ 112]
dic_postfix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 20 [ 106]
Meiyan: 23 [ 112]
Pippip: 19 [ 115]
Totenschiff: 21 [ 100]
Yorikke: 27 [ 100]
Yoshimura: 21 [ 112]
wyhash: 43 [ 103]
YoshimitsuTRIAD: 25 [ 103]
FNV-1a: 72 [ 105]
Larson: 77 [ 105]
CRC-32: 61 [ 94]
Murmur2: 34 [ 111]
Murmur3: 39 [ 105]
XXHfast32: 29 [ 106]
XXHstrong32: 32 [ 112]
iSCSI CRC: 25 [ 92]
dic_prefix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 20 [ 102]
Meiyan: 22 [ 106]
Pippip: 19 [ 110]
Totenschiff: 20 [ 98]
Yorikke: 27 [ 92]
Yoshimura: 21 [ 109]
wyhash: 43 [ 109]
YoshimitsuTRIAD: 26 [ 101]
FNV-1a: 74 [ 94]
Larson: 79 [ 99]
CRC-32: 62 [ 107]
Murmur2: 34 [ 106]
Murmur3: 39 [ 103]
XXHfast32: 29 [ 103]
XXHstrong32: 33 [ 102]
iSCSI CRC: 26 [ 106]
dic_Shakespeare.txt:
3228 lines read
8192 elements in the table (13 bits)
Jesteress: 182 [ 585]
Meiyan: 183 [ 588]
Pippip: 113 [ 577] ! Let Shakespeariada begins !
Totenschiff: 116 [ 589]
Yorikke: 116 [ 536]
Yoshimura: 193 [ 552]
wyhash: 244 [ 599]
YoshimitsuTRIAD: 214 [ 552]
FNV-1a: 206 [ 555]
Larson: 218 [ 583]
CRC-32: 212 [ 563]
Murmur2: 214 [ 566]
Murmur3: 206 [ 555]
XXHfast32: 234 [ 491]
XXHstrong32: 223 [ 491]
iSCSI CRC: 179 [ 584]
dic_variables.txt:
1842 lines read
4096 elements in the table (12 bits)
Jesteress: 120 [ 366]
Meiyan: 119 [ 350]
Pippip: 82 [ 357]
Totenschiff: 89 [ 366]
Yorikke: 88 [ 350]
Yoshimura: 123 [ 356]
wyhash: 143 [ 372]
YoshimitsuTRIAD: 132 [ 361]
FNV-1a: 148 [ 374]
Larson: 162 [ 366]
CRC-32: 149 [ 338]
Murmur2: 138 [ 383]
Murmur3: 140 [ 334]
XXHfast32: 159 [ 347]
XXHstrong32: 151 [ 355]
iSCSI CRC: 122 [ 368]
KAZE_www.byronknoll.com_cmix-v18.zip_english.dic:
44880 lines read
131072 elements in the table (17 bits)
Jesteress: 2940 [ 6721]
Meiyan: 2988 [ 6923]
Pippip: 2128 [ 6822]
Totenschiff: 2189 [ 6818]
Yorikke: 2274 [ 6883]
Yoshimura: 3120 [ 7013]
wyhash: 3689 [ 6812]
YoshimitsuTRIAD: 3251 [ 7006]
FNV-1a: 3561 [ 6833]
Larson: 3646 [ 6830]
CRC-32: 3618 [ 6891]
Murmur2: 3542 [ 6820]
Murmur3: 3515 [ 6874]
XXHfast32: 3805 [ 6812]
XXHstrong32: 3742 [ 6819]
iSCSI CRC: 2893 [ 6785]
KAZE_3333_Latin_Powers.TXT:
3333 lines read
8192 elements in the table (13 bits)
Jesteress: 179 [ 576]
Meiyan: 184 [ 583]
Pippip: 145 [ 560] ! Latinophilia all the way !
Totenschiff: 163 [ 602]
Yorikke: 196 [ 573]
Yoshimura: 154 [ 593]
wyhash: 309 [ 595]
YoshimitsuTRIAD: 200 [ 615]
FNV-1a: 477 [ 604]
Larson: 481 [ 581]
CRC-32: 431 [ 613]
Murmur2: 248 [ 600]
Murmur3: 281 [ 583]
XXHfast32: 213 [ 596]
XXHstrong32: 236 [ 571]
iSCSI CRC: 194 [ 594]
"KAZE_IPS_(3_million_IPs_dot_format).TXT":
2995394 lines read
8388608 elements in the table (23 bits)
Jesteress: 496694 [691369]
Meiyan: 479529 [593723]
Pippip: 476112 [476410] ! Second-best and IP-friendly, yet, iSCSI CRC dominates again !
Totenschiff: 504529 [476467]
Yorikke: 545878 [506954]
Yoshimura: 476331 [476699]
wyhash: 610894 [476412]
YoshimitsuTRIAD: 500257 [476699]
FNV-1a: 669118 [477067]
Larson: 661395 [475575]
CRC-32: 639273 [472854]
Murmur2: 624035 [476330]
Murmur3: 623168 [476845]
XXHfast32: 657857 [476358]
XXHstrong32: 665029 [476358]
iSCSI CRC: 398902 [479542]
"KAZE_Word-list_12,561,874_wikipedia-en-html.tar.wrd":
12561874 lines read
33554432 elements in the table (25 bits)
Jesteress: 2241692 [2121868]
Meiyan: 2272542 [2111271]
Pippip: 2178470 [2084750] ! Ay-ay-ya, this time around 2nd to iSCSI CRC !
Totenschiff: 2282135 [2084381]
Yorikke: 2365470 [2099673]
Yoshimura: 2299264 [2086155]
wyhash: 2805367 [2081865]
YoshimitsuTRIAD: 2425637 [2084931]
FNV-1a: 3027965 [2081195]
Larson: 2932953 [2080111]
CRC-32: 3071583 [2075088]
Murmur2: 2823376 [2081476]
Murmur3: 2773854 [2082084]
XXHfast32: 3032854 [2084164]
XXHstrong32: 3058895 [2084514]
iSCSI CRC: 2037665 [2077725]
KAZE_www.gutenberg.org_ebooks_100.txt:
138578 lines read
524288 elements in the table (19 bits)
Jesteress: 21643 [31211]
Meiyan: 21940 [31116]
Pippip: 17559 [31196]
Totenschiff: 19093 [31134]
Yorikke: 21886 [31139]
Yoshimura: 18147 [31245]
wyhash: 26013 [31260]
YoshimitsuTRIAD: 24281 [31316]
FNV-1a: 41612 [31178]
Larson: 42924 [31406]
CRC-32: 40994 [31210]
Murmur2: 28858 [31203]
Murmur3: 28447 [31308]
XXHfast32: 23350 [31146]
XXHstrong32: 25654 [31118]
iSCSI CRC: 19798 [31248]
KAZE_www.maximumcompression.com_english.dic:
354951 lines read
1048576 elements in the table (20 bits)
Jesteress: 46021 [53809]
Meiyan: 46802 [54013]
Pippip: 43666 [53393] ! Ay-ay-ya, this time around 2nd to iSCSI CRC !
Totenschiff: 45871 [53546]
Yorikke: 47848 [53782]
Yoshimura: 47475 [53768]
wyhash: 58804 [53996]
YoshimitsuTRIAD: 50426 [53658]
FNV-1a: 62479 [53896]
Larson: 61968 [54076]
CRC-32: 63866 [54020]
Murmur2: 59155 [53857]
Murmur3: 58057 [53983]
XXHfast32: 64050 [53411]
XXHstrong32: 64319 [53391]
iSCSI CRC: 42131 [53915]
KAZE_enwiki-20190920-pages-articles.xml.SORTED.wrd:
42206534 lines read
134217728 elements in the table (27 bits)
Jesteress: 7535466 [6011292]
Meiyan: 7683208 [5985680]
Pippip: 7429496 [5996107] ! iSCSI CRC beats everyone with a margin here !
Totenschiff: 7754666 [5996598]
Yorikke: 7910662 [6011605]
Yoshimura: 7897196 [5991798]
wyhash: 9619451 [5991525]
YoshimitsuTRIAD: 8361802 [5992635]
FNV-1a: 10018813 [5980248]
Larson: 9488624 [5937238]
CRC-32: 10389536 [5843653]
Murmur2: 9413606 [5991065]
Murmur3: 9232074 [5992379]
XXHfast32: 10317317 [6008154]
XXHstrong32: 10423512 [6007552]
iSCSI CRC: 6959881 [5803092]Note: In order to minimize fluctuations, this time, I increased runs in Peter's hash.c from 10 to 40 for all testfiles with less than 400,000 lines:
//UINT repetitions = g_lines_count > 40000 ? 10 : 40; //Kaze was here, the line below increases the runs ... for more precise output.
UINT repetitions = g_lines_count > 400000 ? 10 : 40;@Sanmayce, could you add a few strong hash-functions as reference for a collisions rate?
For instance, 32-bits from any SHA-like hash and Pelle Evensen's mixer, i.e.
// New mixer, "rrxmrrxmsx_0", failing one subtest of RR-64-40-TF2-0.94.
// With a unit counter starting at 0, it has passed 128 TB of
// PractRand 0.94 -tf 2 without anomalies found past 2 TB.
uint64_t rrxmrrxmsx_0(uint64_t v) {
v ^= ror64(v, 25) ^ ror64(v, 50);
v *= 0xA24BAED4963EE407UL;
v ^= ror64(v, 24) ^ ror64(v, 49);
v *= 9FB21C651E98DF25UL;
return v ^ v >> 28;
}@leo-yuriev Sure- sure, more the merrier, just post the full hasherS here.
Sanmayce
commented
4 years ago @leo-yuriev I just don't have remote understanding how these mixer do their magic, therefore I need "ready-for-use" functions. For example, in Lookuperorama I have SHA3-224 included (unactive though), but have no idea how to transform these 224bits to 32bits, if you can do the final mixing for me, gladly will include it along with others. As for Peter's hash.c, there I have limited abilities to mess around, cannot compile it with GCC, for example.
erthink
commented
4 years ago @Sanmayce, for SHA you can get ANY 32-bit from it's result. For Pelle Evensen's mixer it is easy to construct the simple hash function:
#include <stdint.h>
#include <string.h>
static uint64_t rrxmrrxmsx_0(uint64_t v) {
/* Pelle Evensen's mixer, https://bit.ly/2HOfynt */
v ^= (v << 39 | v >> 25) ^ (v << 14 | v >> 50);
v *= UINT64_C(0xA24BAED4963EE407);
v ^= (v << 40 | v >> 24) ^ (v << 15 | v >> 49);
v *= UINT64_C(0x9FB21C651E98DF25);
return v ^ v >> 28;
}
uint64_t hash_based_on_Pelle_Evensen_mixer(const void *data, size_t bytes, uint64_t seed) {
uint64_t tmp, hash = rrxmrrxmsx_0(rrxmrrxmsx_0(seed) + bytes);
while(bytes >= sizeof(tmp)) {
memcpy(&tmp, data, sizeof(tmp));
data = (char*)data + sizeof(tmp);
hash = rrxmrrxmsx_0(hash + tmp);
bytes -= sizeof(tmp);
}
if (bytes) {
tmp = 0;
memcpy(&tmp, data, bytes);
hash = rrxmrrxmsx_0(hash + tmp);
}
return hash;
}It looks like a top-performer, already. Very nice article it is, after completion will ask Mr. Evensen for sharing a corpus of keys suitable for such deep tests.
Thank you @leo-yuriev, will include it in Lookuperorama r.5, maybe tomorrow night. Will put it in Peter's hash.c after an hour or so and will share here the results.
It is interesting to see how this mixer fares against the simplistic Pippip's endgame. And since I test only some up to 29bits, I am gonna take lowest 32 bits from its result as in SHA3-224, hope it is a good choice.
Excuse me for not grouping my posts into one, I use an old Windows XP and for some reason github/chrome refuse to allow me editing, putting pictures ... everything except 'Comment' button. A year ago the same machine had these features allowed.
Sanmayce
commented
4 years ago @leo-yuriev This is what I put into hash.c:
// https://github.com/rurban/smhasher/issues/73#issuecomment-543812950
static unsigned long long rrxmrrxmsx_0(unsigned long long v) {
// Pelle Evensen's mixer, https://bit.ly/2HOfynt
v ^= (v << 39 | v >> 25) ^ (v << 14 | v >> 50);
v *= (unsigned long long)(0xA24BAED4963EE407);
v ^= (v << 40 | v >> 24) ^ (v << 15 | v >> 49);
v *= (unsigned long long)(0x9FB21C651E98DF25);
return v ^ v >> 28;
}
UINT Hash_LeoPelle(const char *data, SIZE_T bytes)
{
unsigned long long tmp, hash = rrxmrrxmsx_0(rrxmrrxmsx_0(0) + bytes);
while(bytes >= sizeof(tmp)) {
memcpy(&tmp, data, sizeof(tmp));
data = (char*)data + sizeof(tmp);
hash = rrxmrrxmsx_0(hash + tmp);
bytes -= sizeof(tmp);
}
if (bytes) {
tmp = 0;
memcpy(&tmp, data, bytes);
hash = rrxmrrxmsx_0(hash + tmp);
}
return hash>>32; // Highest 32bit, Lowest 32bit, or folded - no time for checking 'em out
}And results on Kaby Lake:
dic_common_words.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 14 [ 110]
Meiyan: 19 [ 102]
Pippip: 13 [ 110]
Totenschiff: 15 [ 105]
Yorikke: 14 [ 106]
Yoshimura: 14 [ 109]
LeoPelle: 56 [ 104]
wyhash: 40 [ 110]
YoshimitsuTRIAD: 22 [ 108]
FNV-1a: 30 [ 124]
Larson: 29 [ 99]
CRC-32: 23 [ 101]
Murmur2: 17 [ 103]
Murmur3: 18 [ 101]
XXHfast32: 23 [ 110]
XXHstrong32: 24 [ 109]
iSCSI CRC: 12 [ 105]
dic_fr.txt:
13408 lines read
32768 elements in the table (15 bits)
Jesteress: 1127 [ 2427]
Meiyan: 1153 [ 2377]
Pippip: 729 [ 2421]
Totenschiff: 771 [ 2377]
Yorikke: 796 [ 2412]
Yoshimura: 1148 [ 2392]
LeoPelle: 1918 [ 2344] ! Best dispersion on French words !
wyhash: 1260 [ 2366]
YoshimitsuTRIAD: 1244 [ 2392]
FNV-1a: 1289 [ 2446]
Larson: 1286 [ 2447]
CRC-32: 1306 [ 2400]
Murmur2: 1282 [ 2399]
Murmur3: 1286 [ 2376]
XXHfast32: 1404 [ 2494]
XXHstrong32: 1441 [ 2496]
iSCSI CRC: 1104 [ 2388]
dic_ip.txt:
3925 lines read
8192 elements in the table (13 bits)
Jesteress: 173 [ 819]
Meiyan: 171 [ 807]
Pippip: 140 [ 856]
Totenschiff: 153 [ 803]
Yorikke: 164 [ 791]
Yoshimura: 179 [ 821]
LeoPelle: 561 [ 786] ! Best dispersion on IPs !
wyhash: 242 [ 793]
YoshimitsuTRIAD: 220 [ 821]
FNV-1a: 311 [ 796]
Larson: 300 [ 789]
CRC-32: 253 [ 802]
Murmur2: 230 [ 825]
Murmur3: 249 [ 818]
XXHfast32: 308 [ 829]
XXHstrong32: 315 [ 829]
iSCSI CRC: 166 [ 795]
dic_numbers.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 16 [ 300]
Meiyan: 14 [ 125]
Pippip: 13 [ 116]
Totenschiff: 14 [ 116]
Yorikke: 14 [ 82]
Yoshimura: 15 [ 86]
LeoPelle: 62 [ 104]
wyhash: 23 [ 120]
YoshimitsuTRIAD: 19 [ 86]
FNV-1a: 16 [ 108]
Larson: 14 [ 16]
CRC-32: 14 [ 64]
Murmur2: 17 [ 104]
Murmur3: 17 [ 104]
XXHfast32: 23 [ 102]
XXHstrong32: 23 [ 102]
iSCSI CRC: 10 [ 112]
dic_postfix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 20 [ 106]
Meiyan: 25 [ 112]
Pippip: 17 [ 115]
Totenschiff: 20 [ 100]
Yorikke: 25 [ 100]
Yoshimura: 19 [ 112]
LeoPelle: 81 [ 101]
wyhash: 45 [ 103]
YoshimitsuTRIAD: 28 [ 103]
FNV-1a: 84 [ 105]
Larson: 83 [ 105]
CRC-32: 55 [ 94]
Murmur2: 32 [ 111]
Murmur3: 40 [ 105]
XXHfast32: 29 [ 106]
XXHstrong32: 34 [ 112]
iSCSI CRC: 24 [ 92]
dic_prefix.txt:
500 lines read
1024 elements in the table (10 bits)
Jesteress: 22 [ 102]
Meiyan: 25 [ 106]
Pippip: 17 [ 110]
Totenschiff: 20 [ 98]
Yorikke: 26 [ 92]
Yoshimura: 20 [ 109]
LeoPelle: 83 [ 105]
wyhash: 46 [ 109]
YoshimitsuTRIAD: 29 [ 101]
FNV-1a: 84 [ 94]
Larson: 83 [ 99]
CRC-32: 55 [ 107]
Murmur2: 32 [ 106]
Murmur3: 40 [ 103]
XXHfast32: 29 [ 103]
XXHstrong32: 34 [ 102]
iSCSI CRC: 25 [ 106]
dic_Shakespeare.txt:
3228 lines read
8192 elements in the table (13 bits)
Jesteress: 212 [ 585]
Meiyan: 214 [ 588]
Pippip: 106 [ 577]
Totenschiff: 111 [ 589]
Yorikke: 106 [ 536]
Yoshimura: 223 [ 552]
LeoPelle: 391 [ 544]
wyhash: 263 [ 599]
YoshimitsuTRIAD: 249 [ 552]
FNV-1a: 249 [ 555]
Larson: 249 [ 583]
CRC-32: 239 [ 563]
Murmur2: 237 [ 566]
Murmur3: 239 [ 555]
XXHfast32: 252 [ 491]
XXHstrong32: 256 [ 491]
iSCSI CRC: 209 [ 584]
dic_variables.txt:
1842 lines read
4096 elements in the table (12 bits)
Jesteress: 142 [ 366]
Meiyan: 150 [ 350]
Pippip: 87 [ 357]
Totenschiff: 80 [ 366]
Yorikke: 84 [ 350]
Yoshimura: 140 [ 356]
LeoPelle: 240 [ 366]
wyhash: 160 [ 372]
YoshimitsuTRIAD: 161 [ 361]
FNV-1a: 181 [ 374]
Larson: 180 [ 366]
CRC-32: 166 [ 338]
Murmur2: 153 [ 383]
Murmur3: 161 [ 334]
XXHfast32: 168 [ 347]
XXHstrong32: 173 [ 355]
iSCSI CRC: 144 [ 368]
KAZE_www.byronknoll.com_cmix-v18.zip_english.dic:
44880 lines read
131072 elements in the table (17 bits)
Jesteress: 3729 [ 6721]
Meiyan: 3826 [ 6923]
Pippip: 2423 [ 6822]
Totenschiff: 2586 [ 6818]
Yorikke: 2651 [ 6883]
Yoshimura: 3807 [ 7013]
LeoPelle: 6938 [ 6908]
wyhash: 4281 [ 6812]
YoshimitsuTRIAD: 4146 [ 7006]
FNV-1a: 4351 [ 6833]
Larson: 4325 [ 6830]
CRC-32: 4396 [ 6891]
Murmur2: 4281 [ 6820]
Murmur3: 4292 [ 6874]
XXHfast32: 4567 [ 6812]
XXHstrong32: 4667 [ 6819]
iSCSI CRC: 3639 [ 6785]
KAZE_3333_Latin_Powers.TXT:
3333 lines read
8192 elements in the table (13 bits)
Jesteress: 202 [ 576]
Meiyan: 210 [ 583]
Pippip: 142 [ 560]
Totenschiff: 161 [ 602]
Yorikke: 196 [ 573]
Yoshimura: 155 [ 593]
LeoPelle: 566 [ 602]
wyhash: 263 [ 595]
YoshimitsuTRIAD: 232 [ 615]
FNV-1a: 551 [ 604]
Larson: 540 [ 581]
CRC-32: 407 [ 613]
Murmur2: 264 [ 600]
Murmur3: 303 [ 583]
XXHfast32: 226 [ 596]
XXHstrong32: 257 [ 571]
iSCSI CRC: 216 [ 594]
"KAZE_IPS_(3_million_IPs_dot_format).TXT":
2995394 lines read
8388608 elements in the table (23 bits)
Jesteress: 479224 [691369]
Meiyan: 464853 [593723]
Pippip: 448279 [476410]
Totenschiff: 516702 [476467]
Yorikke: 536163 [506954]
Yoshimura: 462728 [476699]
LeoPelle: 1377047 [476087]
wyhash: 557265 [476412]
YoshimitsuTRIAD: 494215 [476699]
FNV-1a: 721015 [477067]
Larson: 708784 [475575]
CRC-32: 604314 [472854]
Murmur2: 586309 [476330]
Murmur3: 581613 [476845]
XXHfast32: 677829 [476358]
XXHstrong32: 694420 [476358]
iSCSI CRC: 395067 [479542]
"KAZE_Word-list_12,561,874_wikipedia-en-html.tar.wrd":
12561874 lines read
33554432 elements in the table (25 bits)
Jesteress: 2333882 [2121868]
Meiyan: 2385505 [2111271]
Pippip: 2141209 [2084750]
Totenschiff: 2294174 [2084381]
Yorikke: 2367833 [2099673]
Yoshimura: 2375780 [2086155]
LeoPelle: 5581455 [2084471]
wyhash: 2799528 [2081865]
YoshimitsuTRIAD: 2536009 [2084931]
FNV-1a: 3134136 [2081195]
Larson: 3017962 [2080111]
CRC-32: 2994616 [2075088]
Murmur2: 2855417 [2081476]
Murmur3: 2860693 [2082084]
XXHfast32: 3085141 [2084164]
XXHstrong32: 3190057 [2084514]
iSCSI CRC: 2161231 [2077725]
KAZE_www.gutenberg.org_ebooks_100.txt:
138578 lines read
524288 elements in the table (19 bits)
Jesteress: 24192 [31211]
Meiyan: 24668 [31116]
Pippip: 18222 [31196]
Totenschiff: 20360 [31134]
Yorikke: 23712 [31139]
Yoshimura: 19543 [31245]
LeoPelle: 48454 [31372]
wyhash: 28113 [31260]
YoshimitsuTRIAD: 27275 [31316]
FNV-1a: 49301 [31178]
Larson: 49184 [31406]
CRC-32: 41684 [31210]
Murmur2: 31683 [31203]
Murmur3: 31564 [31308]
XXHfast32: 24667 [31146]
XXHstrong32: 27229 [31118]
iSCSI CRC: 22622 [31248]
KAZE_www.maximumcompression.com_english.dic:
354951 lines read
1048576 elements in the table (20 bits)
Jesteress: 50179 [53809]
Meiyan: 51489 [54013]
Pippip: 44641 [53393]
Totenschiff: 48526 [53546]
Yorikke: 50078 [53782]
Yoshimura: 51705 [53768]
LeoPelle: 120381 [53627]
wyhash: 61663 [53996]
YoshimitsuTRIAD: 55429 [53658]
FNV-1a: 68594 [53896]
Larson: 67472 [54076]
CRC-32: 65315 [54020]
Murmur2: 62624 [53857]
Murmur3: 62975 [53983]
XXHfast32: 68514 [53411]
XXHstrong32: 70636 [53391]
iSCSI CRC: 46514 [53915]
KAZE_enwiki-20190920-pages-articles.xml.SORTED.wrd:
42206534 lines read
134217728 elements in the table (27 bits)
Jesteress: 9193542 [6011292]
Meiyan: 9452745 [5985680]
Pippip: 8748221 [5996107]
Totenschiff: 9232164 [5996598]
Yorikke: 9269432 [6011605]
Yoshimura: 9597632 [5991798]
LeoPelle: 22517088 [5996503] ! Hm, I expected better dispersion for so many keys !
wyhash: 11240783 [5991525]
YoshimitsuTRIAD: 10191346 [5992635]
FNV-1a: 12012840 [5980248]
Larson: 11012405 [5937238]
CRC-32: 11593089 [5843653]
Murmur2: 11297683 [5991065]
Murmur3: 11319826 [5992379]
XXHfast32: 12025495 [6008154]
XXHstrong32: 12389242 [6007552]
iSCSI CRC: 8451327 [5803092]Thanks. The C source and the Intel v19.0 64bit binary is here: www.sanmayce.com/Fastest_Hash/PeterK_strchr.com_iSCSI-CRC_vs_WYHASH_vs_FNV1A-Pippip-v1.zip
Sanmayce
commented
4 years ago @dumblob
please be so kind and take a thorough look at http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html presenting in my opinion the currently best hash algorithm in the world and run the full benchmark suite (available under https://github.com/Cyan4973/xxHash/tree/dev/tests/bench ) ...
I did, here are the results:
Didn't have time to run it on all of my laptops, though.
We're really eager to see the comparable benchmarking results.
Sure, me too:
https://github.com/rurban/smhasher/issues/75#issuecomment-547900920 https://github.com/Cyan4973/xxHash/issues/275#issuecomment-546635300 https://github.com/rurban/smhasher/issues/75#issuecomment-548036030
dumblob
commented
4 years ago @Sanmayce thanks for letting me know - see my comment https://github.com/Cyan4973/xxHash/issues/275#issuecomment-548309597 .
Hi Reini, please consider taking a look at my latest-n-fastest etude - 'Yorikke':
The source code along with the superheavy (1 trillion unique keys) benchmark is freely downloadable at: www.sanmayce.com/Fastest_Hash/Knight-Tour_FNV1A_Yorikke_vs_CRC32_TRISMUS.zip
The quick overview: