Bjarne Stroustrup 说我们必须避免链表

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

P.S:我是一名高中生,可以轻松处理链表,但我很难自己学习向量.你能推荐任何学习向量的来源吗?

zhaojun730730 回答:Bjarne Stroustrup 说我们必须避免链表

向量 vs. 链表的优势

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

Advantages of vector vs. linked list

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

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

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

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

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

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

一个 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 的内容还没有被缓存.

在for循环中处理数据的过程中会发生什么?

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

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

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

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

4)是元素 v1 在缓存中?--> 是加载了先前的提取,因为相邻的 v[0]

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

5)加载 v1 从缓存和进程中通过将其值添加到 s

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

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

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

...等等...

34) 元素 v[16] 是否在缓存中?--> 没有

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

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

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

37) 元素 v[17] 是否在缓存中?--> 是加载了先前的提取,因为相邻的 v[16]

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

等等...

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

链表不提供连续存储保证,您不能指望获得这种性能提升.这也是为什么连续容器的随机迭代(随机访问元素)比前向迭代(按顺序访问元素)表现更差的原因.

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

如果一个块已经从主内存加载,预取器准备加载下一个块/已经将它放入缓存,显着减少从主内存的那部分加载内容的惩罚.

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

参见:c++向量,每当它在堆栈上扩展/重新分配时会发生什么?

这篇关于Bjarne Stroustrup 说我们必须避免链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持前端之家!

本文链接:https://www.f2er.com/3186439.html

大家都在问