C++Now 2018: 你可以比 std::unordered_map 做得更好:哈希表性能的新改进

C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance

频道:CppNow · 时长:1:30:53 · 发布:2018-06-09 · 播放:62997

在 YouTube 观看

简介

Malte Skarupke 在 C++Now 2018 上关于哈希表性能的演讲,解释了为什么 std::unordered_map 速度慢且内存消耗大,并提出了更快的设计,包括他的 bytell 哈希表。

HN 为什么推荐

推荐为对哈希表设计权衡的全面、备受好评的解释,以及为什么标准容器是一个糟糕的选择。

许多关于哈希表的视频都很棒。我觉得这个特别好。 — HN, 2024

C、C++、Rust、Go 与系统语言 · 软件性能与优化 · 算法与数据结构

中文字幕节选

欢迎来到我的演讲,你可以做得比 std 更好,以及哈希表的最新改进。 我一开始给你看这个图,它只是展示我们将获得的改进量。 整个演讲中,我们从非常慢的表开始, 最终会得到一个非常快的表,这只是一个初步指标, 我们会达到目标,但主要是到时候再说。这个演讲会有很多图表, 所以不妨从一个开始。我叫 Malte Skarupke, 是纽约 Avalanche Studios 的 AI 程序员。我去年也在这里, 在同一个房间做了一个关于基数排序的演讲,我对其进行了泛化, 使排序速度更快,达到 n log n。我仍然觉得更多人应该使用它, 所以我想再次提及。但这个演讲是关于哈希表的, 显然这是一个极其重要的数据结构,有人说是最重要的, 而且近年来似乎有一些新进展,因为我认为我在这里写的是, unordered_map 有点慢,这其实是一种伪装的好处, 因为很多人出去思考他们能做得比标准 map 更好, 而且通常他们能做到,然后我们看到了非常好的发展,在 C++ 中的哈希表 在过去几年里。所以这个演讲将是我谈论我 多年来断断续续研究哈希表,以及我学到的关于它们的东西, 改进是什么,然后最后我还展示一个新的哈希表, 这些都是为这个演讲准备的,这将是我新的最喜欢的哈希表, 有很多好的特性。首先,作为基线, 我想测量标准容器的性能, 包括有序容器,如你所要求。这里是一个图表,测量标准 unordered_map 中的查找时间。 所以这是,我创建了一个基准测试,其中 我创建一个特定大小的 unordered_map,大小在 x 轴上,比如 要么有四个元素,要么四百万,或其他大小,然后我所做的是 在一个循环中,我反复调用这个 map 的 find,查找的键 实际上会在这个 map 中,所以这些都是成功的查找,然后 发生的是,当表最小时,或者我忘记的另一件事是, 在循环结束时,我测量查找花了多长时间,然后除以 迭代次数,这给出了平均查找时间。所以 在那个基准测试中发生的是,在左侧当表很小时,因为 我们在循环中不断访问它,它很快会进入缓存,然后所有 查找都会相当快,我们会得到这些不错的低性能,低 查找键的时间数字。然后在右侧,当表 太大无法放入缓存时,我们将不得不更多地访问内存, 那时表真的应该慢下来。所以你可以 看到 L3 缓存结束的确切位置,如果它在 L3 缓存中,我们不会花很长时间, 奇怪的是,一旦超出,就会急剧下降,变得慢得多。所以我想将此与 其他标准容器进行比较。所以我要,但要做到这一点,我应该放大 这个第一段,从大小 4 到 40。所以如果我们放大,我们看到 测量中有一些噪声,但让我们忽略噪声,我们看到它 徘徊在 12 纳秒左右,在这个 map 中查找一个项,这是如果你 不断访问它,而且它已经全部在缓存中。现在我们要添加标准 map 到这个, 在这个大小下,它快得多,这应该让你惊讶,因为如果

HN 上的讨论

许多关于哈希表的视频都很棒。我发现这个特别好。[ [VIDEO] ] C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance — ww520, 2024-10
它具有哈希映射正确的渐近保证,但除此之外它没有什么优点。它强调指针/迭代器稳定性和任意负载因子的程度在几乎所有实际情况下都不是一个好的权衡(除非你不关心性能)。参见[VIDEO]进行更全面的讨论,或者这里的兄弟线程。 — MauranKilom, 2021-08
在我的例子中,表存储的是哈希码本身而不是键(因为哈希函数是可逆的) 哦,我明白了,对。如果确定主桶是简单的,那么反向移位方法很棒。问题只是它不像最初看起来那样是一个通用的解决方案。在糟糕的情况下,它真的很糟糕。使用不同的算法(Robin Hood或双向线性探测),负载因子可以保持在90%以上并具有良好的性能,正如同一仓库中的基准测试所证明的那样。我在关于Robin Hood哈希表的文献中多次看到90%的说法。根据我的经验,这个说法有点夸张,尽管我想这取决于我们对“良好性能”的定义。参见这些基准测试,它们再次达到最大负载因子0.95(尽管boost和Absl在0.85-0.9时强制增长/重新哈希):[LINK] Tsl、Martinus和CC都是Robin Hood表(分别是[LINK]、[LINK]和[LINK])。Absl(来自Google)和Boost是著名的基于C++ SIMD的哈… — JacksonAllan, 2023-11
> 某种桶优化(每次分配多个元素,而不是每次分配一个元素)也应该满足标准为此设定的所有约束 我相当确定那样会使在不使指针/迭代器失效的情况下实现merge成为不可能,而这是标准施加的约束([LINK])。> 如果最初被我回复的人能站出来捍卫他的观点,那就好了 如果你想看数据,请参见[LINK],或者例如同一作者的这次演讲[VIDEO]。 — MauranKilom, 2021-08

相关视频