This is not a full-blown hash function, just a mixer, like in murmur. It hashes only a single word, not a buffer. Haven't yet checked how good it is, but it's definitely a bit slower than fnv1, and faster than murmur. Will add it to smhasher soon, as soon as I get the unaligned part written. So far it doesn't look too good.
I will add that 32 bit version compiles quite nicely on arm. It's also what made me try something with this structure.
https://godbolt.org/z/abd79sEh1
As for x86/x86_64 processors compiling with a flag like -march=broadwell will remove quite few movs from the compiled code since the RORX instruction will be available which can take two register parameters, and a constant. Unlike the normal ROR instruction which is just a register and constant or the CL register for the rotation amount.
Now compared to functions that use multiplication. Multiplication can mix bits quite quickly. If the hardware multiplier is fast I don't think it would be faster with than fnv1 considering how simple that function is.
Not the GP, but in the sense that it can't be used to hash arbitrary (word-padded) data. This "hash" can only turn words into other words. A true hash function needs to produce a hash from a multi-word buffer, and do so in a way that all the data in the buffer is equally significant to the final hash value.
It can only take an input of fixed size and return an output of the same size.
"True" hash functions take an input buffer of an arbitrary size, and return an output of a fixed size. The mixer can be a part of the complete hash function, often the key part, but it is not the entire thing.
Here's another hash function / mixer that uses only add, rotate and xor. Actually this is based on common ARX ciphers, but a lot smaller because it doesn't need to be a secure cipher.
It is 48 x86_64 instructions, compared to the 36 instructions of khash in the link. I am sure you could put more data into b, c, and d as parameters, but I've only used it as a U64 to U64 function.
static uint64_t rotl64(uint64_t n, uint8_t k) {
uint64_t a = n << k;
uint64_t b = n >> (64 - k);
return a | b;
}
uint64_t hash(uint64_t a) {
uint64_t b = 0;
uint64_t c = 0;
uint64_t d = 0;
for (uint8_t i = 0; i < 4; i++) {
b ^= rotl64(a + d, 7);
c ^= rotl64(b + a, 9);
d ^= rotl64(c + b, 13);
a ^= rotl64(d + c, 18);
}
return a ^ b ^ c ^ d;
}
Worth pointing out for bystanders that in superscalar, pipelined processors the number of instructions has very little bearing over whether something is faster or slower (unless we are talking about differences of many orders of magnitude in the number of instructions). This applies even if we are not talking about instructions that deal with memory or I/O.
For the simple ops used in these particular algorithms, it should be possible to use SIMD to saturate the pipeline, getting high throughput for the same latency, assuming SIMD is part of the ISA. Cache misses wouldn't be a factor in comparing hash algorithms, as the memory layout is a feature of the hash input, and hash state would typically either be in register or in cache
It seems to me is that if you want to do that, you would use the value as a seed to set the internal state of the PRNG and then call the PRNG just once to get the hash value.
But in order to do that, you would have to derive the seed from the data in an appropriate way, which is basically the same exercise as defining a general hash function (i.e. projecting a data of arbitrary length into a set of values of fixed length).
So it looks like you are back to square one, more or less.
Perhaps I'm missing something, but what are applications of a hash function that returns the same word size as its input? Just obfuscation of the input?
It is often useful to have integer-keyed associative arrays; or, if you prefer, sparse positional arrays.
In either case, a hash table is often the most optimal implementation strategy. And unless the keys are guaranteed to be evenly distributed, the identity is an asymptotically bad hash function.
But the hash still produces sparse outputs, it has some degree of avalanche effect does it not? In which case, wouldn't the hash function produce worse results w.r.t. cache misses?
I am not sure what you're getting at. Are you unfamiliar with hash tables as a data structure?
If your keys are maximally clustered then you can use an alternate dense representation. Otherwise, using a hash table with the identity hash function will likely result in many collisions.
Typically it is important for a hash function to be fast, because it is on the critical path.
This hash function builds up a very long dependency chain, so takes about as many clock cycles as lines. It is generally better to keep dependency chains short and independent.
In this case, it would be better to start three or more separate expressions, and xor them together at the end, so they could execute in parallel, maybe 3x as fast.
But if you have an AES instruction, a couple of rounds of that are probably better and faster than what you would invent.
In short: it shows why a simple word mixer alone is not enough for a proper hash. It is insecure, fails all tests, and is not as fast as expected. I would not even use it for PRNG's, but I haven't tested that usage yet.
30 comments
[ 3.2 ms ] story [ 71.0 ms ] threadAs for x86/x86_64 processors compiling with a flag like -march=broadwell will remove quite few movs from the compiled code since the RORX instruction will be available which can take two register parameters, and a constant. Unlike the normal ROR instruction which is just a register and constant or the CL register for the rotation amount.
Now compared to functions that use multiplication. Multiplication can mix bits quite quickly. If the hardware multiplier is fast I don't think it would be faster with than fnv1 considering how simple that function is.
Meaning it's super easy to create collisions? How easy exactly?
It can only take an input of fixed size and return an output of the same size.
"True" hash functions take an input buffer of an arbitrary size, and return an output of a fixed size. The mixer can be a part of the complete hash function, often the key part, but it is not the entire thing.
It is 48 x86_64 instructions, compared to the 36 instructions of khash in the link. I am sure you could put more data into b, c, and d as parameters, but I've only used it as a U64 to U64 function.
K-HASH: 26 instructions https://godbolt.org/z/s3f13nGdG
Your-ARX: 48 instructions (even with rorx) https://godbolt.org/z/cv6PeohP6
Even if the dependency chain is too long for the CPU (or you) to split it, the CPU can always run hyperthread while waiting.
Heres a script to make one from /dev/urandom. Use something.pbm as the file name. size is in octets.
It seems to me is that if you want to do that, you would use the value as a seed to set the internal state of the PRNG and then call the PRNG just once to get the hash value.
But in order to do that, you would have to derive the seed from the data in an appropriate way, which is basically the same exercise as defining a general hash function (i.e. projecting a data of arbitrary length into a set of values of fixed length).
So it looks like you are back to square one, more or less.
- A PRNG takes a pseudo-random state and produces another pseudo-random state
- A mixer takes possibly correlated inputs and must produce outputs as uncorrelated as possible.
I've actually experimented with using xorshift variants as mixers and they fail the basic statistical tests.
In either case, a hash table is often the most optimal implementation strategy. And unless the keys are guaranteed to be evenly distributed, the identity is an asymptotically bad hash function.
If your keys are maximally clustered then you can use an alternate dense representation. Otherwise, using a hash table with the identity hash function will likely result in many collisions.
This hash function builds up a very long dependency chain, so takes about as many clock cycles as lines. It is generally better to keep dependency chains short and independent.
In this case, it would be better to start three or more separate expressions, and xor them together at the end, so they could execute in parallel, maybe 3x as fast.
But if you have an AES instruction, a couple of rounds of that are probably better and faster than what you would invent.
In short: it shows why a simple word mixer alone is not enough for a proper hash. It is insecure, fails all tests, and is not as fast as expected. I would not even use it for PRNG's, but I haven't tested that usage yet.