C++ STL: 数组 vs 向量：原始元素访问性能

Question

我正在构建一个解释器，因为这一次我追求原始速度，所以每个时钟周期对我来说都很重要。

你有没有任何经验或信息来说明哪个更快：Vector还是Array？ 所有关键的是我可以访问一个元素的速度（接收操作码），我不关心插入、分配、排序等。

我现在要冒风险说：

• 在访问一个元素i方面，数组至少比向量快一点。

这对我来说似乎非常合理。使用向量，您需要处理所有那些安全和控制开销，而数组则不存在这些问题。

（为什么）我错了吗？

不，我不能忽略性能差异——即使它非常小——我已经优化并最小化了执行操作码的虚拟机的每个其他部分 ：）

- oh boy

---

如果这对你很重要，编写一个简单的基准测试并计算时间差。而你所说的“安全和控制开销”是指哪些方面？无论如何，这是个重复的问题。 - anon

Op的名字是最好的注释 :) 测量、测量和再测量，这就是答案。 - Maciej Hehl

Answer 1

在一个典型的实现中，使用std::vector访问元素的时间与使用指向对象的普通数组（即运行时指针值）访问元素的时间相同。

std::vector<int> v;
int *pa;
...
v[i];
pa[i]; 
// Both have the same access time

然而，访问可用作数组对象的数组元素的访问时间比上述两种访问方式都要快（相当于通过编译时指针值进行访问）。

int a[100];
...
a[i];
// Faster than both of the above

例如，在x86平台上，通过运行时指针值访问的int数组的典型读取访问将在编译后的代码中如下所示。

// pa[i]
mov ecx, pa // read pointer value from memory
mov eax, i
mov <result>, dword ptr [ecx + eax * 4]

访问向量元素的方式基本相同。

对于作为数组对象可用的本地int数组的典型访问将如下所示。

// a[i]
mov eax, i
mov <result>, dword ptr [esp + <offset constant> + eax * 4]

访问全局 int 数组对象的典型方式如下：

// a[i]
mov eax, i
mov <result>, dword ptr [<absolute address constant> + eax * 4]

性能差异源于第一个变体中多了一条mov指令，这需要额外访问内存。

然而，差异微不足道，并且可以轻松优化到在多次访问的情况下完全相同（通过将目标地址加载到寄存器中）。

因此，“数组稍微快一点”这个说法在狭义情况下是正确的，当数组直接通过数组对象访问而不是通过指针对象访问时。但这种差异的实际价值几乎为零。

- AnT stands with Russia

---

你在说什么？你真的应该用某种机器级描述来说明这将有何不同。 - Potatoswatter

@Potatoswatter：我刚刚添加了一个机器级别的描述。 - AnT stands with Russia

好的。但是这假定数组在堆栈上，而不是在数据结构、通过引用传递或命名空间范围内。它还假定 vector 基指针没有被提升到寄存器中，在循环内是可以预期的。 - Potatoswatter

@Potatoswatter：是的，但首先，当您将vector传递到某个地方时，通常也会通过引用传递它，因此在vector的情况下，您必须进行两次解引用：一次获取vector本身，然后再获取数组本身。因此，我们可以忽略第一个解引用（在两种情况下都是如此），并专注于数组访问本身。其次，正如我自己所说，在多次访问上下文中（例如循环），可以通过将基地址预加载到寄存器中轻松优化掉差异。 - AnT stands with Russia

这就是我来SO寻求答案的详细回复！ - Matthieu M.

有些人喜欢使用数组而不是向量的另一个原因是，向量是动态分配的，这意味着它需要进行新的调用。如果容器不必是动态的，那么我会使用静态数组，因为这样可以少一次新的调用。无论如何，我不知道有任何理由更喜欢动态数组而不是std::vector<>，因为这就是向量在内部所做的。 - xcrypt

Answer 2

你可能正在错误地追寻。相比于执行的指令数量，缓存未命中可能更加重要。

- Jive Dadson

Answer 3

在底层，std::vector和C++0x std::array都是通过将n加到第一个元素的指针上来找到元素n的指针。 vector::at可能比array::at慢，因为前者必须与变量进行比较，而后者与常量进行比较。这些函数提供了边界检查，而不是operator[]。

如果你指的是C风格的数组而不是C++0x std::array，那么就没有at成员，但是要点仍然相同。

编辑：如果你有一个操作码表，一个全局数组（例如使用extern或static链接）可能会更快。当在方括号内放入常量时，全局数组的元素可以像全局变量一样单独寻址，而操作码通常是常量。

总之，这都是过早优化。如果你不使用vector的调整大小功能，它看起来足够像一个数组，你应该能够轻松地在两者之间转换。

- Potatoswatter

---

array<>是什么？OP的问题似乎是关于内置数组，而不是关于某个array<>。内置数组在底层不是指针。 - AnT stands with Russia

@Andrey：内置数组通过内置下标运算符隐式转换为指针，因此我认为它们是。 - Potatoswatter

@Potatoswatter：指针转换纯粹是概念性的，它仅存在于语言层面上（只是为了定义标准文档中“[]”运算符的语义）。所得到的概念性指针是一个编译时值，这意味着一旦我们深入了解，那里就没有真正的指针参与。 - AnT stands with Russia

@Andrey：基础只能在编译时成为常量的唯一方法是作为全局变量。我认为你的意思是它直接偏移自堆栈指针。无论如何，我认为我们都已经表达了自己的观点。 - Potatoswatter

@Potatoswatter：是的，你说得对。但就性能而言，常量栈偏移比显式内存读取更接近于编译时常量，因为偏移寻址通常由单个指令支持（如上面的示例），不需要进行内存读取。 - AnT stands with Russia

Answer 4

你在比较苹果和橙子。数组具有固定的大小并且是自动分配的，而向量具有动态大小并且是动态分配的。你使用哪个取决于你的需求。

通常情况下，数组分配速度“更快”（用引号因为比较毫无意义），因为动态分配速度较慢。但是，访问一个元素应该是相同的。（尽管数组很可能在高速缓存中，但在第一次访问之后这并不重要。）

此外，我不知道你所说的“安全性”，向量与数组一样有很多方法会产生未定义行为。虽然它们有at()函数，但如果您知道索引是有效的，则不需要使用它。

最后，进行性能测试并查看生成的汇编代码。没有人的猜测会解决任何问题。

- GManNickG

Answer 5

为了获得良好的结果，在你的主循环或其他地方之前，使用std::vector作为后备存储，并获取指向其第一个元素的指针。

std::vector<T> mem_buf;
// stuff
uint8_t *mem=&mem_buf[0];
for(;;) {
    switch(mem[pc]) {
    // stuff
    }
}

这样可以避免在operator[]中执行边界检查的实现产生任何问题，并使单步调试更容易，例如在代码后面步入表达式mem_buf[pc]。

如果每个指令都足够努力，并且代码足够复杂，那么使用全局数组比起全局数组，应该会快一些，但不会有明显的差异。(如果差异显著，则需要使操作码更加复杂。)

与使用全局数组相比，在x86上进行这种分派的指令应该更简洁（没有32位位移字段），对于更类似于RISC的目标，应该生成更少的指令（没有TOC查找或尴尬的32位常量），因为常用值都在栈帧中。

我并不确信以这种方式优化解释器的分派循环会产生良好的投资回报 - 如果这是一个问题，指令应该确实地变得更多 - 但我认为尝试几种不同的方法并测量差异不应该花费太长时间。如常所言，在出现意外行为时，应查阅生成的汇编语言（在x86上还应查看机器代码，因为指令长度可能是一个因素）以检查明显的低效率。

- please delete me