Loading…
This event has ended. Visit the official site or create your own event on Sched.
Back To Schedule
Wednesday, September 27 • 4:45pm - 5:45pm
Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
Hash tables consume a large volume of both compute resources and memory across Google's production system. The design for hash tables in C++ traces its origins to the SGI STL implementation from 20 years ago. Over these years, computer architecture and performance has changed dramatically and we need to evolve this fundamental data structure to follow those changes. This talk describes the process of design and optimization that starts with std::unordered_map and ends with a new design we call "SwissTable", a 2-level N-way associative hash table. Our implementation of this new design gets 2-3x better performance with significant memory reductions (compared to unordered_map) and is being broadly deployed across Google.

Speakers
avatar for Matt Kulukundis

Matt Kulukundis

Staff Software Engineer, Google
Matt is a senior software engineer on the C++ libraries team at Google.  Prior to Google he has worked on compilers, machine learning, and underwater robotics.  In his free time, he scuba dives in warm places.


Wednesday September 27, 2017 4:45pm - 5:45pm PDT
Atanasoff Hall Meydenbauer Center