vector :: operator []开销

Question

显然,在分析了我的(科学计算)C++代码之后,25%(!)的时间用于调用vector::operator[].是的,我的代码花费了所有的时间来读取和写入vector<float>s(以及一些vector<int>s),但是,我仍然想知道operator[]与C风格的数组相比是否应该有一些显着的开销？

(我已经看到了关于SO的另一个相关问题,但关于[]vs at()- 但显然[]对我来说太慢了？!)

谢谢,安东尼

(编辑:仅供参考:在Ubuntu上使用g ++ -O3版本4.5.2)

Answer 1

在现代编译器中,在发布模式下,启用优化后,与原始指针相比,使用时不会产生任何开销operator []:调用完全内联并解析为指针访问.

我猜你在某种程度上复制了赋值中的返回值,这导致在指令中花费了25%的实际时间.[ float与int] 无关

或者你的其余代码非常快.

Answer 2

是的,会有一些开销,因为通常vector会包含指向动态分配的数组的指针,而数组就是"那里".这意味着在数组vector::operator[]上使用时通常会有额外的内存取消引用[].(注意,如果你有一个指向数组的指针,这通常不比a好vector.)

如果您通过同一vector代码或同一代码段中的指针执行多次访问而不会导致向量可能需要重新分配,则此额外取消引用的成本可能会在多次访问时共享,并且可能可以忽略不计.

例如

#include <vector>
extern std::vector<float> vf;
extern float af[];
extern float* pf;

float test1(long index)
{
        return vf[index];
}

float test2(long index)
{
        return af[index];
}

float test3(long index)
{
        return pf[index];
}

在g ++上为我生成以下代码(一些guff trimmed):

.globl _Z5test1i
        .type   _Z5test1i, @function
_Z5test1i:
        movq    vf(%rip), %rax
        movss   (%rax,%rdi,4), %xmm0
        ret
        .size   _Z5test1i, .-_Z5test1i

.globl _Z5test2i
        .type   _Z5test2i, @function
_Z5test2i:
        movss   af(,%rdi,4), %xmm0
        ret
        .size   _Z5test2i, .-_Z5test2i

.globl _Z5test3i
        .type   _Z5test3i, @function
_Z5test3i:
        movq    pf(%rip), %rax
        movss   (%rax,%rdi,4), %xmm0
        ret
        .size   _Z5test3i, .-_Z5test3i

注意指针和矢量版本如何生成完全相同的代码,只有数组版本"获胜".

Answer 3

一般来说,应该没有明显的区别.但是,由于各种原因,实际上会出现差异,具体取决于编译器如何优化特定的代码位.一个重要的可能区别:您正在进行分析,这意味着您正在执行已检测的代码.我不知道你正在使用什么样的分析器,但是在编译分析时,编译器经常出于各种原因关闭内联.你确定在这里不是这种情况,并且这是人为地导致索引看起来比内联的时间更长.

Answer 4

std::vector::operator[] 应该是相当有效的,但编译器必须是偏执的,并且对于对函数的每次调用,它必须假定向量可能已被移动到内存中的其他位置.

例如,在此代码中

for (int i=0,n=v.size(); i<n; i++)
{
    total += v[i] + foo();
}

如果foo事先不知道代码,则编译器每次都被迫重新加载向量启动的地址,因为该向量可能由于内部代码而被重新分配foo().

如果您确定该向量不会在内存中移动或重新分配,那么您可以将此查找操作分解为类似

double *vptr = &v[0]; // Address of first element
for (int i=0,n=v.size(); i<n; i++)
{
    total += vptr[i] + foo();
}

使用这种方法可以保存一个内存查找操作(vptr很可能最终在整个循环的寄存器中).

效率低下的另一个原因可能是缓存垃圾.要查看这是否是一个问题,一个简单的技巧就是通过一些不均匀的元素来过度分配向量.

原因在于,如果你有很多向量,例如4096个元素,缓存是如何工作的,它们都会在地址中碰巧有相同的低位,你可能会因高速缓存行失效而失去很多速度.例如我的电脑上的这个循环

std::vector<double> v1(n), v2(n), v3(n), v4(n), v5(n);
for (int i=0; i<1000000; i++)
    for (int j=0; j<1000; j++)
    {
        v1[j] = v2[j] + v3[j];
        v2[j] = v3[j] + v4[j];
        v3[j] = v4[j] + v5[j];
        v4[j] = v5[j] + v1[j];
        v5[j] = v1[j] + v2[j];
    }

如果n == 8191在3.2秒内,则在大约8.1秒内执行n == 10000.请注意,内部循环始终为0到999,与值无关n; 不同的是内存地址.

根据处理器/体系结构的不同,由于缓存垃圾,我甚至观察到10倍速度下降.