c++ - Bjarne Stroustrup 说我们必须避免链表

Question

我在 YouTube 上看到了这个视频:https://www.youtube.com/watch?v=YQs6IC-vgmo其中 Bjarne 说最好使用 vector ，而不是链表。我无法掌握全部内容，所以谁能通俗地解释一下他在说什么？

P.S:我是一名高中生，可以轻松处理链表，但我很难自学 vector 。你能推荐任何学习 vector 的资源吗？

Answer 1

vector 与链表的优势

vector 相对于链表的主要优势是内存局部性。

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

vector 保证连续存储所有包含的元素。 (项目彼此相邻，没有间隙；)

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

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

1。缓存未命中

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

示例:

一个 64 字节的 block (通常的缓存行大小)一次适合 16 个 32 位整数。因此，缓存未命中(数据尚未在缓存中 -> 需要从主内存加载)最早发生在从第一个元素被带到缓存的那一刻起处理完 16 个元素之后。如果使用链表，第一个元素很可能是 64 字节 block 中的唯一元素。理论上，列表的每个元素都可能发生缓存未命中。

具体例子:

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)Check whether element v[0] is in cache. --> Nope

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

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

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

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

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

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

... etc...

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

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

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

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

etc...

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

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

2。预取

上述效果被称为“预取器”的 CPU 功能放大。

如果一个 block 已经从主内存加载，预取器准备加载下一个 block /已经将它放入缓存，显着减少从主内存的那部分加载东西的惩罚。

当且仅当您实际上需要下一个准备好的 block 中的数据时，这当然有效。

vector 通常如何工作(内部)？

参见:c++ Vector, what happens whenever it expands/reallocate on stack?