c – 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执行约8.1秒,如果n == 10000则在3.2秒内执行.注意,内循环始终为0到999,与n的值无关;只是内存地址有什么不同？

根据处理器/架构的不同,由于缓存丢失,我甚至观察到10倍的速度下降.