在以下来自geeksforgeeks.org的网站中,它说明了这一点
链接的缓存性能不好,因为密钥是使用链表存储的.由于所有内容都存储在同一个表中,因此开放式寻址可提
所以我的问题是:
是什么导致链接具有错误的缓存性能？
缓存在哪里使用？
为什么开放寻址会提供更好的缓存性能,因为我看不到缓存是如何进入的？
在决定链接和线性探测开放寻址和二次探测开放寻址之间时,您还要考虑什么？
Andriy Beres..
10
对不起,由于问题非常广泛,答案也会非常通用,有些链接可以提供更详细的信息.
最好从问题开始:
缓存在哪里使用？
在现代CPU上,缓存随处可见:读取程序指令和读取/写入内存中的数据.在大多数CPU上,缓存是透明的,即不需要显式管理缓存.
缓存是多比主存储器(DRAM)更快.为了给您一个透视图,访问1级缓存中的数据大约是4个CPU周期,而访问同一CPU上的DRAM大约是200个CPU周期,即快50倍.
缓存在称为缓存行的小块上运行,缓存行通常为64字节长.
更多信息:https://en.wikipedia.org/wiki/CPU_cache
是什么导致链接具有错误的缓存性能？
基本上,链接不是缓存友好的.这不仅仅是哈希表中的这种情况,与"经典"列表相同.
散列键(或列表节点)彼此远离,因此每个键访问都会产生"高速缓存未命中",即缓慢的DRAM访问.因此,检查链中的10个密钥需要10个DRAM访问,即200 x 10 = 2000我们的通用CPU的循环.
next在当前密钥中读取指针之前,不知道下一个密钥的地址,因此优化空间不大......
为什么开放寻址会提供更好的缓存性能,因为我看不到缓存是如何进入的？
线性探测是缓存友好的.密钥"聚集"在一起,因此一旦我们访问第一个密钥(慢速DRAM访问),很可能下一个密钥将已经在缓存中,因为缓存行是64字节.因此,使用开放寻址访问相同的10个密钥需要1个DRAM访问和9个缓存访问,即200 x 1 + 9 x 4 = 236我们的通用CPU的循环.对于链式密钥,它比2000个周期快得多.
此外,由于我们以可预测的方式访问内存,因此可以进行缓存预取等优化:https://en.wikipedia.org/wiki/Cache_prefetching
在决定链接和线性探测开放寻址和二次探测开放寻址之间时,您还要考虑什么？
无论如何,链接或线性探测都不是一个好兆头.因此,我要考虑的第一件事是通过使用良好的散列函数和合理的散列大小来确保冲突的概率最小.
我要考虑的第二件事是即用型解决方案.当然,当您需要自己的实施时,仍然可能会出现一些罕见的情况......
不确定语言,但这里有使用BSD许可证的快速哈希表实现:http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.h
因此,如果你仍然需要自己的哈希表实现并且你关心性能,那么下一个很容易实现的方法是使用缓存对齐的桶而不是普通的哈希元素.每个元素会浪费几个字节(即每个哈希表元素长度为64字节),但是在发生冲突的情况下,至少有几个密钥会有一些快速存储.管理这些存储桶的代码也会有点复杂,所以考虑一下你是否值得为之烦恼......
1> Andriy Beres..：
对不起,由于问题非常广泛,答案也会非常通用,有些链接可以提供更详细的信息.
最好从问题开始:
缓存在哪里使用？
在现代CPU上,缓存随处可见:读取程序指令和读取/写入内存中的数据.在大多数CPU上,缓存是透明的,即不需要显式管理缓存.
缓存是多比主存储器(DRAM)更快.为了给您一个透视图,访问1级缓存中的数据大约是4个CPU周期,而访问同一CPU上的DRAM大约是200个CPU周期,即快50倍.
缓存在称为缓存行的小块上运行,缓存行通常为64字节长.
更多信息:https://en.wikipedia.org/wiki/CPU_cache
是什么导致链接具有错误的缓存性能？
基本上,链接不是缓存友好的.这不仅仅是哈希表中的这种情况,与"经典"列表相同.
散列键(或列表节点)彼此远离,因此每个键访问都会产生"高速缓存未命中",即缓慢的DRAM访问.因此,检查链中的10个密钥需要10个DRAM访问,即200 x 10 = 2000我们的通用CPU的循环.
next在当前密钥中读取指针之前,不知道下一个密钥的地址,因此优化空间不大......
为什么开放寻址会提供更好的缓存性能,因为我看不到缓存是如何进入的？
线性探测是缓存友好的.密钥"聚集"在一起,因此一旦我们访问第一个密钥(慢速DRAM访问),很可能下一个密钥将已经在缓存中,因为缓存行是64字节.因此,使用开放寻址访问相同的10个密钥需要1个DRAM访问和9个缓存访问,即200 x 1 + 9 x 4 = 236我们的通用CPU的循环.对于链式密钥,它比2000个周期快得多.
此外,由于我们以可预测的方式访问内存,因此可以进行缓存预取等优化:https://en.wikipedia.org/wiki/Cache_prefetching
在决定链接和线性探测开放寻址和二次探测开放寻址之间时,您还要考虑什么？
无论如何,链接或线性探测都不是一个好兆头.因此,我要考虑的第一件事是通过使用良好的散列函数和合理的散列大小来确保冲突的概率最小.
我要考虑的第二件事是即用型解决方案.当然,当您需要自己的实施时,仍然可能会出现一些罕见的情况......
不确定语言,但这里有使用BSD许可证的快速哈希表实现:http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_cuckoo_hash.h
因此,如果你仍然需要自己的哈希表实现并且你关心性能,那么下一个很容易实现的方法是使用缓存对齐的桶而不是普通的哈希元素.每个元素会浪费几个字节(即每个哈希表元素长度为64字节),但是在发生冲突的情况下,至少有几个密钥会有一些快速存储.管理这些存储桶的代码也会有点复杂,所以考虑一下你是否值得为之烦恼......
京公网安备 11010802041100号