CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表”
CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
频道:CppCon · 时长:59:33 · 发布:2017-10-26 · 播放:137843
简介
Matt Kulukundis解释了Google如何从std::unordered_map逐步设计出SwissTable,一个快速、缓存友好的哈希表。演讲涵盖了开放寻址、SIMD探测以及改变基础数据结构的权衡。
HN 为什么推荐
HN反复引用它作为SwissTable的权威解释,这是Abseil、Rust的哈希映射和Go的映射背后的设计。
精彩的演讲,清晰简洁地解释了概念。 — HN, 2026
C、C++、Rust、Go 与系统语言 · 软件性能与优化 · 算法与数据结构
中文字幕节选
大家好。欢迎,我是 Matt Kulukundis。 本次演讲是“逐步设计一个快速、高效、缓存友好的哈希表”。 如果你以为讲的是别的, 请留下,这比你想象的还要好。 相信我。但在开始之前,我想先致谢, 因为这是许多人共同努力的成果。 我并不是其中许多工作的主要作者,我更像是主要的布道者。 我说服人们去做事情,他们听我的,因为他们傻。 按字母顺序,我要感谢 Elcus Evlogimanos, 他可能是所有这些工作的最主要作者。 他完成了大部分编码和许多深入的思考。 来自 Google 的 Jeff Dean,在非常合适的时机 带来了一些绝妙的见解。 还有 Jeffrey Limb,好吧,大家都在 Google。 Jeffrey Limb 做了一些非常底层的汇编微优化。 他的工作实际上不会涉及,因为太底层了。 Roman Periplitza 负责所有疯狂的模板技巧。 Sam Benza 也做了大量的代码审查、模板技巧, 一些优化工作,并且只是 有效地将自己分散到所有工作中。 Sanjay Ghemawat 和 Jeff Dean 同时加入。 提供了一个非常关键的观察。 如果你不知道 Sanjay 和 Jeff Dean,他们就像是一个单一蜂巢思维 在两个身体里行走。 Vitaly Goldstein 在哈希函数方面做了大量工作,并且仍在继续。 这是巨大的团队努力,如果我 不提及这一点,那就太傲慢了,比平时更傲慢。 正如我所说,我们正在逐步设计缓存表。 你可能以前看过这类演讲,对吧? 我从简单的东西开始。 不不不,这是一个关于 C++ 的演讲。 我从简单的东西开始,然后我就会飞速略过它 进入复杂的东西,比你跟上的速度还快。 这类演讲就是这样。 逐步演讲总是这样。 抱歉,这写在合同里了。 不过,让我先给你们几句警告。 在本次演讲中,table、map 和 set 是可以互换的词。 如果我练习得更多,我会总是说 table,但 我不擅长这个,我会把 map 和 set 扔进去迷惑你们, 因为我喜欢那样做。 我说的话,目标是 90% 真实。 完美的保真度会妨碍理解 当你处理如此复杂的话题时。 对吧?90% 真实。 哈希表性能的很大一部分 取决于哈希函数的质量。 有关于此的博士论文,我会略过所有这些。 我只是假设我们有一个好的哈希函数 无论我对好的定义是什么。 我会尽量指出最重要的地方。 但我会漏掉一些,你应该知道,你有一个好的哈希函数。 哈希函数和哈希表之间的交互 非常微妙,通常取决于表的具体实现。 一点背景知识,对吧? 哈希表对性能极其敏感。 在 Google,现在,就在我说话的时候,在我们的集群中, 百分之一的 CPU 正在哈希表内计算某些东西。 就在我说话的时候,超过百分之四的 Google 内存 被哈希表占用,而这还只是在 C++ 中。 我不知道如何获取JAVA的这些数字。
HN 上的讨论
必须推荐 Matt Kulukundis 的原始 Swiss Table 演讲:[VIDEO] 非常棒的演讲,清晰简洁地解释了这些概念。 — lalitmaganti, 2026-07
相关:这个关于 absl::flat_hash_map(boost::unordered_flat_map 的“竞争对手”)制作过程的演讲 [VIDEO] 是我最喜欢的之一。 — KerrickStaley, 2022-11
非常酷!除了对 `aesenc` 和 `aesdec` 的酷炫使用外,跳过随机流和分叉单独流的功能也很棒。> 我目前的家庭项目是用于 GPU 的 SIMD 中的 bump 分配器 + 半空间垃圾回收。据我所知,bump 分配和半空间垃圾回收都可以以明显的方式轻松 SIMD 化。而且由于 cudamalloc 是完全同步的,我想要一个更可扩展、并行的 GPU 内存分配问题解决方案。这是一个好主意。我想知道我们是否可以通过 SIMD 加速 GC 的标记和/或清除阶段来进一步加速 LuaJIT……如果你对这个领域的更多工作感兴趣,一位前同事写了一个简洁的 librsync 的 SPMD 实现 [1]。而且,如果你还没看过,关于 SwissTable [2](谷歌的 SIMD 加速哈希表)的演讲非常出色。[1] [LINK] [2] [VIDEO] — sujayakar, 2021-03
我认为你低估了链式哈希所需的内存重定向次数。不止一次。这是致命伤。重要的是要警惕假设你的数据会在缓存中。通常不会。问题不在于在哈希映射中进行大量高密度搜索,而在于偶尔进行一次搜索。一个进行三次 DRAM 访问的哈希映射总是比只进行一次的差,无论它需要做多少工作,这有两个原因。第一个很明显:RAM 慢得要命,我们明白。第二个更隐蔽。你刚刚驱逐了两个缓存行。不仅仅是查找本身更慢,你还使数据结构的消费者更慢。以下是现代开放寻址的样子:[VIDEO](警告,长达一小时。也需要一段时间才能进入正题。但仍然值得一看。) — nwallin, 2019-10
除了这个评论的兄弟资源外,我还推荐这个非常棒的关于 Swisstable 的 Cppcon 演讲 [VIDEO] — SkiFire13, 2025-07
相关视频
- Bryan Cantrill 谈 Jails 和 Solaris Zones · PapersWeLove · 1:45:46
- Twitter和Visual Studio吐槽 · Molly Rocket · 38:19
- LibreSSL:最初的30天,以及未来走向 · Andrea Ross · 1:05:50
- 与 Shawn McGrath 的模拟面试 · Molly Rocket · 1:41:38
- Robocalypse Now:使用深度学习打击《反恐精英:全球攻势》中的作弊行为 · GDC Festival of Gaming · 1:05:25
- CppCon 2016:Chandler Carruth “垃圾进,垃圾出:关于未定义行为的争论...” · CppCon · 57:39
- CppCon 2015: Herb Sutter "编写良好的 C++14... 默认情况下" · CppCon · 1:29:05
- 3D 高斯泼溅 - 为什么图形学将永远不同 · IndividualKex · 2:12
- Python如何被泄漏的内部机制塑造,Armin Ronacher,Flask框架 · Видео с мероприятий {speach! · 49:55
- CppCon 2015:Andrei Alexandrescu “std::allocator...” · CppCon · 1:12:27
- Go 中的词法扫描 - Rob Pike · GoogleFOSSSydney · 51:17
- 防止文明崩溃 / Jonathan Blow (Thekla, Inc) · DevGAMM · 1:02:41
- Emery Berger 的“性能至关重要” · Strange Loop Conference · 42:15
- 三千万行代码问题 · Molly Rocket · 1:48:55
- RustConf 2018 - 闭幕主题演讲 - 使用 Rust 进行游戏开发 by Catherine West · Rust Programming Language · 42:29
- Erlang Factory 2014 - 那是带 'B' 的 'Billion':在 WhatsApp 扩展到下一个级别 · Erlang Solutions · 49:15