Bjarne Stroustrup说我们必须避免链接列表

Question

我在YouTube上看到了这个视频:https://www.youtube.com/watch？v = YQs6IC-vgmo,其中Bjarne说最好使用向量而不是链接列表.我无法掌握整个事情,所以任何人都可以用外行的话来解释他说的话吗？

PS:我是一名高中生,可以轻松处理链接列表,但我正在努力学习自己的向量.你能建议学习载体的任何来源吗？

Answer 1

向量与链表的优点

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

通常,每个元素都单独分配在链表中.因此,这些元素在内存中可能并不是彼此相邻的.(内存中元素之间的差距.)

保证向量连续存储所有包含的元素.(彼此相邻的项目,没有差距;)

注意:可能会出现过度简化...;)

Imo,关于连续存储的数据存储模式与非连续存储的卓越性能的简化关键点是

缓存未命中

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

例:

64字节块(通常的高速缓存行大小)一次适合16个32位整数.因此,在从第一个元素进入高速缓存的那一刻开始处理16个元素之后,最早发生高速缓存未命中(尚未在高速缓存中的数据 - >从所需的主存储器加载).如果使用链接列表,则第一个元素可能是64字节块中唯一的元素.从理论上讲,可能会发生列表中每个元素的高速缓存未命中.

具体例子:

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尚未缓存的内容.

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

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

2)从v_0的地址开始从主存储器获取64字节到高速缓存行

3)通过将其值添加到s来从缓存和进程加载v [0]

4)缓存中的元素v 1是什么？ - >是加载了之前的提取因为邻近的v [0]

5)通过将其值添加到s来从缓存和进程加载v 1

6)缓存中的元素v [2]是什么？ - >是的......

7)通过将其值添加到s来从缓存和进程加载v [2]

......等......

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

35)从v [16]的地址开始从主存储器获取64字节到高速缓存行

36)通过将其值添加到s来从缓存和进程加载v [16]

37)元素v [17]是否在缓存中？ - >是加载了以前的提取因为邻近的v [16]

等等...

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

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

2.预取

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

如果已经从主存储器加载了一个块,则预取器准备加载下一个块/已经将其放入缓存中,从而显着降低了从主存储器的该部分加载东西的恶劣性.

当且仅当您实际上需要来自下一个准备好的块的数据时,这当然是有效的.

向量通常如何工作(内部)？

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