为什么std :: vector比原始动态分配的数组更快？

Question

与同事讨论的结果我最终编写了测试std::vectorvs原始动态分配数组的基准测试,结果出人意料.

我的测试如下:

#include "testconsts.h" // defines NUM_INTS across all tests
#include <vector>

int main()
{
    const int numInts = NUM_INTS;
    std::vector<int>                     intVector( numInts );
    int * const                          intArray       = new int[ numInts ];

    ++intVector[0]; // force access to affect optimization
    ++intArray[0];  // force access to affect optimization

    for( int i = 0; i < numInts; ++i )
    {
        ++intArray[i];
    }

    delete[] intArray;
    return 0;
}

和:

#include "testconsts.h" // defines NUM_INTS across all tests
#include <vector>

int main()
{
    const int numInts = NUM_INTS;
    std::vector<int>                     intVector( numInts );
    int *                                intArray       = new int[ numInts ];

    ++intArray[0];  // force access to affect optimization
    ++intVector[0]; // force access to affect optimization

    for( int i = 0; i < numInts; ++i )
    {
        ++intVector[i];
    }

    delete[] intArray;
    return 0;
}

它们使用g ++ 4.4.3编译为g ++ -O3

多次运行基准测试的结果time类似于:

阵:

real    0m0.757s
user    0m0.176s
sys     0m0.588s

向量:

real    0m0.572s
user    0m0.268s
sys     0m0.304s

有三件事是清楚的:

1. 数组在用户时间更快
2. 矢量更快,系统时间更短
3. 在所有的矢量赢得了这场斗争

问题是"为什么？".

我猜测的系统时间问题必须与页面错误有关,但我无法准确地描述为什么会出现明显更多的页面错误.

至于用户时间问题,它对我来说不那么有趣,但我仍然对这方面的意见很好奇.我曾经想象它与初始化有关,虽然我没有将初始化值传递给向量构造函数,所以我不知道.

Answer 1

与动态数组相比,差异不在于向量的性能,而在于您执行的对内存的访问次数.

实际上,在向量测试中,您将重新访问缓存内存,而在阵列版本中则不会.在任何一种情况下,您都要支付缓存矢量版本的价格.

在向量测试中,您为数组分配动态内存但保持不变,内存永远不会被触及,因此操作不会出现页面错误.创建,初始化向量,然后第二遍将访问已缓存的数据(如果大小适合缓存,如果不适合,则不会在缓存中,但在两个版本中将产生相同的成本).

在另一方面测试数组时,矢量构造函数初始化的元素,这意味着,在案件中你试图剖析数组的行为,矢量内容,走过去和数组元素的走了过来.将应用程序使用的内存访问次数,页面错误和内存加倍.

您可以尝试修改代码,以便执行动态分配,如下所示:

int * intArray = new int[ numInts ](); // note extra ()

哪个将初始化整个数组,或者初始化数组内容,如何.运行该测试的修改版本的结果应该是类似的.