performance - 使用链式与开放式寻址的哈希表中的缓存性能

Question

在以下网站来自 geeksforgeeks.org它指出

Cache performance of chaining is not good as keys are stored using linked list. Open addressing provides better cache performance as everything is stored in same table.

所以我的问题是:

是什么导致链接的缓存性能不佳？

缓存在哪里使用？

为什么开放寻址会提供更好的缓存性能，因为我看不到缓存是如何实现的？

在决定链接和线性探测开放寻址和二次探测开放寻址时，您还考虑什么？

Answer 1

抱歉，由于问题相当广泛，答案也将非常通用，并提供一些链接以获取更详细的信息。

最好从问题开始:

Where is the cache being used?

在现代 CPU 上，缓存无处不在:读取程序指令和读取/写入内存中的数据。在大多数 CPU 上，缓存是透明的，即不需要显式管理缓存。

缓存是 多比主存储器 (DRAM) 快。只是给你一个视角，访问一级缓存中的数据大约是 4 个 CPU 周期，而访问同一 CPU 上的 DRAM 是大约 200 个 CPU 周期，即快 50 倍。

缓存对名为 的小块进行操作缓存行 ，通常为 64 字节长。

更多信息: https://en.wikipedia.org/wiki/CPU_cache

What causes chaining to have a bad cache performance?

基本上，链接不是缓存友好的。这不仅与哈希表中的这种情况有关，“经典”列表也存在同样的问题。

哈希键(或列表节点)彼此远离，因此每次键访问都会产生“缓存未命中”，即慢速 DRAM 访问。因此，检查链中的 10 个 key 需要 10 次 DRAM 访问，即 200 x 10 = 2000我们通用 CPU 的周期。

直到 next 才知道下一个 key 的地址指针是在当前键中读取的，所以没有太多优化空间......

Why would open addressing provide better cache performance as I cannot see how the cache comes into this?

线性探测对缓存友好。键被“聚集”在一起，所以一旦我们访问了第一个键(慢速 DRAM 访问)，很可能下一个键已经在缓存中，因为缓存行是 64 字节。因此，使用开放寻址访问相同的 10 个键需要 1 次 DRAM 访问和 9 次缓存访问，即 200 x 1 + 9 x 4 = 236我们通用 CPU 的周期。它比链式 key 的 2000 个周期快得多。

此外，由于我们以可预测的方式访问内存，因此还有一些优化空间，例如缓存预取: https://en.wikipedia.org/wiki/Cache_prefetching

Also what considerations what you take into account when deciding between chaining and linear probed open addressing and quadratic probed open addressing?

无论如何，链接或线性探测都不是一个好兆头。所以我首先要考虑的是通过使用一个好的散列函数和合理的散列大小来确保冲突的概率最小。

我会考虑的第二件事是现成的解决方案。当然，当您需要自己的实现时，仍然可能有一些罕见的情况......

不确定语言，但这里是使用 BSD 许可证的极快的哈希表实现: http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.h

所以，如果你仍然需要你自己的哈希表实现并且你确实关心性能，那么下一个很容易实现的事情是使用缓存对齐的桶而不是普通的哈希元素。每个元素会浪费很少的字节(即每个哈希表元素的长度为 64 字节)，但在发生冲突的情况下，至少会有一些键的快速存储。管理这些bucket的代码也会稍微复杂一些，所以值得你考虑一下是否值得......