Abseil的开源哈希表:两年回顾 - Matt Kulukundis - CppCon 2019
Abseil's Open Source Hashtables: 2 Years In - Matt Kulukundis - CppCon 2019
频道:CppCon · 时长:54:00 · 发布:2019-10-02 · 播放:22120
简介
Matt Kulukundis回顾了Abseil的Swiss table哈希表两年来的发展,涵盖发布后的优化、在谷歌推广的经验教训、设计选择,以及全局监控所揭示的内容。
HN 为什么推荐
HN指出这是关于Swiss table的权威演讲,涉及设计理念和现实影响,如海勒姆定律。
更深入地探讨了为什么这是一个好主意 — HN, 2026
C、C++、Rust、Go 与系统语言 · 软件性能与优化 · 算法与数据结构
中文字幕节选
好的,大家好,我是 Matt Kula Kondos,这是我第二次在 CppCon 做重要演讲,两年前我介绍了那个哈希表的开源项目,它现在 已经开源了,但在开始之前,我想非常明确地说明,这是 许多人的工作,幻灯片上的许多人做了初始工作,许多人做了开源 工作,主要是 schandle 实际完成了开源工作,我 即将展示的幻灯片很大程度上是 Sam Benz akin 的工作,他做了很多 这里的优化,但无论如何我都不是主要甚至 重要贡献者,所以我要开始给大家 简要概述我们要讲的内容,因为这个演讲进展很快,我 在菜单上标记为中级-高级,但那是新西兰 徒步分级系统,不是美国徒步分级系统,所以我们要 探索几个相互关联的大问题,围绕我们的哈希表,我们 在谷歌部署时学到了什么,我们能提高它们的 CPU 效率吗, 我们能改进小表的内存吗,我们能自动 识别大规模下行为异常的表,并以有用的方式吗,所以这 大致就是我们要讲的方向,但我要从背景开始,这里有一大 块内容需要理解,我会快速过一遍我 2017 年 CppCon 演讲的内容, 不涉及任何动机,我只解释给你听,如果你想 理解为什么,回去看我的 2017 年演讲,我希望那还算合理 我还想请大家把问题留到最后,除非是真的很 快的澄清,你相信我能用一两句话回答,所以 就这样,让我们从一些术语开始,我要讲的主要容器是 flat hash set,这有点像 std::unordered_map 的 API, 但更像 vector 而不是链表,它不提供指针 稳定性,它直接在内存中保存值,并在重新哈希时移动它们,它 有一个元数据数组,显然存储关于元素的元数据,它还有 槽数组,实际值存储在那里,逻辑上这些是两个独立的 数组,在实现内部它们只是一个东西,因为没人想 分配两次,所以当我提到位置 3 时,我经常指的是 元数据数组中的控制字节和该位置值所在的槽 存储,所以现在如果我们把16个位置放在一起,就形成了一个组, 随着我进一步展开,你会明白为什么这个16很重要。表本身只包含 n个组 当我们查看时,当我们取哈希码时,通常你从64位哈希码开始, 我们将其分为两部分:h1是57个高位,并不是说我们保证 会继续使用57个高位,但目前是这样,还有这7个低位, 即h2。h1是你取模的部分,就像传统的做法,我要对 表大小取模来找到哈希表中的位置。h2中的7位进入 元数据中的控制字节。我们需要额外的位来更加元。 这是使Swiss table快速的核心洞察。这是 一小段使用SSE的代码,昨晚和Chandler交谈时,我实际上 了解到它使用的是ssse3,但那是一种流式SIMD 扩展,它是一条基本上所有CPU都有的指令,允许你 一次性进行16宽探测,抱歉,是128字节探测。 所以,对,我要把 这个拆分成更小的部分,因为我实际上不会说汇编,而且大多数 人也不应该会。这就是它用图片方式所做的:你给它一个单字节的
HN 上的讨论
Swiss Table 是谷歌首选的哈希表设计,它是你在 Abseil C++ 库中得到的东西,多年来它也是 Rust 的 HashMap 类型背后的实现,如你所见,它现在也是 Go 的 map 的工作方式。[VIDEO] 是 Matt Kulukundis 在 2019 年 CppCon 上的演讲,如果你是一个知道 SIMD 是什么以及缓存如何工作的人,它会更深入地探讨为什么这是一个好主意。 — tialaramex, 2026-07
甚至有一个 CPPCon 演讲关于谷歌的“Swiss”表,每当新代码的可观察行为改变时,Hyrum 就会打断,因为在谷歌,他们内部有足够的用户,使得 Hyrum 定律一直生效:[VIDEO] 这个演讲现场应该更好,因为 Hyrum 没有麦克风,所以他的插话很难听清,但这是一个很好的说明方式。有些例子和这个故事很像,你设计了这个复杂、高度优化的无序容器,用于数百万个项目,然后你的用户放了三个项目进去,他们依赖这些项目的顺序,而你“破坏”了他们的代码,因为你没有提供你从未承诺过的行为,而且依赖它毫无意义。这个线程中提到的防御措施(随机化那些不保证稳定性的东西)被引入是因为这些是谷歌员工,他们知道 Hyrum,但这还不够。当然,当我尝试存储 40 个项目时,由于你的随机化,代码失败了,但我发现存储十个项目时它工作正常,因为随机化被击败了,所以现在我存储十个项目,然后你最新的改变又破坏了它……数… — tialaramex, 2021-06
这是他们在 2019 年演示中声称的改进之一。[VIDEO] 报告查找速度提高 10%,但插入速度降低 15%。速度提升可能来自使用更多 4 位哈希,这导致更少的冲突。而速度降低来自更复杂的镜像代码。我仍然对 SIMD 对齐感到困惑。有带对齐要求的加载指令(_mm_load_si128)和不带对齐要求的(_mm_loadu_si128)。两者声称相同的延迟和吞吐量。我在某处听说未对齐访问的减速来自使用更多带宽来加载两个对齐的 128 位行以组成未对齐值。但不知道这是否影响连续内存的多次加载。 — mizmar, 2025-07
> Abseil、Boost 和 Folly 都提供了类型,如果这是你需要的“即插即用”,它们会牺牲一些性能来恢复这一点。确实,谷歌最初从 std::unordered_map 迁移到 swisstables 时,将所有人迁移到 absl::node_hash_map,因为它更安全,尽管 flat_hash_map 通常提供更好的性能。> 在向你的用户哈希表添加假用户 Alice、Bob 和 Carol 后,当以无特定顺序请求用户时,你得到的正是:Carol、Alice、Bob。哎 :( 这让我想起 Matt Kulukundis 在 cppcon 上谈论从 std::unordered_map 迁移,他正好提出了这一点:[VIDEO] 然后 Matt 继续描述 Abseil 如何为每个哈希表添加一个非确定性的迭代偏移,以防止任何人今后依赖这一点。 — vitus, 2024-06
这里有一个关于这个数据结构的演讲:[VIDEO] 基本上,它存储一个 1 字节标记的数组,包含一个满或空的位和一个 7 位的哈希前缀,然后是一个单独的桶数组。查找首先在前一个数组中加载一个邻域的字节,以找到第一个哈希字节匹配的条目或空条目。如果表负载非常高,或者哈希函数质量低,可以跳过一些检查完整哈希相等或值相等的步骤(前者可能只是缓存未命中,后者可能非常昂贵),但在哈希和负载因子更好的条件下,以及已知连续查找随机性相当差的条件下,避免在标记小数组中做一次加载和在哈希表条目大数组中做另一次加载的成本可能更好。在演讲中,演讲者还说他们改变了第一次加载的方式,使其有时跨越两个缓存行,这使其稍微更昂贵,但这对他们来说仍然是一个胜利。 — anonymoushn, 2022-08
相关视频
- Rust之壳:生命周期注解 · Jon Gjengset · 1:33:23
- CppCon 2015: Kate Gregory “停止教 C” · CppCon · 1:00:11
- Diffie-Hellman 密钥交换 · Art of the Problem · 8:38
- 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
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- RustConf 2018 - 闭幕主题演讲 - 使用 Rust 进行游戏开发 by Catherine West · Rust Programming Language · 42:29
- Erlang Factory 2014 - 那是带 'B' 的 'Billion':在 WhatsApp 扩展到下一个级别 · Erlang Solutions · 49:15
- 古惑狼如何黑掉原版PlayStation | 战争故事 | Ars Technica · Ars Technica · 31:37
- Gil Tene 的 "如何不测量延迟" · Strange Loop Conference · 42:59
- CppCon 2016: Jason Turner “为微型计算机编写丰富代码:用C++17实现一个简单的Commodore 64游戏” · CppCon · 1:19:52
- 关于游戏新编程语言的想法。 · Jonathan Blow · 1:55:24