Bjarne Stroustrup说我们必须避免链接列表 [英] Bjarne Stroustrup says we must avoid linked lists

问题描述

我在YouTube上观看了此视频: https://www.youtube.com/watch ?v = YQs6IC-vgmo Bjarne说最好使用向量，而不是链表.我无法掌握全部内容，所以有人可以用外行的话来解释他在说什么吗?

I saw this video on YouTube: https://www.youtube.com/watch?v=YQs6IC-vgmo in which Bjarne says it is better to use vectors, rather than linked lists. I am unable to grasp the entire thing, so could anyone explain what he is saying in layman's terms?

P.S:我是一名高中生，可以轻松处理链表，但是我一直在努力学习向量.你能建议一些学习向量的资料吗?

P.S: I am an high school student and can easily handle linked lists, but I am struggling to learn vectors on my own. Could you suggest any sources to learn vectors?

推荐答案

向量列表与链接列表的优点

向量列表和链接列表的主要优点是内存局部性.

Advantages of vector vs. linked list

The main advantage of vector versus linked lists is memory locality.

通常，每个元素都是在链表中单独分配的.结果，这些元素在内存中可能并不相邻. (内存中元素之间的间隙.)

Usually, each element is allocated seperately in a linked list. As a consequence those elements probably are not next to each other in memory. (Gaps between the elements in memory.)

保证向量可以连续存储所有包含的元素. (项目彼此相邻，没有间隙；)

A vector is guaranteed to store all contained elements contiguously. (Items next to each other, no gaps;)

注意:过度简化可能会发生...;)

Imo，关于连续存储的数据存储模式与非连续存储的优异性能的简化要点是

Imo, the simplified key points about the superior performance of a contiguously stored data storage pattern versus non-contiguous storage are

现代CPU不会从内存中获取单个字节，而是会获取稍大的块.因此，如果数据对象的大小小于这些块的大小，并且存储是连续的，则一次可以获取多个元素，因为单个块中可能包含多个元素.

Modern CPUs do not fetch single bytes from memory but slightly larger chunks. Thus, if your data objects size is less than the size of those chunks and if storage is contiguous, you can get more than one element at a time because multiple elements may be in a single chunk.

一个64字节的块(通常的高速缓存行大小)一次可容纳16个32位整数.因此，从第一个元素被缓存到缓存中以来，最早处理完16个元素之后，最早会发生缓存未命中(数据尚未缓存在缓存中->需要从主内存中加载).如果使用链表，则第一个元素很可能是64字节块中的唯一元素.从理论上讲，列表的每个元素都可能发生高速缓存未命中.

A 64byte block (usual cache line size) fits sixteen 32bit integers at a time. Therefore, a cache miss (data not in cache yet -> load from main memory required) occurs at the earliest after processing 16 elements from the moment first one has been brought to cache. If a linked list is used, the first element might well be the only one within a 64byte block. It might in theory happen that a cache miss occurs for every single element of the list.

std::vector<std::uint32_t> v;
// somehow fill 64 values into v
std::uint32_t s{};
for(std::size_t i{0}; i<v.size(); ++i)
{
  s += v[i];
}

想象一下v的内容尚未被缓存.

Imagine the contents of v not being cached yet.

在for循环中处理数据期间会发生什么?

1)检查元素v [0]是否在缓存中. ->不可以

1)Check whether element v[0] is in cache. --> Nope

2)从v [0]的地址开始将64个字节从主存储器中提取到缓存行中

2)Fetch 64 bytes starting at the address of v[0] from main memory into a cache line

3)从缓存中加载v [0]并通过将其值添加到s进行处理

3)Load v[0] from cache and process by adding its value to s

4)是元素v 1 在缓存中? ->是，因为相邻v [0]

4)Is element v1 in cache? --> Yes loaded with previous fetch because neighbouring v[0]

5)加载v 1 从缓存中进行处理，方法是将其值添加到s

5)Load v1 from cache and process by adding its value to s

6)元素v [2]是否在缓存中? ->是的...

6)Is element v[2] in cache? --> Yes ...

7)从缓存中加载v [2]并通过将其值添加到s进行处理

7) Load v[2] from cache and process by adding its value to s

...等等...

34)元素v [16]是否在缓存中? ->不可以

34)Is element v[16] in cache? --> Nope

35)从主存储器的v [16]地址开始将64个字节提取到缓存行中

35) Fetch 64 bytes starting at the address of v[16] from main memory into a cache line

36)从缓存中加载v [16]并通过将其值添加到s进行处理

36)Load v[16] from cache and process by adding its value to s

37)元素v [17]是否在缓存中? ->是，因为相邻的v [16]

37)Is element v[17] in cache? --> Yes loaded with previous fetch because neighbouring v[16]

等...

将数据从主存储器读取到缓存中比将数据从缓存加载到处理器寄存器并执行简单操作要花费更多的时间.因此，多个值可能驻留在单个缓存行上这一事实可以显着提高性能.

Fetching data from main memory into the cache takes much more time than loading data from cache into processor registers and perform simple operations. Therefore, the fact that multiple values may reside on a single cache line can boost performance significantly.

链接列表不提供连续的存储保证，您不能希望获得这种性能提升.这也是连续容器的随机迭代(随机访问元素)比正向迭代(顺序访问元素)性能差的原因.

Linked lists do not provide a contiguous storage guarantee and you cannot hope to get this performance boost. This is also the reason why random iteration (accessing elements randomly) performs worse than forward iteration (accessing elements in order) for contiguous containers.

上述效果被称为预取器"的CPU功能放大了.

The above effect is amplified by a CPU feature called "prefetcher".

如果已经从主内存中加载了一个块，则预取器将准备加载下一个块/已将其放入缓存中，从而大大减少了从该部分内存中加载内容的麻烦.

If a chunk has been loaded from main memory, the prefetcher prepares loading the next chunk / already puts it into cache, significantly reducing the penality of loading stuff from that part of the main memory.

仅当您实际上需要下一个准备好的块中的数据时，这才有效.

This is of course effective if and only if you in fact need data from the next prepared chunk.

请参阅: c ++ Vector，每当它在堆栈上扩展/重新分配时会发生什么?

这篇关于Bjarne Stroustrup说我们必须避免链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！