69 ms·

I'm not very well versed in data structure optimization, but I was surprised they dismissed hash tables so quickly, especially when the table they are searching

I'm not very well versed in data structure optimization, but I was surprised they dismissed hash tables so quickly, especially when the table they are searching through is static. I find it somewhat hard to believe that a specially optimized hash table would not be faster than their trie implementation.

supermatt 2y ago
They mentioned it is the overhead of the hashing that makes it slow compared to the trie.
- hooli42 2y ago
  Hash functions can be as simple as a single modulo.
  - ironman1478 2y ago
    As they said though, the hash function on a string type requires looking at every element in the string. Also, modulo is historically very slow. So, they still have to deal with O(n) operations, where n is the length of the input string. If they can improve the memory hopping problem associated with lists / graph structures (which they claim to have done in their library), then a trie could would be much fast enough, which is what they observed. Combined with the fact that they claim that 90% of the time there is a miss when querying the trie, then you exit early a lot, whereas you always need to compute the whole hash on the input string when doing the hash map strategy.
    - hervature 2y ago
      > As they said though, the hash function on a string type requires looking at every element in the string. Maybe for the default hash function. As another commenter pointed out, your data may make the following hash very effective: s[0] + s[len(s)//2] + s[-1] which would be very fast. The point being is spending a day seeing if such a hash exists is worth it.
    - mightyham 2y ago
      The hash does not need to be computed on the whole string. I pointed this out in my other comment but just as a example: a hash function could be as simple as xoring the first 16 and last 16 bits of the string then indexing a 2^16 array. That means hashing is two pointer offsets and an xor (no modulo required). If there are 100 strings that need to be removed, then ~99% of rejections will be a very fast O(1). And in the case of a match, a fast hash + memcmp will be way faster than a trie traversal. In fact, according to the trie-hard github readme, std::HashMap is already much faster than their trie implementation when searching for a match.
  - torusle 2y ago
    Or as simple as using the hardware accelerated CRC32 that we have in our x86 CPUs. Last time I checked, CRC32 worked surprisingly well as a hash.
    - hooli42 2y ago
      Hah, neat. The 'weird' instructions can often be 3-4 orders of magnitude slower than arithmetic instructions, though I doubt that matters here.
      - Validark 2y ago
        CRC32 is the same speed as an integer multiply, going all the way back to Nehalem (2008). 3 cycles latency, and you can start a new one each cycle (or more than one, on Zen 5).
        hooli42 2y ago
        Sure, in the same way SIMD instructions get a linear speedup in theory. If you Google the words "CRC32 is slow", you can see hundreds of people complaining about this.
- mightyham 2y ago
  The point I'm making is that a specially optimized hashing function would probably blow away any trie traversal. When you know the data being hashed before hand it is possible to make custom hash functions that are as simple as a few bitwise operations on the first, middle and last character of the string (just an example).
  - dividuum 2y ago
    Right. Out of curiosity I looked into what code gperf generates and it seems it would end up O(1) for misses (it's always three lookups into a generated table) and O(L) for hits, as a potential hit has to be confirmed by essentially a strcmp. Not sure how something like https://github.com/rust-phf/rust-phf https://github.com/rust-phf/rust-phf would work, but probably similar?
  - treis 2y ago
    Isn't the sticky wicket collisions with external to CF defined headers?
  - Denvercoder9 2y ago
    They don't know all the data that's being hashed, though. They know everything that's in the map, but not all the keys they're trying to lookup.
  - dathinab 2y ago
    if all your internal headers start with cf- and most non-internal headers don't (but not all) and most headers are non-internal a trie might be hard to beat
- vlovich123 2y ago
  If they just used the default, that's SipHash which is optimized for security and DOS resistance, not performance. XXh3 is ~10x faster than that and there's some newer ones that are even faster than Xxh3 like GxHash (like another ~1.5x-2x faster). You would precompute the hash for the constant string list & then compute the hash only for for the set of strings that begin with C/c since "cf-" is a common prefix for those internal headers if I recall correctly, using RawTable to find entries by hash & then comparing against the precomputed value to see if a collision matched before checking a string for equality.
5kg 2y ago
There is FxHashMap (https://github.com/rust-lang/rustc-hash https://github.com/rust-lang/rustc-hash) which is faster than std::collections::HashMap. With ~100 static entries, o1hash (https://github.com/rurban/smhasher/blob/master/o1hash.h https://github.com/rurban/smhasher/blob/master/o1hash.h) should also work.
- rapsey 2y ago
  Note FxHashMap is just the std HashMap with a different hashing algorithm.
samatman 2y ago
A hash function can't reject a string with a single test of the first byte. It just can't. For this application, that's a leg up which a hash won't be able to touch. The rest of the art here is shaving down the constant factor of a trie far enough that the initial boost pays off in real-world performance.

supermatt 2y ago

They mentioned it is the overhead of the hashing that makes it slow compared to the trie.

hooli42 2y ago
Hash functions can be as simple as a single modulo.
- ironman1478 2y ago
  As they said though, the hash function on a string type requires looking at every element in the string. Also, modulo is historically very slow. So, they still have to deal with O(n) operations, where n is the length of the input string. If they can improve the memory hopping problem associated with lists / graph structures (which they claim to have done in their library), then a trie could would be much fast enough, which is what they observed. Combined with the fact that they claim that 90% of the time there is a miss when querying the trie, then you exit early a lot, whereas you always need to compute the whole hash on the input string when doing the hash map strategy.
  - hervature 2y ago
    > As they said though, the hash function on a string type requires looking at every element in the string. Maybe for the default hash function. As another commenter pointed out, your data may make the following hash very effective: s[0] + s[len(s)//2] + s[-1] which would be very fast. The point being is spending a day seeing if such a hash exists is worth it.
  - mightyham 2y ago
    The hash does not need to be computed on the whole string. I pointed this out in my other comment but just as a example: a hash function could be as simple as xoring the first 16 and last 16 bits of the string then indexing a 2^16 array. That means hashing is two pointer offsets and an xor (no modulo required). If there are 100 strings that need to be removed, then ~99% of rejections will be a very fast O(1). And in the case of a match, a fast hash + memcmp will be way faster than a trie traversal. In fact, according to the trie-hard github readme, std::HashMap is already much faster than their trie implementation when searching for a match.
- torusle 2y ago
  Or as simple as using the hardware accelerated CRC32 that we have in our x86 CPUs. Last time I checked, CRC32 worked surprisingly well as a hash.
  - hooli42 2y ago
    Hah, neat. The 'weird' instructions can often be 3-4 orders of magnitude slower than arithmetic instructions, though I doubt that matters here.
    - Validark 2y ago
      CRC32 is the same speed as an integer multiply, going all the way back to Nehalem (2008). 3 cycles latency, and you can start a new one each cycle (or more than one, on Zen 5).
      - hooli42 2y ago
        Sure, in the same way SIMD instructions get a linear speedup in theory. If you Google the words "CRC32 is slow", you can see hundreds of people complaining about this.
mightyham 2y ago
The point I'm making is that a specially optimized hashing function would probably blow away any trie traversal. When you know the data being hashed before hand it is possible to make custom hash functions that are as simple as a few bitwise operations on the first, middle and last character of the string (just an example).
- dividuum 2y ago
  Right. Out of curiosity I looked into what code gperf generates and it seems it would end up O(1) for misses (it's always three lookups into a generated table) and O(L) for hits, as a potential hit has to be confirmed by essentially a strcmp. Not sure how something like https://github.com/rust-phf/rust-phf https://github.com/rust-phf/rust-phf would work, but probably similar?
- treis 2y ago
  Isn't the sticky wicket collisions with external to CF defined headers?
- Denvercoder9 2y ago
  They don't know all the data that's being hashed, though. They know everything that's in the map, but not all the keys they're trying to lookup.
- dathinab 2y ago
  if all your internal headers start with cf- and most non-internal headers don't (but not all) and most headers are non-internal a trie might be hard to beat
vlovich123 2y ago
If they just used the default, that's SipHash which is optimized for security and DOS resistance, not performance. XXh3 is ~10x faster than that and there's some newer ones that are even faster than Xxh3 like GxHash (like another ~1.5x-2x faster). You would precompute the hash for the constant string list & then compute the hash only for for the set of strings that begin with C/c since "cf-" is a common prefix for those internal headers if I recall correctly, using RawTable to find entries by hash & then comparing against the precomputed value to see if a collision matched before checking a string for equality.

5kg 2y ago

There is FxHashMap (https://github.com/rust-lang/rustc-hash https://github.com/rust-lang/rustc-hash) which is faster than std::collections::HashMap. With ~100 static entries, o1hash (https://github.com/rurban/smhasher/blob/master/o1hash.h https://github.com/rurban/smhasher/blob/master/o1hash.h) should also work.

rapsey 2y ago
Note FxHashMap is just the std HashMap with a different hashing algorithm.

samatman 2y ago

A hash function can't reject a string with a single test of the first byte. It just can't. For this application, that's a leg up which a hash won't be able to touch. The rest of the art here is shaving down the constant factor of a trie far enough that the initial boost pays off in real-world performance.