6 ms·

Hash tables

139 points by milsebg 7y ago

sdegutis 7y ago
Also http://craftinginterpreters.com/hash-tables.html http://craftinginterpreters.com/hash-tables.html
saagarjha 7y ago
> A hash function is a one-way function that produces the same output for a given input. It’s one-way in the sense that, given the hash function, it should be difficult to convert the output back to the input without trial and error. Usually I like to say that they convert an input into a uniform distribution of fixed length output, since reversibility isn’t really important if you using it for a non-cryptographic purpose such as this one.
- barbegal 7y ago
  Yeah sometimes the best hash functions for hash tables are easily reversible. And hash functions that can't be reversed faster than brute force can be really bad if their output is biased making collisions more likely.
  - AdamN 7y ago
    It's an important distinction that many people forget: * Hash tables need speed and uniformity * Cryptographic hashes need irreversibility
    - dragontamer 7y ago
      Cryptographic hashes also need speed and uniformity. They just need irreversibility significantly more. GF(2) space is incredible for both speed and uniformity. IIRC, the fastest x86 hash-functions just use the AESENC instruction (Note: the AESENC instruction executes with 1-instruction per clock cycle on Intel, and 2-instructions per clock cycle on AMD. Its an incredibly fast primitive).
      - jcranmer 7y ago
        That's throughput you're citing, they still have 4-8 clock cycles of latency, according to https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=132,133,227,236,233&othertechs=AES https://software.intel.com/sites/landingpage/IntrinsicsGuide...
        dragontamer 7y ago
        True, but in practice, throughput is what you should be thinking about as a low level performance programmer. CPUs can execute many, many, many instructions in parallel. If all your data fits inside of L1 cache (4-clocks of latency), its actually pretty easy to achieve 2-instructions per clock or more ! Furthermore, modern CPUs are out-of-order processors. So the processor will automatically execute independent instructions to "fill up your latency", at least to some extent. CPUs have enough space to even handle main memory fetches (over 200+ reorder buffers on Skylake, to handle the 200+ clocks of latency on a DDR4 memory read or write). As long as you have "enough independent work to do," its not too bad. Compilers usually figure out independent chunks of work as they unroll loops for example. In my experience, the loop accounting (for int i=0; i<100; i++) will all execute inside of that latency in parallel to the work inside of the loop. So there's almost always work to do, at least at the ~5 clocks to 10-clocks worth of "misc" functions in any bit of code. The hard part is coming up with work to do for ~50ns of latency (ex: DDR4 Reads or Writes).
        gpderetta 7y ago
        Actually no, latency is usually a bottleneck before throughput is. Edit: for example when accessing an hash table, the hash computation is in the critical path.
        dragontamer 7y ago
        > Edit: for example when accessing an hash table, the hash computation is in the critical path. Hmmm... I think I'm biased a bit because of something I'm writing recently where different iterations of a loop were independent. In this case, you're right. The hash calculation is on the critical path and therefore is latency bound.
- papermachete 7y ago
  Why would it necessarily be uniform?
  - PeCaN 7y ago
    so that not too many things get hashed to the same location. that's kind of the entire point, you want hashes to be distributed equally among the entire array to minimize collisions.
dragontamer 7y ago
High-performance Hash table design is pretty interesting, because modern CPU architecture has grossly changed their performance characteristics. In the 90s, it was (probably) faster to do linked-list / chaining as a collision resolution mechanism. But because L1 caches are so fast on today's machines (and DDR4 remains very high latency), linear probing seems to be the winner on modern machines. Consider that DDR4 RAM is maybe 200-clock cycles to access (50ns on a 4GHz modern machine). L1 cache can be accessed within 4 clock cycles. Fetching an entire cache line is like guessing on 8-positions in linear probing. The if/else statements will execute all within single-digit nanoseconds (Modern CPUs execute at 4GHz, and can execute more than 1 instruction per clock tick... up to 6-instructions per tick if all instructions are in uop cache and are properly branch-predicted), long before the 2nd location (ex: the 2nd member in a Linked List) can be even accessed. Furthermore, modern CPUs will perform pre-fetching when they notice code traversing through memory linearly. As such, the 200-clock cycle latency is "pipelined" and performed in parallel in practice. Your "effective latency" drops significantly when you traverse linearly. EDIT: And finally: staying on the same DDR4 row (Roughly 1024 bytes) means that you only have to perform a Column-read command over and over again. If you leave a DDR4 Row, the RAM needs to precharge, open the new row, and then perform a new column read. Takes roughly 3x longer than reading from an already open column.
- java-man 7y ago
  This is the most coherent and elucidating answer on the topic I've seen on HN in many years. Thank you!
- ignoramous 7y ago
  One of my favourite lock-free, hash-table talks is by Dr. Cliff Click, ex-Azul Systems, presently at H2O.ai, from 6 years ago: https://www.youtube-nocookie.com/embed/WYXgtXWejRM https://www.youtube-nocookie.com/embed/WYXgtXWejRM Rust's implementation of Google's SwissTables is pretty trippy, as well: https://blog.waffles.space/2018/12/07/deep-dive-into-hashbrown https://blog.waffles.space/2018/12/07/deep-dive-into-hashbro... Whilst Clojure, Scala, Erlang, and Haskell use Hash Array Mapped Tries https://en.wikipedia.org/wiki/Hash_array_mapped_trie https://en.wikipedia.org/wiki/Hash_array_mapped_trie and its lock-free variant, Ctrie. Speaking of exotic data-structures used widely: HAProxy's creator u/wtarreau invented Elastic-Binary tree that powers HAProxy's caches and schedulers. Presentation: https://www.youtube-nocookie.com/embed/fXuYWqWsdFQ https://www.youtube-nocookie.com/embed/fXuYWqWsdFQ Blog: http://wtarreau.blogspot.com/2011/12/elastic-binary-trees-ebtree.html http://wtarreau.blogspot.com/2011/12/elastic-binary-trees-eb...
rurban 7y ago
> SipHash is a relatively fast hash function. Oh my! SipHash is by far the slowest of all practical hash functions. https://github.com/rurban/smhasher#smhasher https://github.com/rurban/smhasher#smhasher
- pubby 7y ago
  Those benchmarks are for hashing data in the billions of bytes range. Hash tables typically use data in the 1-20 byte range. Pretty big difference! As it turns out, hash functions optimized for billions of bytes don't work so well when you use them on only a few bytes. There's just too much startup time and too many irrelevant branches and too much bloat for the icache to handle. That's why most hash tables use simpler algorithms like FNV1A or SipHash, which are faster for small data.
  - zzzcpan 7y ago
    > Those benchmarks are for hashing data in the billions of bytes range. Hash tables typically use data in the 1-20 byte range. No, you misunderstood the purpose of the project. From the benchmarks, SipHash: Small key speed test - 1-byte keys - 110.91 cycles/hash Small key speed test - 2-byte keys - 110.32 cycles/hash ... Small key speed test - 20-byte keys - 164.79 cycles/hash wyhash: Small key speed test - 1-byte keys - 18.00 cycles/hash Small key speed test - 2-byte keys - 18.00 cycles/hash ... Small key speed test - 20-byte keys - 21.00 cycles/hash The whole purpose of smhasher is to help choose hash functions for hash tables and alike implementations.

139 points by milsebg 7y ago

Also http://craftinginterpreters.com/hash-tables.html http://craftinginterpreters.com/hash-tables.html

> A hash function is a one-way function that produces the same output for a given input. It’s one-way in the sense that, given the hash function, it should be difficult to convert the output back to the input without trial and error. Usually I like to say that they convert an input into a uniform distribution of fixed length output, since reversibility isn’t really important if you using it for a non-cryptographic purpose such as this one.

barbegal 7y ago
Yeah sometimes the best hash functions for hash tables are easily reversible. And hash functions that can't be reversed faster than brute force can be really bad if their output is biased making collisions more likely.
- AdamN 7y ago
  It's an important distinction that many people forget: * Hash tables need speed and uniformity * Cryptographic hashes need irreversibility
  - dragontamer 7y ago
    Cryptographic hashes also need speed and uniformity. They just need irreversibility significantly more. GF(2) space is incredible for both speed and uniformity. IIRC, the fastest x86 hash-functions just use the AESENC instruction (Note: the AESENC instruction executes with 1-instruction per clock cycle on Intel, and 2-instructions per clock cycle on AMD. Its an incredibly fast primitive).
    - jcranmer 7y ago
      That's throughput you're citing, they still have 4-8 clock cycles of latency, according to https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=132,133,227,236,233&othertechs=AES https://software.intel.com/sites/landingpage/IntrinsicsGuide...
      - dragontamer 7y ago
        True, but in practice, throughput is what you should be thinking about as a low level performance programmer. CPUs can execute many, many, many instructions in parallel. If all your data fits inside of L1 cache (4-clocks of latency), its actually pretty easy to achieve 2-instructions per clock or more ! Furthermore, modern CPUs are out-of-order processors. So the processor will automatically execute independent instructions to "fill up your latency", at least to some extent. CPUs have enough space to even handle main memory fetches (over 200+ reorder buffers on Skylake, to handle the 200+ clocks of latency on a DDR4 memory read or write). As long as you have "enough independent work to do," its not too bad. Compilers usually figure out independent chunks of work as they unroll loops for example. In my experience, the loop accounting (for int i=0; i<100; i++) will all execute inside of that latency in parallel to the work inside of the loop. So there's almost always work to do, at least at the ~5 clocks to 10-clocks worth of "misc" functions in any bit of code. The hard part is coming up with work to do for ~50ns of latency (ex: DDR4 Reads or Writes).
        gpderetta 7y ago
        Actually no, latency is usually a bottleneck before throughput is. Edit: for example when accessing an hash table, the hash computation is in the critical path.
        dragontamer 7y ago
        > Edit: for example when accessing an hash table, the hash computation is in the critical path. Hmmm... I think I'm biased a bit because of something I'm writing recently where different iterations of a loop were independent. In this case, you're right. The hash calculation is on the critical path and therefore is latency bound.
papermachete 7y ago
Why would it necessarily be uniform?
- PeCaN 7y ago
  so that not too many things get hashed to the same location. that's kind of the entire point, you want hashes to be distributed equally among the entire array to minimize collisions.

dragontamer 7y ago

High-performance Hash table design is pretty interesting, because modern CPU architecture has grossly changed their performance characteristics. In the 90s, it was (probably) faster to do linked-list / chaining as a collision resolution mechanism. But because L1 caches are so fast on today's machines (and DDR4 remains very high latency), linear probing seems to be the winner on modern machines. Consider that DDR4 RAM is maybe 200-clock cycles to access (50ns on a 4GHz modern machine). L1 cache can be accessed within 4 clock cycles. Fetching an entire cache line is like guessing on 8-positions in linear probing. The if/else statements will execute all within single-digit nanoseconds (Modern CPUs execute at 4GHz, and can execute more than 1 instruction per clock tick... up to 6-instructions per tick if all instructions are in uop cache and are properly branch-predicted), long before the 2nd location (ex: the 2nd member in a Linked List) can be even accessed. Furthermore, modern CPUs will perform pre-fetching when they notice code traversing through memory linearly. As such, the 200-clock cycle latency is "pipelined" and performed in parallel in practice. Your "effective latency" drops significantly when you traverse linearly. EDIT: And finally: staying on the same DDR4 row (Roughly 1024 bytes) means that you only have to perform a Column-read command over and over again. If you leave a DDR4 Row, the RAM needs to precharge, open the new row, and then perform a new column read. Takes roughly 3x longer than reading from an already open column.

java-man 7y ago
This is the most coherent and elucidating answer on the topic I've seen on HN in many years. Thank you!
ignoramous 7y ago
One of my favourite lock-free, hash-table talks is by Dr. Cliff Click, ex-Azul Systems, presently at H2O.ai, from 6 years ago: https://www.youtube-nocookie.com/embed/WYXgtXWejRM https://www.youtube-nocookie.com/embed/WYXgtXWejRM Rust's implementation of Google's SwissTables is pretty trippy, as well: https://blog.waffles.space/2018/12/07/deep-dive-into-hashbrown https://blog.waffles.space/2018/12/07/deep-dive-into-hashbro... Whilst Clojure, Scala, Erlang, and Haskell use Hash Array Mapped Tries https://en.wikipedia.org/wiki/Hash_array_mapped_trie https://en.wikipedia.org/wiki/Hash_array_mapped_trie and its lock-free variant, Ctrie. Speaking of exotic data-structures used widely: HAProxy's creator u/wtarreau invented Elastic-Binary tree that powers HAProxy's caches and schedulers. Presentation: https://www.youtube-nocookie.com/embed/fXuYWqWsdFQ https://www.youtube-nocookie.com/embed/fXuYWqWsdFQ Blog: http://wtarreau.blogspot.com/2011/12/elastic-binary-trees-ebtree.html http://wtarreau.blogspot.com/2011/12/elastic-binary-trees-eb...

rurban 7y ago

> SipHash is a relatively fast hash function. Oh my! SipHash is by far the slowest of all practical hash functions. https://github.com/rurban/smhasher#smhasher https://github.com/rurban/smhasher#smhasher

pubby 7y ago
Those benchmarks are for hashing data in the billions of bytes range. Hash tables typically use data in the 1-20 byte range. Pretty big difference! As it turns out, hash functions optimized for billions of bytes don't work so well when you use them on only a few bytes. There's just too much startup time and too many irrelevant branches and too much bloat for the icache to handle. That's why most hash tables use simpler algorithms like FNV1A or SipHash, which are faster for small data.
- zzzcpan 7y ago
  > Those benchmarks are for hashing data in the billions of bytes range. Hash tables typically use data in the 1-20 byte range. No, you misunderstood the purpose of the project. From the benchmarks, SipHash: Small key speed test - 1-byte keys - 110.91 cycles/hash Small key speed test - 2-byte keys - 110.32 cycles/hash ... Small key speed test - 20-byte keys - 164.79 cycles/hash wyhash: Small key speed test - 1-byte keys - 18.00 cycles/hash Small key speed test - 2-byte keys - 18.00 cycles/hash ... Small key speed test - 20-byte keys - 21.00 cycles/hash The whole purpose of smhasher is to help choose hash functions for hash tables and alike implementations.