All posts tagged "hashing"
Optimising Adler-32 checksum
The Adler-32 checksum consists of two 16-bit sums. One is the sum of all the bytes in the data, plus one, and the other is the sum of all those intermediate sums, which works out to be the same as the sum of all the bytes multiplied by their distance from the end of the buffer plus the length of the buffer. Both modulo 65521.
Hash map reduction operations
I notice that some defaults for things like STL
unordered_mapare a bit scary. The function to reduce the range of the hash down to the size of the table is remainder, and the default hash for integers is the identity function.A reasonably effective hash instruction
As per part one of this post, I have reasoned through and tested a proof of concept for generic CPU instruction which could achieve most of the required mixing of a good hash function in a single cycle (working with a combinational depth of 20 to 24 gates as a guide).
Why I want a dedicated hash instruction
A good hash function is expected to remove correlations of various sorts between subsets of inputs and their hashed outputs in order to mitigate the risk of those correlations producing performance aberrations (cache collisions, unbalanced structures, etc.) or statistical biases.
Idly musing over RowHammer mitigation strategies
Watching a RowHammer talk (slides) a while back (not actually the linked one, but I couldn’t find the one I attended) left me with a couple of thoughts about possible mitigations which I didn’t see discussed.
N-bit Mixer Functions
For reasons I intend (hah!) to go into in a longer post I was looking for operations with which to construct and whiten (or “finalise” or “mix” or “avalanche” or whatever) RNGs with 2n periods. I was looking at splitmix64 which led me to Fast splittable pseudorandom number generators which cited Improving on MurmurHash3’s 64-bit Finalizer (although I found that page by other means) and finally MurmurHash3 which tells me where those constants and that construction both come from.