4 ms·

Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the

by rntz 8y ago

Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this might be. But later it mentions, in passing, a simpler approach: just shift the high bits down and xor! The author only tries doing this as a preprocessing step in front of Fibonacci hashing to avoid "bad patterns". So I'm left wondering: might shift-down-and-xor be good enough on its own?

adrianratnapala 8y ago
Yep. The high-bits thing puzzled me as well because I thought shift-and-xor folding was standard practice. Also multiply-and-shift-down still tends to favour certain bits over others.
twic 8y ago
The article presents Fibonacci hashing as an operation to map a hash code into a smaller range, but it isn't that, really. The operation that does that is still just taking some bits from the hash code. What Fibonacci hashing actually is is a way of stirring a hash code before use, to spread its entropy out more, so that the bits you end up taking a more likely to be well-distributed. If your hash codes are already well-distributed, then this is pointless. But if they aren't, it's useful. So, it seems to me that rather than applying Fibonacci hashing to all hash codes, it would be better to use it as the original hash function for types which currently have bad hash functions. This is something a C++ standard library could easily do. For example, LLVM's libc++ implements string hashing using MurmurHash2 on 32-bit machines, and CityHash on 64-bit machines: https://github.com/llvm-mirror/libcxx/blob/master/include/__string#L854 https://github.com/llvm-mirror/libcxx/blob/master/include/__... https://github.com/llvm-mirror/libcxx/blob/master/include/utility#L954 https://github.com/llvm-mirror/libcxx/blob/master/include/ut... But hashes all sizes of integers to themselves: https://github.com/llvm-mirror/libcxx/blob/master/include/ext/__hash#L94 https://github.com/llvm-mirror/libcxx/blob/master/include/ex... Changing that to a Fibonacci hash, or a simpler shift-and-xor, could be a quick win. Provided that libc++'s unordered_map uses power-of-two table sizes, that is. The code is labyrinthine, but i think, rather gloriously, sometimes it does, and sometimes it doesn't: https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L2131 https://github.com/llvm-mirror/libcxx/blob/master/include/__... https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L125 https://github.com/llvm-mirror/libcxx/blob/master/include/__... __constrain_hash is a simple but entertaining bit of bit-dickery (reformatted slightly): size_t __constrain_hash(size_t __h, size_t __bc) { return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc); } The x & (x - 1) tests whether a number is a power of two, because for any number that is not a power of two, subtracting one leaves the top bit set, so the bitwise and will contain at least one set bit. If the bucket count (number of slots) is a power of two, use a mask to extract the bottom bits of the hash. If it's not, do a modulus - but spend a branch to avoid that if the hash is already in the right range, which i'm surprised is a win.
- acqq 8y ago
  > LLVM's libc++ Great find! So the library solutions are still often suboptimal, and it's even more easy to hide bad decisions in the C++ sources, so whoever has the approach "just use the default library" should be aware of that once the performance is important. Yes, even the simple multiplicative constants can significantly improve the hash if it by default doesn't do anything with the input! The libraries definitely should be fixed, and adding the multiplication step is really a simple and fast change for a great benefit. As an inspiration, Kernighan and Ritchie in their book about C used a simple number 31, and that simple hash is still quite good compared to much more complex and more recent solutions as K&R also haven't used the (I guess misleadingly named) "open addressing" for their hash table. Their solution is amazingly minimalistic and in that context amazingly good for chain hash tables. I wouldn't be surprised if just changing return __c; to return __c * 31; in the functions discovered would result in great improvement. The good side of such a constant is that it can give the fast and small code even on the old architectures where the "normal" multiplication is slow (e.g. even if there's no fast multiplier the result can be obtained by one shift and one subtraction!). Also on modern architectures using this constant can't result in any performance degradation but improving the hash behavior of these formerly unprocessed inputs guarantees speedup. And there are surely use cases when using more complex functions is much better, e.g. those suggested by aappleby: https://news.ycombinator.com/item?id=17330787 https://news.ycombinator.com/item?id=17330787 Back to the "open addressing", if you are rolling your own hash table and don't plan too much hash tables to be present in memory at once, it's often much faster to use "chains" (like in the K&R C book) than trying to store everything only in the table (which is misleadingly often called "open addressing" even if "closed hashing" is a better term) and jump through the table in the collision case. Maintaining lists per entry is typically much faster when the table is fuller, provided the allocation routines are fast. https://www.strchr.com/hash_functions https://www.strchr.com/hash_functions By the way, MurmurHash2 or 3 and CityHash are definitely very good functions, the problem is when they aren't used in the library, like, it seems, in libcxx. And in the cases where the simpler code is needed, even a simple * 31 is much, much better than nothing! And note, it seems there are even problems with these good functions, security wise: apparently the language implementations or the services accepting uncontrolled inputs also have to care about the security aspects of their hash functions: https://131002.net/siphash/ https://131002.net/siphash/ "Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. Some of the technologies affected have switched to SipHash." "SipHash was designed as a mitigation to hash-flooding DoS attacks. It is now used in the hash tables implementation of Python, Ruby, Perl 5, etc." "SipHash was designed by Jean-Philippe Aumasson and Daniel J. Bernstein."

by rntz 8y ago

adrianratnapala 8y ago

Yep. The high-bits thing puzzled me as well because I thought shift-and-xor folding was standard practice. Also multiply-and-shift-down still tends to favour certain bits over others.

twic 8y ago

The article presents Fibonacci hashing as an operation to map a hash code into a smaller range, but it isn't that, really. The operation that does that is still just taking some bits from the hash code. What Fibonacci hashing actually is is a way of stirring a hash code before use, to spread its entropy out more, so that the bits you end up taking a more likely to be well-distributed. If your hash codes are already well-distributed, then this is pointless. But if they aren't, it's useful. So, it seems to me that rather than applying Fibonacci hashing to all hash codes, it would be better to use it as the original hash function for types which currently have bad hash functions. This is something a C++ standard library could easily do. For example, LLVM's libc++ implements string hashing using MurmurHash2 on 32-bit machines, and CityHash on 64-bit machines: https://github.com/llvm-mirror/libcxx/blob/master/include/__string#L854 https://github.com/llvm-mirror/libcxx/blob/master/include/__... https://github.com/llvm-mirror/libcxx/blob/master/include/utility#L954 https://github.com/llvm-mirror/libcxx/blob/master/include/ut... But hashes all sizes of integers to themselves: https://github.com/llvm-mirror/libcxx/blob/master/include/ext/__hash#L94 https://github.com/llvm-mirror/libcxx/blob/master/include/ex... Changing that to a Fibonacci hash, or a simpler shift-and-xor, could be a quick win. Provided that libc++'s unordered_map uses power-of-two table sizes, that is. The code is labyrinthine, but i think, rather gloriously, sometimes it does, and sometimes it doesn't: https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L2131 https://github.com/llvm-mirror/libcxx/blob/master/include/__... https://github.com/llvm-mirror/libcxx/blob/master/include/__hash_table#L125 https://github.com/llvm-mirror/libcxx/blob/master/include/__... __constrain_hash is a simple but entertaining bit of bit-dickery (reformatted slightly): size_t __constrain_hash(size_t __h, size_t __bc) { return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc); } The x & (x - 1) tests whether a number is a power of two, because for any number that is not a power of two, subtracting one leaves the top bit set, so the bitwise and will contain at least one set bit. If the bucket count (number of slots) is a power of two, use a mask to extract the bottom bits of the hash. If it's not, do a modulus - but spend a branch to avoid that if the hash is already in the right range, which i'm surprised is a win.

acqq 8y ago
> LLVM's libc++ Great find! So the library solutions are still often suboptimal, and it's even more easy to hide bad decisions in the C++ sources, so whoever has the approach "just use the default library" should be aware of that once the performance is important. Yes, even the simple multiplicative constants can significantly improve the hash if it by default doesn't do anything with the input! The libraries definitely should be fixed, and adding the multiplication step is really a simple and fast change for a great benefit. As an inspiration, Kernighan and Ritchie in their book about C used a simple number 31, and that simple hash is still quite good compared to much more complex and more recent solutions as K&R also haven't used the (I guess misleadingly named) "open addressing" for their hash table. Their solution is amazingly minimalistic and in that context amazingly good for chain hash tables. I wouldn't be surprised if just changing return __c; to return __c * 31; in the functions discovered would result in great improvement. The good side of such a constant is that it can give the fast and small code even on the old architectures where the "normal" multiplication is slow (e.g. even if there's no fast multiplier the result can be obtained by one shift and one subtraction!). Also on modern architectures using this constant can't result in any performance degradation but improving the hash behavior of these formerly unprocessed inputs guarantees speedup. And there are surely use cases when using more complex functions is much better, e.g. those suggested by aappleby: https://news.ycombinator.com/item?id=17330787 https://news.ycombinator.com/item?id=17330787 Back to the "open addressing", if you are rolling your own hash table and don't plan too much hash tables to be present in memory at once, it's often much faster to use "chains" (like in the K&R C book) than trying to store everything only in the table (which is misleadingly often called "open addressing" even if "closed hashing" is a better term) and jump through the table in the collision case. Maintaining lists per entry is typically much faster when the table is fuller, provided the allocation routines are fast. https://www.strchr.com/hash_functions https://www.strchr.com/hash_functions By the way, MurmurHash2 or 3 and CityHash are definitely very good functions, the problem is when they aren't used in the library, like, it seems, in libcxx. And in the cases where the simpler code is needed, even a simple * 31 is much, much better than nothing! And note, it seems there are even problems with these good functions, security wise: apparently the language implementations or the services accepting uncontrolled inputs also have to care about the security aspects of their hash functions: https://131002.net/siphash/ https://131002.net/siphash/ "Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. Some of the technologies affected have switched to SipHash." "SipHash was designed as a mitigation to hash-flooding DoS attacks. It is now used in the hash tables implementation of Python, Ruby, Perl 5, etc." "SipHash was designed by Jean-Philippe Aumasson and Daniel J. Bernstein."