so it turns out that knuth hash is the same as not hashing at all. Because the input is a random number from a fixed range, and I'm getting the hash index by masking the lower bits nothing much is going to improve the distribution.
-
Show this thread
-
I also realised that because the keys are ints the cost of a collision is very low (as opposed to for strings where a compare is expensive)
1 reply 0 retweets 0 likesShow this thread -
Replying to @stewartlynch8
If you're OK requiring AESNI:https://github.com/cmuratori/refterm/blob/91e932f011e12c02a6c609ac59570f5c19fe4727/refterm_example_source_buffer.c#L166 …
1 reply 0 retweets 2 likes -
Replying to @cmuratori @stewartlynch8
This one is perfect distribution, take any bits you want, ~1 byte per cycle. You can reduce the number of aesdecs if you want more speed and don't care about slightly more potential collisions (this one needed to _never_ collide).
1 reply 0 retweets 0 likes -
Replying to @cmuratori @stewartlynch8
These also overlap, so if you do multiple hashes at the same time, it goes from 1 byte per cycle to 4 bytes per cycle.
1 reply 0 retweets 0 likes -
-
Replying to @stewartlynch8
My recommendation to people is usually that if you can afford AESNI, try doing basically this routine but with only 2 aesdecs, and test the histogram for your data. If it's "good enough", then you're done. If it's not, add two more (like the routine given), and THEN you're done.
1 reply 0 retweets 0 likes -
Replying to @cmuratori @stewartlynch8
2 aesdecs is 8 cycles, but they overlap with everything else, too. So if you are doing something like just hashing a pointer, you can mov it into an xmm register, do the two aesdecs, and they _should_ overlap with other things you were doing if there's anything else to do.
1 reply 0 retweets 0 likes
So it can be _extremely_ efficient, almost negligible, and you get very good bit distribution.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.