CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”

Matt Kulukundis delivers a presentation on designing a fast, efficient, and cash-friendly hash table, detailing the step-by-step evolution of Google's new hash table, SwissTable, into FlatHashSet. He credits the extensive team involved, including Alcas Evlogimenos, Jeff Dean, and Sanjay Gemwat, among others. Kulukundis explains the trade-offs made in optimizing for performance and memory usage, such as removing indirections and using SSE instructions, and discusses the importance of good hash functions. He also addresses the ergonomic considerations for container design, common pitfalls in C++ related to temporary objects and const correctness, and the defense mechanisms against Hiram's Law during the rollout of these changes across Google. The presentation concludes with a Q&A session covering topics like open-sourcing the code, resizing strategies, and comparisons with other hash table implementations like Robinhood hashing.