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

Question

在与同事的讨论中，我最终编写了基准测试来测试std::vector和原始动态分配数组，并最终得出了一个惊喜的结果。

我的测试如下：

#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;
}

使用gcc 4.4.3编译，并使用g++ -O3编译。

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

数组：

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

向量：

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

三个结论非常明显：

1. 数组在用户时间上更快
2. 向量在系统时间上更快
3. 总体而言，向量赢得了这场竞争

问题是“为什么？” 我猜系统时间问题可能与页面错误有关，但我无法准确描述为什么会有更多的页面错误。 至于用户时间问题，对我来说不太有趣，但我仍然很好奇对此的看法。我想象中它与初始化有关，但我没有将初始化值传递给向量构造函数，所以我不确定。

- Catskul

---

尝试使用其他类型的向量...这可能与32位整数的向量类优化有关。他们对布尔值进行了优化。 - Patrick87

@Thomas：那就太错了。向量内部使用分配的空间作为数组。vector<bool>是完全不同的东西，是一个设计错误。 - Karoly Horvath

比较汇编代码怎么样？这应该会给你一个很好的想法。 - Kerrek SB

@Kerrek的建议不错，可以帮助回答用户时间问题，但无法回答系统时间问题。 - Catskul

@Catskul：你已经知道答案了：更多的页面错误，你只需要解释为什么如此，而不需要深入到汇编语言，高级C++的解释就足够了：std::vector在构造时默认初始化元素，而你代码中的new没有这样做。数组测试承担了两个容器的成本，而向量测试只有自己的成本。 - David Rodríguez - dribeas

Answer 1

差异不在于向量与动态数组的性能比较，而在于你执行的访问内存次数。实际上，在向量测试中，您正在重新访问缓存的内存，而在数组版本中则不是这样。无论哪种情况下，您都要为缓存向量版本付出代价。在向量测试中，您为数组分配了动态内存，但将其保持不变，由于从未接触该内存，因此没有由此操作引起的页面错误。向量被创建、初始化，然后第二次通过将访问已经缓存的数据（如果大小符合缓存，如果不符合，则不会在缓存中，但在两个版本中将产生相同的代价）。另一方面，在测试数组时，向量构造函数初始化元素，这意味着在尝试分析数组行为的情况下，向量内容将被遍历并且数组元素也将被遍历。这将导致内存访问次数、页面错误和应用程序使用的内存数量增加一倍。您可以尝试修改代码，使动态分配像这样执行：

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

你可以使用值初始化方式初始化整个数组，或者以其他方式初始化数组内容。运行修改后的测试结果应该相似。

- David Rodríguez - dribeas

---

我读了几遍才明白，但重新基准测试表明你是正确的。希望你不介意我编辑你的答案以帮助澄清。 - Catskul

@Catskul：我不介意，我是在深夜写的，问题足够复杂。关键是：在向量基准测试中，您只触及向量内容，在数组基准测试中，您会触及数组和向量内容，因此访问的内存量增加了一倍，带来了所有相关问题。 - David Rodríguez - dribeas

Answer 2

你进行过多次测试吗？基准测试是一个艰难的过程，必须依靠平均值才能得到任何有意义的结果；在运行数组基准测试时可能会有几个 CPU 循环被用于其他事情，从而导致速度变慢。如果给出足够的结果，我会预计它们会相似，因为 std::vector 的内部实现采用了 C 风格的数组。

- Thomas Russell

---

也许这应该是一条注释。 - Nick Rolando

@Nicklamort：啊，好的，抱歉，我不确定是要放在评论还是回答中。 - Thomas Russell

听起来对我来说是一个有效的答案，虽然可能需要再加强一些肯定性。是的，它们应该有相同的表现。 - Karoly Horvath

它们已经运行了数十次，并得到相同的结果。不过想法不错，我会更新并提及这一点。 - Catskul