4 ms·
High-performance Hash table design is pretty interesting, because modern CPU architecture has grossly changed their performance characteristics. In the 90s, it
by 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 agoThis is the most coherent and elucidating answer on the topic I've seen on HN in many years. Thank you!
- ignoramous 7y agoOne 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...
- hesk 7y ago> 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. It depends on the use case, for example if it's read or write heavy, the number of successful lookups and the load factor. LP is often a good choice but in some cases bucket chaining wins. Quadratic probing and Robin Hood hashing are also winning candidates, as is Cuckoo hashing. See the flowchart at the end of this paper: Richter et al., 2005. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing, https://dl.acm.org/citation.cfm?id=2850585 https://dl.acm.org/citation.cfm?id=2850585
- kazinator 7y agoFirstly, we have L2 caches, not only L1. Secondly, it is possible for all of a linked list to in fact be in L1. Thirdly, if by "linear probing" you are at all referring to "open addressing", then there are some disadvantages to consider there. If we suspect that linked lists are performing badly, the reasonable thing would be to stick with the chained hash table, but replace the chains by little vectors. Essentially, "linear probing" but sideways out of the table, into little sub-tables. Issues with open addressing are issues like clustering if linear probing is used. If we use quadratic probing, then the table size has to be prime, otherwise we may not be able to able to insert a key into the table even if it is nowhere near full. When we delete keys, we have to leave "tombstone" entries in their place, so that the linear probing can continue past them to find other items. Things of that sort.
- dragontamer 7y ago> Issues with open addressing are issues like clustering if linear probing is used. Robin Hood hashing more or less solves that problem. > When we delete keys, we have to leave "tombstone" entries in their place, so that the linear probing can continue past them to find other items. Actually no. Even ignoring Robin Hood Hashing, you just swap a later element into place. idx = hash(value); delete(array[idx]); for(int i=idx+1; array[i] != empty; i = (i+1) % TABLE_SIZE){ if(hash(array[i].value) <= idx){ array[idx] = array[i]; idx = i; // Repeat for the new location } } I just typed the above in like 2 minutes, so there's probably a bug. But its probably "correct enough" that you can get the concept. There's no tombstones needed for linear probing (and only linear probing). Conceptually, you can see that array[i] is simply being "re-hashed" into the hash table. Donald Knuth in "The Art of Computer Programming" proves that the above procedure (well... the correct bug-free version at least) is equivalent to clearing out the hash table and rehashing all elements. Except of course, the above procedure is way faster. -------- Robin Hood hashing solves the problem in a different way. See this other guy's blog post for details: https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ https://www.sebastiansylvan.com/post/robin-hood-hashing-shou...
- kazinator 7y ago
- agumonkey 7y agoHow often are these things or even thinking used ? is it obvious work done in gcc/clang ? what about the jvm ? or kernels ?
- dragontamer 7y agoHigh performance compute techniques are basically used whenever you have code that runs for 20+ hours at a time. Things like Raytracers, supercomputers, database-analysis, physics simulations, chemical simulations, weather simulations, etc. etc. And I'm not talking about Webservers (which stay up for days, but the compute problem only happens over the course of ~1 second or so). Consider that when 3d movies are made, they hit the "Render" button and then wait 1 or 2 weeks for the movie to be made. Even if they have an entire cluster of computers calculating the scene... it takes a LOT of compute power to make movies. If you eek out a 10% improvement, your render-time drops from 10-days to 9-days. Alternatively, you can have 10% fewer computers to get the same job done. Or in the case of scientists (ex: a Car engineer who is running a FEA computer-simulated car crash), your models can be more detailed. (Ex: Instead of modeling the engine as a perfectly elastic sphere, maybe you can model the engine as a more appropriate shape in the simulated car-crash) There are a few exceptions. High-frequency traders also count milliseconds for their speed of execution. I see some HPC work coming out of HFT companies. But for the most part, highly-optimized code is specialized to the communities who still wait days (or even weeks) for the results from modern computers.