std :: vector如何比普通数组更快？

Question

在对循环缓冲区进行基准测试时,我偶然发现了这一点.任何人都可以解释一下std :: vector如何在这个实例中胜过普通数组？

#include <iostream>
#include <vector>

struct uint_pair {
    unsigned int a, b;
    uint_pair (unsigned int x = 0, unsigned int y = 0) : a(x), b(y) {}
};

struct container {
    unsigned int pos;

#ifdef USE_VECTOR
    std::vector<uint_pair> data;
    container() : pos(0) { data.resize(16); }
#else
    uint_pair data[16];
    container() : pos(0) {}
#endif

    void add(uint_pair val) {
        data[++pos % 16] = val;
    }
};

int main() {
    container c;
    for (unsigned int i = 0; i < 1000000000; i++) c.add(uint_pair{i, i});
    std::cout << c.data[0].a << " " << c.data[0].b << std::endl;
}

这些是我使用GCC的结果(类似于Clang):

g++ -o bench -std=c++0x -Os main.cpp -D'USE_VECTOR'
real    0m8.757s
user    0m8.750s
sys     0m0.002s

g++ -o bench -std=c++0x -Os main.cpp
real    0m9.215s
user    0m9.209s
sys     0m0.002s

Answer 1

这是你如何消除差异.而不是你add,使用这样的函数:

void set(unsigned int x, unsigned int y) {
    ++pos;
    data[pos % 16].a = x;
    data[pos % 16].b = y;
}

像这样叫:

for (unsigned int i = 0; i < 1000000000; i++) c.set(i, i);

这与您的完全相同,但它避免了语义上创建临时对象.看起来当你使用向量时,编译器能够更好地优化临时.

$ g++-4.8 -o bench -std=c++11 -Os main.cpp -DUSE_VECTOR
$ time ./bench 
999999999 999999999

real    0m0.635s
user    0m0.630s
sys 0m0.002s

$ g++-4.8 -o bench -std=c++11 -Os main.cpp
$ time ./bench 
999999999 999999999

real    0m0.644s
user    0m0.639s
sys 0m0.002s

在我的机器无论是set和add方法产生具有矢量相同的性能.只有阵列显示出差异.为了进一步提高优化,如果使用-O0进行编译,那么数组方法会稍快一些(但是比使用-Os慢10倍).

这并不能解释为什么编译器会以不同的方式处理这两者.毕竟,矢量是由数组支持的.此外,std::array行为与您的C风格数组相同.