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（鏗鏘類似）得到的結果：

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風格陣列相同。

Answer 2

一個問題是在結構中放置「pos」成員。

對於c數組，請記住它連續存儲在與「pos」成員相鄰的內存中。當數據被推入c數組時，必須發佈額外的指令來抵消「pos」成員之後的結構。但是，寫入向量不會造成這種限制，因爲它的內存位於其他地方。

要擠出更多性能，請確保最熱門的數據位於緩存行的前端。

編輯：

要獲得的c-陣列一樣快執行作爲矢量，該C-陣列必須在8個字節邊界的64位機器上進行分配。因此，像：

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

有了一個稍微修改add函數：

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 ::向量：

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

標準庫實現rs正在爲你全力以赴:)

Answer 3

看來C++ 11編譯器由於operator =（右值引用）而生成更好的向量代碼。 首先，在C++ 03編譯器中，普通數組比矢量快兩倍。其次，如果你使用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