std::vector<A>与std::vector<A*>在CPU方面的区别

Question

让我们讨论一个情况：当我有一个巨大的 std::vector 时，我需要迭代所有元素并调用 print 函数。有两种情况。如果我将对象存储在向量中，并且对象将相邻存储，则对象将在内存中分布。或者，我在堆上分配我的对象，并将对象的指针存储在向量中。在这种情况下，对象将分布在整个 RAM 中。

如果对象的副本存储在 std::vector 中，则当 CPU 将数据从 RAM 带到 CPU 缓存时，它会带来包含向量的多个元素的一块内存。在这种情况下，当您对每个元素进行迭代并调用函数时，您知道将处理多个元素，只有然后 CPU 才会去 RAM 请求其余部分的数据以进行处理。这很好，因为 CPU 没有太多空闲周期。

那么 std::vector 的情况呢？当它带来一组指针时，CPU 是否容易通过指针获取对象？还是应该从 RAM 请求调用某些函数的对象，这将导致缓存未命中和空闲 CPU 周期？从性能方面而言，与以上情况相比如何？

- Narek

---

使用 std::vector<A>。它既易读又足够高效。 - Shoe

就性能而言，从纯粹阅读向量的狭窄视角来看，使用std::vector<A *>永远不会更快，甚至可能更慢。例如，假设您的对象非常小且分散在内存中，则性能将受到影响，因为如果使用vector<A>，则可以获得更好的缓存性能。 - kec

我向您推荐Herb Shutter在BUILD 2014的演讲：http://channel9.msdn.com/Events/Build/2014/2-661。他谈到了缓存一致性的重要性，比较了`std::vector`和C#/Java数组，它们只是`std::vector<A*>`的不同表现形式。 - Manu343726

@Manu343726 谢谢你提供的链接。这个视频太棒了。 :) - Narek

@Manu343726 请将Herb Sutter的视频作为答案发布，并注明他开始谈论主题的时间，这样我就可以接受它作为答案。这真是太棒了。 - Narek

Answer 1

至少在典型情况下，当CPU从内存中获取指针（或多个指针）时，它通常不会自动获取这些指针所指向的数据。

因此，在指针的向量的情况下，当您加载每个指针所引用的项目时，通常会出现缓存未命中，并且访问速度会比连续存储要慢得多。特别是当每个项目相对较小，因此一些项目可以适合单个高速缓存行（对于某个级别的高速缓存-请记住当前处理器通常有两到三个级别的高速缓存，每个级别可能具有不同的行大小）。

然而，可以在一定程度上减轻这种情况。您可以重载operator new来控制分配该类对象的分配。使用这个方法，您至少可以使该类的对象在内存中保持在一起。这并不能保证特定向量中的项目是连续的，但可以改善局部性以使速度明显提高。

还要注意，向量通过Allocator对象（默认为std::allocator<T>，其又使用new）来分配其数据。虽然接口有些混乱，因此比通常希望的要难一些，但如果愿意，可以定义一个分配器以不同的方式运行。这通常不会对单个向量产生太多影响，但如果您有许多向量（每个大小固定）并希望它们使用相邻的内存，则可以通过分配器对象实现。

- Jerry Coffin

Answer 2

如果我把对象存储在向量中，那么对象将相邻地存储在内存中，或者我在堆上分配我的对象。无论使用std::vector<A>还是std::vector<A *>，向量的内部缓冲区都将在堆中分配。您可以使用高效的内存池来管理分配和删除，但仍然需要在堆上处理数据。

与上述情况相比，从性能方面来看是否不好？

在使用std::vector<A *>的情况下，如果没有专门的内存管理，您可能会很幸运地进行分配并始终获得良好对齐的数据，但通常最好通过std::vector<A>执行连续分配。在前一种情况下，重新分配整个向量可能需要更长时间（因为指针通常比常规结构体小），但它将受到局部性的影响（考虑内存访问）。

- Rubens

Answer 3

当它带来一堆指针时，CPU易于通过指针获取对象吗？

不，它不容易。在 CPU 拉取“解引用”指令之前，CPU 不知道它们是指针（CPU 看到的只是一堆位，没有语义参与）。

还是说它应该从 RAM 请求调用某些函数的对象，这样就会出现缓存未命中和空闲 CPU 周期？

没错。CPU 将尝试加载对应于已缓存指针的数据，但很可能该数据位于最近访问的内存远处，因此会出现缓存未命中。

与上述情况相比，性能方面是否更糟糕？

如果您唯一关心的是访问元素，则是的，这很糟糕。但在某些情况下，指针向量更可取。也就是说，如果您的对象不支持移动（C++11 还不是主流），则向量复制变得更加昂贵。即使您不复制您的向量，也可能存在这样的情况：您事先不知道存储的元素数量，因此无法提前调用 reverse(n)。然后，当向量耗尽其容量并被强制调整大小时，所有对象都将被复制。

但最终取决于具体类型。如果您的对象很小（小结构体、整数或浮点数），那么由于指针开销过大，复制它们显然更好。

- Artem Sobolev