hackertube.io

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

CppCon · talk · Watch on YouTube

Algorithms & data structuresSoftware performance & optimizationC, C++, Rust, Go & systems languages

What it is

Matt Kulukundis explains how Google designed SwissTable, a fast, cache-friendly hash table, step by step from std::unordered_map. The talk covers open addressing, SIMD probing and the tradeoffs of changing a fundamental data structure.

Why Hacker News recommends it

HN repeatedly cites it as the definitive explanation of SwissTable, the design behind Abseil, Rust's hash map and Go's maps.

  • 9 people recommended it
  • 10 different months
  • 4 strong recommendations
  • first 2018, last 2026

What HN commenters said

  1. “(warning, it's an hour. Takes a while to build up, too. Still worth it.)”

    Hour-long look at modern open addressing hash tables

    nwallin, 2019-10 · Strong recommendation · in “Hash tables”

  2. “the talk on SwissTable [2] (Google's SIMD accelerated hash table) is excellent”

    Talk on SIMD accelerated hash table

    sujayakar, 2021-03 · Strong recommendation · in “MIPS Becomes RISC-V”

  3. “is one of my favorites”

    Making of absl::flat_hash_map

    KerrickStaley, 2022-11 · Strong recommendation · in “Inside boost::unordered_flat_map”

  4. “Excellent talk which explains the concepts really clearly and concisely.”

    Clear, concise explanation of Swiss Table concepts

    lalitmaganti, 2026-07 · Strong recommendation · in “Golang Maps: how Swiss Tables replaced the old bucket design”

  5. “There's a good talk about such a dense, flat hash set here”

    Dense flat hash set design

    kllrnohj, 2019-08 · Recommendation · in “Bulk Data Structures C++”

  6. “There's a good talk from CppCon [0] that explains its design decisions”

    Explains SwissTable design decisions

    vthriller, 2020-03 · Recommendation · in “When Bloom filters don't bloom”

  7. “The whole talk is interesting to watch.”

    Shows pitfalls of std::unordered_map and its indirections

    yakubin, 2021-09 · Recommendation · in “Transmission torrent client ported to C++”

  8. “Is a fun presentation by Matthew Kulukundis (designer of Google's Hash Table)”

    Design and rollout of Google's hash table with Hyrum's law objections

    jbandela1, 2024-10 · Recommendation · in “Hash Ordering and Hyrum's Law”

Excerpts from Hacker News comments, linked to the originals. Summaries and labels were written by a language model from those comments.

Topics: swisstable, hash tables, c++, simd, abseil, cache efficiency

Also recommended by the same people