当我们说特定数据结构是缓存友好的时候意味着什么？

Question

我经常读到链表数据结构及其变体跳过列表在并行硬件中是缓存友好的.这是什么意思 ？有人可以用一种易于理解的方式解释.

编辑:上下文位于 此链接中.

Answer 1

我经常读到链表数据结构及其变体跳过列表是缓存友好的

链表和类似结构不是CPU缓存友好的,因为每个节点可以随机排列在内存中,导致许多缓存未命中.

相比之下,ArrayList将在内存中顺序包含所有引用,因此当读入缓存行(通常为64字节长)时,它可以一次读取16个引用.

注意:List引用的对象仍然可以随机排列在内存中,这是您无法控制的.:|

从问题中的文章.

除了非常适合并发遍历和更新之外,链接列表在并行硬件上也是缓存友好的.例如,当一个线程移除一个节点时,需要传输到随后读取列表的每个其他核心的唯一存储器是包含两个相邻节点的存储器.

这就是当一个链接列表被多个线程同时修改(LinkedListJava中的某些东西不支持)时,只需要修改列表中的节点需要使缓存一致.相比之下,如果在ArrayList的中间或开头删除或添加元素,则需要更新所有引用.已知这是低效的,在任何情况下都最好避免.

Java中最接近于此的示例是ConcurrentLinkedQueue支持并发添加和删除.问题是,由于此操作会产生更重要的垃圾,但仍然不是非常重要,因此可以通过能够更新缓存方面的开始和结束而获得的任何好处都会丢失.

如果使用ArrayBlockingQueue,则会获得更好的缓存和垃圾行为,因为引用在内存中是连续的,不需要像ArrayList一样向下移动,也不要创建垃圾来添加条目.(不幸的是take()创建了一个对象:P)