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

在 YouTube 观看

简介

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

相关视频