3 ms·

Great article. 1. This seems to disagree with Rust's tests for FVN vs xxHash.[1] This article has xxHash winning a bit after 10 bytes. The Rust one has FVN win

Great article. 1. This seems to disagree with Rust's tests for FVN vs xxHash.[1] This article has xxHash winning a bit after 10 bytes. The Rust one has FVN winning until after 32 bytes. Rust recently added FVN. Is someone wrong or am I missing something? 2. Why is 64-bit slower on asm.js? If the host is 64-bit shouldn't it get 64-bit? I know JS doesn't have proper ints, but I thought asm.js-aware browsers were supposed to handle this well? Curious: Is there no uniform, fast, way to switch the algorithm for small inputs? Require the caller to hint that the key might be small (<8 or 16 bytes), otherwise in streaming mode, just restart if it turns out you only get <16 bytes. Or will that branching+code kill the gain? 1: http://cglab.ca/~abeinges/blah/hash-rs/ http://cglab.ca/~abeinges/blah/hash-rs/

rurban 10y ago
as 1) SMHasher is not the right test for performance for a hash function in a hash table. In a hash table FNV will always win over xxHash and all those file digests, which are optimized for aligned larger blocks. SMHasher is a good test for network throughput or hashing files, but not for hash tables. The reason is that an easily short inlinable hash function like FNV will always win over a big non-inlinable digest like Murmur, xxHash, Farm, Metro ... Furthermore, even if small worse hash functions produce more collisions, their small icache size will still outperform bigger functions with less collisions. More work, but less cache misses. For small hash tables it is even faster to do a linear search because of cache advantages, and also a linked-list of buckets is better be written as array. ("Cache-Conscious Collision Resolution in String Hash Tables" by Nikolas Askitis and Justin Zobel, Melbourne 2005) ad branching) Google successfully experimented with hash variants based on alignment and size. Newer CPU's explore those branches beforehead, so the overhead was not that big and worth it. See their sparse hashtable.
aras_p 10y ago
asm.js is essentially a "32 bit" compilation target, it does not (to my knowledge) support 64 bit arithmetic efficiently right now.

rurban 10y ago

as 1) SMHasher is not the right test for performance for a hash function in a hash table. In a hash table FNV will always win over xxHash and all those file digests, which are optimized for aligned larger blocks. SMHasher is a good test for network throughput or hashing files, but not for hash tables. The reason is that an easily short inlinable hash function like FNV will always win over a big non-inlinable digest like Murmur, xxHash, Farm, Metro ... Furthermore, even if small worse hash functions produce more collisions, their small icache size will still outperform bigger functions with less collisions. More work, but less cache misses. For small hash tables it is even faster to do a linear search because of cache advantages, and also a linked-list of buckets is better be written as array. ("Cache-Conscious Collision Resolution in String Hash Tables" by Nikolas Askitis and Justin Zobel, Melbourne 2005) ad branching) Google successfully experimented with hash variants based on alignment and size. Newer CPU's explore those branches beforehead, so the overhead was not that big and worth it. See their sparse hashtable.

aras_p 10y ago

asm.js is essentially a "32 bit" compilation target, it does not (to my knowledge) support 64 bit arithmetic efficiently right now.