Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step

This talk had a lot of potential, but I couldn’t get through it. A lot of bits were very hand-wavy, and probably needed a lot more familiarity with C++ to grok. Examples:

  • What are sentinels?
  • Why does the node_hash_set require iterating over the whole array?
  • What is metadata (in this context)?
  • What are control bytes?

In general the ideas were intriguing, but the delivery made it difficult for me to understand. I’d love to learn more about this stuff, but a paper/blogpost would be far more preferable.

Further Reading