我经常读到链表数据结构及其变体跳过列表在并行硬件中是缓存友好的。这是什么意思 ？有人可以用通俗易懂的方式解释一下。
编辑：上下文在 这个链接中。
问问题
893 次
1 回答
7
我经常读到链表数据结构及其变体跳过列表是缓存友好的
链表和类似结构对 CPU 缓存不友好，因为每个节点都可以在内存中随机排列，从而导致许多缓存未命中。
相比之下，一个 ArrayList 将在内存中顺序地拥有所有引用，因此当读入高速缓存行（通常为 64 字节长）时，它可以一次读入 16 个引用。
注意：List 引用的对象仍然可以在内存中随机排列，这是您无法控制的。:|
从问题中的文章。
除了非常适合并发遍历和更新之外，链表在并行硬件上也是缓存友好的。例如，当一个线程移除一个节点时，唯一需要转移到随后读取列表的每个其他内核的内存是包含两个相邻节点的内存。
这里所说的是一个链表在被多个线程同时修改时（LinkedListJava 中不支持的东西）只有被修改的链表的节点需要缓存一致。相比之下，如果在 ArrayList 的中间或开头删除或添加元素，则需要更新所有引用。众所周知，这样做是低效的，无论如何最好避免。
Java 中与此最接近的示例是ConcurrentLinkedQueue支持并发添加和删除。问题是，您可能通过更新缓存的开始和结束而获得的任何好处都会因为此操作创建垃圾这一事实而丢失，这更重要，尽管仍然不是很重要。
如果您使用 ArrayBlockingQueue，您将获得更好的缓存和垃圾行为，因为引用在内存中是连续的，不需要像 ArrayList 那样洗牌，也不会创建垃圾来添加条目。（不幸的是take()创建了一个对象：P）
于 2012-08-30T10:38:57.677 回答