3 ms·

How does it compare to: FarmHash CityHash SMHasher MetroHash FNV1a_YT Note that if you're just using it for a hash table, where you'll compare the full st

How does it compare to: FarmHash CityHash SMHasher MetroHash FNV1a_YT Note that if you're just using it for a hash table, where you'll compare the full strings to resolve hash collisions, you don't actually need good randomness. FNV1A_VT is faster than most, has worse collision properties, yet provides a faster overall hash table, because the faster hash (every operation) outweighs the extra full string checks (rare). https://github.com/rurban/smhasher https://github.com/rurban/smhasher

howard941 8y ago
That's a cool link - thank you. There's so much there I couldn't tell if there were benchmarks for implementation on embedded hosts. I'm constantly looking for something suitable for use on embedded stuff. Having an x86 would be like having a unicorn as my deployment target. Recently (this year) the MCUs I've asked for have hardware crc32 and sometimes even AES128 but the suits tell me to Remember the BOM, Luke, and those fancy periphs aren't available on common M0+ my hardware guy likes (NXP KE0xxx for ex). Left wondering how this one will work on a run of the mill ARM.
zokier 8y ago
Almost certainly faster than any of the ones you list for large data. I would expect the perf to be more comparable to the other aesni hashes (t1ha and falkhash), both which bench around 4 bytes/ cycle while meow claims 16 bytes/cycle. Meow does include implementation for smhasher, so benchmarking should be easy enough https://github.com/cmuratori/meow_hash/blob/master/meow_smhasher.cpp https://github.com/cmuratori/meow_hash/blob/master/meow_smha...
ninkendo 8y ago
> because the faster hash (every operation) outweighs the extra full string checks (rare) I'm confused... don't you have to do at least one full string check for every table lookup on a hash table, to ensure the value you're returning is really the right key, and not just some other key that happens to collide? In other words, if I have 32 buckets in my table and one value stored at table["hello"], and table["goodbye"] happens to hash to the same bucket, how do you know whether to return not-found for "goodbye" without a full string comparison? (Or for that matter, how do you know whether to return the stored value for "hello" without a comparison?)
- mort96 8y ago
  Every operation requires one hash and at least one string check, but the more collisions there are, the more string checks you have to do. In theory, a hash algorithm with a great distribution and few collisions would require less string checks (I.e generally just one) per operation than an algorithm with a poor distribution. GP was saying that in their experience, the less frequent extra string checks generally isn't worth the slower hashing speed of an algorithm with a better distribution. (It's also worth noting that getting or setting elements which don't exist requires 0 string compares unless there's a collision, which might be relevant for certain workloads.)
  - bonzini 8y ago
    Most of the cost of string checks is often just the cache miss to load the first bytes of the string. Depending on the input, e.g. if lengths have more or less uniform distributions, full string checks might only be needed 10% of the time or so; store the string length in the bucket and you save the cache miss. Or you could store the first few bytes of the key in the bucket (but then in other cases, for example a hash table containing absolute filesystem paths, the first few bytes are always the same across keys).
loeg 8y ago
FNV has terrible hash properties (i.e. it fails many smhasher tests as mentioned in TFA), so it isn't really comparable. SMHasher isn't a hash function? It's a test suite for hash functions. CityHash's CRC modes are nominally 4.3-5.5 bytes/cycle. The others are slower. This article quotes 16 b/c for Meowhash.
- pkaye 8y ago
  Yup FNV is terrible from my experience using it in a custom hashmap implementation. The lower bits of the FNV hash have a lot of bias.

howard941 8y ago

That's a cool link - thank you. There's so much there I couldn't tell if there were benchmarks for implementation on embedded hosts. I'm constantly looking for something suitable for use on embedded stuff. Having an x86 would be like having a unicorn as my deployment target. Recently (this year) the MCUs I've asked for have hardware crc32 and sometimes even AES128 but the suits tell me to Remember the BOM, Luke, and those fancy periphs aren't available on common M0+ my hardware guy likes (NXP KE0xxx for ex). Left wondering how this one will work on a run of the mill ARM.

zokier 8y ago

Almost certainly faster than any of the ones you list for large data. I would expect the perf to be more comparable to the other aesni hashes (t1ha and falkhash), both which bench around 4 bytes/ cycle while meow claims 16 bytes/cycle. Meow does include implementation for smhasher, so benchmarking should be easy enough https://github.com/cmuratori/meow_hash/blob/master/meow_smhasher.cpp https://github.com/cmuratori/meow_hash/blob/master/meow_smha...

ninkendo 8y ago

> because the faster hash (every operation) outweighs the extra full string checks (rare) I'm confused... don't you have to do at least one full string check for every table lookup on a hash table, to ensure the value you're returning is really the right key, and not just some other key that happens to collide? In other words, if I have 32 buckets in my table and one value stored at table["hello"], and table["goodbye"] happens to hash to the same bucket, how do you know whether to return not-found for "goodbye" without a full string comparison? (Or for that matter, how do you know whether to return the stored value for "hello" without a comparison?)

mort96 8y ago
Every operation requires one hash and at least one string check, but the more collisions there are, the more string checks you have to do. In theory, a hash algorithm with a great distribution and few collisions would require less string checks (I.e generally just one) per operation than an algorithm with a poor distribution. GP was saying that in their experience, the less frequent extra string checks generally isn't worth the slower hashing speed of an algorithm with a better distribution. (It's also worth noting that getting or setting elements which don't exist requires 0 string compares unless there's a collision, which might be relevant for certain workloads.)
- bonzini 8y ago
  Most of the cost of string checks is often just the cache miss to load the first bytes of the string. Depending on the input, e.g. if lengths have more or less uniform distributions, full string checks might only be needed 10% of the time or so; store the string length in the bucket and you save the cache miss. Or you could store the first few bytes of the key in the bucket (but then in other cases, for example a hash table containing absolute filesystem paths, the first few bytes are always the same across keys).

loeg 8y ago

FNV has terrible hash properties (i.e. it fails many smhasher tests as mentioned in TFA), so it isn't really comparable. SMHasher isn't a hash function? It's a test suite for hash functions. CityHash's CRC modes are nominally 4.3-5.5 bytes/cycle. The others are slower. This article quotes 16 b/c for Meowhash.

pkaye 8y ago
Yup FNV is terrible from my experience using it in a custom hashmap implementation. The lower bits of the FNV hash have a lot of bias.