C STL：数组与向量：原始元素访问性能

Question

我正在构建一个解释器，因为这次我的目标是原始速度，所以在这种（原始）情况下，每个时钟周期对我来说都很重要。

您是否有任何经验或信息两者中的哪一个更快：向量或数组？重要的是我可以访问元素的速度（操作码接收），我不关心插入、分配、排序等。

我现在要靠在窗外说：

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

这对我来说似乎很合乎逻辑。使用向量，您可以获得数组不存在的所有安全性和控制开销。

（为什么）我错了吗？

不，我不能忽略性能差异——即使它是 如此之 小——我已经优化并最小化了执行操作码的 VM 的所有其他部分:)

原文由 oh boy 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

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

// 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 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

No. Under the hood, both std::vector and C++0x std::array find the pointer to element n by adding n to the pointer到第一个元素。

vector::at 可能比 array::at 慢，因为前者必须与变量进行比较，而后者必须与常数进行比较。 这些 是提供边界检查的功能，而不是 operator[] 。

如果您的意思是 C 样式数组 而不是 C++0x std::array ，那么没有 at 成员，但重点仍然存在。

编辑： 如果您有操作码表，则全局数组（例如 extern 或 static 链接）可能会更快。当一个常量放在括号内时，全局数组的元素可以作为全局变量单独寻址，并且操作码通常是常量。

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

原文由 Potatoswatter 发布，翻译遵循 CC BY-SA 2.5 许可协议