std::vector比普通数组快在哪里？

Question

std::vector比普通数组快在哪里？

11

我在对循环缓冲区进行基准测试时偶然发现了这个问题。有人能解释一下在这种情况下，为什么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

- amarcus

1

可能只是分配方式与缓存中其他数据的对齐方式有关。顺便说一下，你需要使用resize而不是reserve。 - Mark Ransom

我能想到的唯一可能是，对于向量，它在寄存器中保存了缓冲区地址，但对于原始数组则未能这样做。请检查机器代码。尝试使用指向数组的指针而不是直接使用数组。 - Cheers and hth. - Alf

@Cheersandhth.-Alf 我认为这是完全正确的。对于数组，它知道可以在堆栈上计算偏移量，但这并不像拥有指向实际开头的指针那样容易。内部循环多了两个指令。 - rici

1

有一个半正确的答案刚刚被删除了，但是它有一个很好的观察。数组元素在你的container结构体中，而向量元素则在其他地方，并通过指针访问。这对优化也有一些影响。你可以通过将数组改为uint_pair*并在构造函数中分配来缩小差距。在我的测试中，这样做可以使性能提升一倍，但仍然比向量慢一点。 - Adam

1

尝试使用另一个编译器进行测试，反汇编显示问题所在。问题是数组存储在与循环变量相同的内存类中，编译器在别名假设方面比较保守，并将循环变量视为易失性。但使用向量不会出现这个问题，因为它存储在堆上而不是栈上。改用 uint_pair* data 而不是 uint_pair data[16] 可消除差异。 - Hans Passant

显示剩余6条评论

3个回答

2

一个问题出在你的结构体中“pos”成员的位置。

对于C数组来说，记住它是与你的“pos”成员相邻地连续存储在内存中的。当数据被推入C数组时，必须发出额外的指令来偏移进入结构体过去“pos”成员。然而，写入向量不受此类限制，因为其内存位于其他位置。

为了提高性能，请确保最热门的数据位于缓存行的前面。

编辑：

要使C数组执行速度与向量一样快，在64位机器上必须将C数组分配在8字节边界上。所以像这样：

uint_pair* data;
unsigned int pos;

container() : pos(0) {
    std::size_t bufSize = sizeof(uint_pair) * 17;
    void* p = new char[bufSize];
    p = std::align(8, sizeof(uint_pair), p, bufSize);
    data = reinterpret_cast<uint_pair*>(p);
}

使用稍微修改过的添加函数：

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

现在 c 数组的时间是:

real    0m0.735s
user    0m0.730s
sys     0m0.002s

还有std::vector：

real    0m0.743s
user    0m0.736s
sys     0m0.004s

标准库实现者正在为您尽全力 :)

- d3coy

你的主张是问题出在内存对齐上，但你没有证明。你使用了一个和我一样的“add”函数，而我证明仅凭这个变化就可以消除性能差异。因此，内存对齐的改变根本没有任何影响（换句话说，编译器已经处理好了）。 - Adam

你说得对，内置结构的数组和通过指针访问的数组之间确实存在差异。但这并不能完全解释性能差异（请参见我在原始问题上的评论）。我也想看到一些证据来支持你的缓存声明。数据总量不到20个整数。所有方法都应该在缓存中。 - Adam

我们必须得到不同的结果。使用您的“set”或我的修改后的“add”，堆分配的c数组和std :: vector之间的性能差异不相等 - c数组仍然会有约0.04秒的减速。这种差异可以完全通过正确对齐的堆分配来消除，这是编译器不会为您执行的操作。因此，修改后的“add”和正确对齐的堆分配均是必需的。 - d3coy

0

因为使用operator=(右值引用)，C++11编译器似乎会为vector生成更优秀的代码。首先，在C++03编译器中，普通数组比vector快两倍。其次，如果您使用Adam建议的void set(unsigned int x, unsigned int y)，则没有什么区别。

向量的汇编代码

.L49:
leal    (%rdi,%rax), %esi
andl    $15, %esi
leaq    (%rdx,%rsi,8), %rsi
movl    %eax, (%rsi)
movl    %eax, 4(%rsi)
incq    %rax
cmpq    $1000000000, %rax
jne .L49

对于普通数组

.L3:
movl    12(%rsp), %edx
incl    %edx
movl    %edx, 12(%rsp)
andl    $15, %edx
leaq    12(%rsp,%rdx,8), %rdx
movl    %eax, 4(%rdx)
movl    %eax, 8(%rdx)
incl    %eax
cmpl    $1000000000, %eax
jne .L3

- ilnar

我并不认为会发生移动操作。首先，uint_pair 声明了一个构造函数，因此它没有默认的移动构造函数。其次：add 函数中 operator= 的参数是一个左值。第三：即使定义了移动构造函数，这两个无符号成员仍然需要被复制。 - DarioP

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam · Accepted Answer

以下是消除差异的方法。使用如下函数代替您的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风格数组行为相同。