C++ STL:Array vs Vector:原始元素访问性能

Question

我正在建立一个翻译,因为这次我的目标是原始速度,所以在这个(原始)情况下,每个时钟周期对我都很重要.

您是否有任何经验或信息两者更快:Vector或Array？重要的是我可以访问元素的速度(操作码接收),我不关心插入,分配,排序等.

我现在要把自己从窗户里拉出来说:

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

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

(为什么)我错了？

不,我不能忽视性能差异 - 即使它是如此之小 - 我已经优化并最小化执行操作码的VM的每个其他部分:)

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]

对vector元素的访问看起来几乎相同.

对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第一个变体中的额外指令,该指令必须进行额外的存储器访问.

但是,差异可以忽略不计.并且它很容易被优化到在多访问上下文中完全相同的程度(通过在寄存器中加载目标地址).

因此,当数组可以直接通过数组对象访问而不是通过指针对象时,关于"数组快一点"的声明是正确的.但这种差异的实际价值几乎没有.

Answer 2

你可能正在咆哮错误的树.缓存未命中可能比执行的指令数量重要得多.