今天我决定对比一下 std::vector 和 std::array 在 GCC 优化能力上的差异。总体来说，我发现了我预期的结果：在一组短数组中执行每个任务要比在等价向量的集合上执行任务快得多。
但是，我发现了一些意想不到的结果：使用std::vector存储数组集合比使用std::array更快。以防这是由于大量数据在堆栈上造成的某种问题，我还尝试将其分配为堆上的数组和 C 风格的堆上数组（但结果仍类似于堆栈上的数组集合和数组的向量）。
有任何想法为什么std::vector会比std::array（编译器在编译时具有更多信息）表现更好吗？
我使用gcc-4.7 -std=c++11 -O3 进行编译（gcc-4.6 -std=c++0x -O3 也应该产生这个难题）。运行时间使用 bash 原生的 time 命令计算（用户时间）。
代码：
#include <array>
#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>
template <typename VEC>
double fast_sq_dist(const VEC & lhs, const VEC & rhs) {
assert(lhs.size() == rhs.size());
double result = 0.0;
for (int k=0; k<lhs.size(); ++k) {
double tmp = lhs[k] - rhs[k];
result += tmp * tmp;
}
return result;
}
int main() {
const std::size_t K = 20000;
const std::size_t N = 4;
// declare the data structure for the collection
// (uncomment exactly one of these to time it)
// array of arrays
// runtime: 1.32s
std::array<std::array<double, N>, K > mat;
// array of arrays (allocated on the heap)
// runtime: 1.33s
// std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >;
// C-style heap array of arrays
// runtime: 0.93s
// std::array<double, N> * mat = new std::array<double, N>[K];
// vector of arrays
// runtime: 0.93
// std::vector<std::array<double, N> > mat(K);
// vector of vectors
// runtime: 2.16s
// std::vector<std::vector<double> > mat(K, std::vector<double>(N));
// fill the collection with some arbitrary values
for (std::size_t k=0; k<K; ++k) {
for (std::size_t j=0; j<N; ++j)
mat[k][j] = k*N+j;
}
std::cerr << "constructed" << std::endl;
// compute the sum of all pairwise distances in the collection
double tot = 0.0;
for (std::size_t j=0; j<K; ++j) {
for (std::size_t k=0; k<K; ++k)
tot += fast_sq_dist(mat[j], mat[k]);
}
std::cout << tot << std::endl;
return 0;
}
NB 1: 所有版本都输出相同的结果。
NB 2: 只是为了演示 std::array<std::array<double，N>，K>、std::vector<std::array<double，N>> 和 std::vector<std::vector<double>> 之间的运行时差异不仅仅是在分配时进行赋值/初始化的原因，只分配集合的运行时间（即注释掉 tot 的计算和打印）分别为0.000s，0.000s和0.004s。
NB 3: 每种方法都单独编译和运行（而不是在同一个可执行文件中反复计时），以避免缓存中的不公平差异。
NB 4:
数组的汇编代码： http://ideone.com/SM8dB
向量数组的汇编代码: http://ideone.com/vhpJv
向量向量的汇编代码: http://ideone.com/RZTNE
NB 5: 只是为了明确，我绝对不打算批评STL。我非常喜欢STL，并且不仅经常使用它，还学到了很多关于C++的微妙和出色特性的细节。相反，这是一种智力追求：我只是计时以学习高效的C++设计原则。
此外，归因于运行时间差异的起因很难分解，因为启用优化时，可能是编译器优化导致代码变慢而不是变快。关闭优化时，可能是不必要的复制操作（在生产代码中将被优化掉并且永远不会执行），这可能对某些数据类型的偏见更大。
如果你像我一样好奇，我会很乐意得到你的帮助来解决这个问题。
N=1000还是K=1000？如果你是指N=1000，那么数组的向量几乎与向量的向量相同（因为不展开循环的开销非常高）。使用N=1会导致向量数组和向量向量之间的差异更大，因为向量数组应该基本上转换为双精度向量。因此，比较数组和向量的最有趣的情况是K << N（在数学意义上而不是位移意义上的<<）。 - uservector测试之后再进行array测试。等等，你是在完全不同的程序中测试它们吗？如果是这样，那我误解了。 - user541686