重載矢量運算符導致大幅度的性能下降？

Question

我總結和乘以一個常數向量很多次，所以我重載了運算符*和+。然而，使用矢量大大減慢了我的程序。使用標準的C陣列將時間縮短40倍。什麼會導致這樣的緩慢？

下面是一個示例程序，顯示我的重載操作員和展示放慢速度。這個程序的k = k +（0.0001）* q，log（N）次（這裏N = 1000000）。最後，程序輸出使用向量和c數組執行操作的時間，以及時間的比例。

#include <stdlib.h> 
#include <stdio.h> 
#include <iostream> 
#include <time.h> 
#include <vector> 

using namespace std; 
// -------- OVERLOADING VECTOR OPERATORS --------------------------- 
vector<double> operator*(const double a,const vector<double> & vec) 
{ 
    vector<double> result; 
    for(int i = 0; i < vec.size(); i++) 
    result.push_back(a*vec[i]); 
    return result; 
} 

vector<double> operator+(const vector<double> & lhs, 
     const vector<double> & rhs) 
{ 
    vector<double> result; 
    for(int i = 0; i < lhs.size();i++) 
    result.push_back(lhs[i]+rhs[i]); 
    return result; 
} 
//------------------------------------------------------------------ 
//--------------- Basic C-Array operations ------------------------- 
// s[k] = y[k]; 
void populate_array(int DIM, double *y, double *s){ 
    for(int k=0;k<DIM;k++) 
    s[k] = y[k]; 
} 
//sums the arrays y and s as y+c s and sends them to s; 
void sum_array(int DIM, double *y, double *s, double c){ 
    for(int k=0;k<DIM;k++) 
    s[k] = y[k] + c*s[k]; 
} 
// sums the array y and s as a*y+c*s and sends them to s; 
void sum_array2(int DIM, double *y, double *s,double a,double c){ 
    for(int k=0;k<DIM;k++) 
    s[k] = a*y[k] + c*s[k]; 
} 
//------------------------------------------------------------------ 
int main(){ 
    vector<double> k = {1e-8,2e-8,3e-8,4e-8}; 
    vector<double> q = {1e-8,2e-8,3e-8,4e-8}; 
    double ka[4] = {1e-8,2e-8,3e-8,4e-8}; 
    double qa[4] = {1e-8,2e-8,3e-8,4e-8}; 
    int N = 3; 
    clock_t begin,end; 
    double elapsed_sec,elapsed_sec2; 
    begin = clock(); 
    do 
    { 
     k = k + 0.0001*q; 
     N = 2*N; 
    }while(N<1000000); 
    end = clock(); 
    elapsed_sec = double(end-begin)/CLOCKS_PER_SEC; 
    printf("vector time: %g \n",elapsed_sec); 

    N = 3; 
    begin = clock(); 
    do 
    { 
     sum_array2(4, qa, ka,0.0001,1.0); 
     N = 2*N; 
    }while(N<1000000); 
    end = clock(); 
    elapsed_sec2 = double(end-begin)/CLOCKS_PER_SEC; 
    printf("array time: %g \n",elapsed_sec2); 
    printf("time ratio : %g \n", elapsed_sec/elapsed_sec2); 
} 

我得到的矢量時間與c-陣列時間的比值通常在我的linux系統上是40。與C數組操作相比，我的重載操作符是什麼導致了減速？

Answer 1

讓我們來看看這條線：

k = k + 0.0001*q; 

爲了評估這一點，首先計算機需要打電話給你operator*。此函數創建一個vector並需要爲其元素分配動態存儲。實際上，由於您使用的是push_back而不是通過構造函數resize或reserve提前設置大小，因此它可能會在第一次分配太少元素，並且需要再次分配以增加矢量。

這個創建的vector（或一個移動 - 從它構造）然後被用作代表整個語句中的子表達式0.0001*q的臨時對象。

接下來電腦需要撥打你的operator+，通過k那個臨時的vector。此功能還會創建並返回一個vector，執行至少一個動態分配並可能更多。子表達k + 0.0001*q還有第二個臨時vector。

最後，計算機調用屬於std::vector的operator=。幸運的是，有一個移動分配過載，它可能（只是）將分配的內存從第二個臨時移動到k，並釋放k中的內存。

現在已經評估了整個語句，臨時對象被銷燬。首先臨時的k + 0.0001*q被銷燬，但它不再有任何內存可以清理。然後臨時的0.0001*q被銷燬，並且它確實需要釋放其內存。

做很多分配和釋放內存，即使是少量的，往往是有點貴。 （這些向量將使用std::allocator，這允許更聰明並避免一些分配和釋放，但是我不能沒有調查地說實際上在這裏可能會有多大幫助。）

另一方面，您的「 C風格「的實現根本不分配或釋放。它執行「就地」計算，只是修改傳入的數組以存儲傳出的值。如果您有另一個C風格的實現，其中包含double* scalar_times_vec(double s, const double* v, unsigned int len);等單個函數，它們使用malloc獲取結果的內存並要求結果最終爲freed，那麼您可能會得到類似的結果。

那麼如何改進C++實現呢？

如前所述，您可以在添加數據給它們之前向量爲reserve，或者給它們一個初始大小，並執行v[i] = out;而不是push_back(out);。

下一個最簡單的步驟是使用更多允許就地計算的運算符。如果你重載：

std::vector<double>& operator+=(const std::vector<double>&); 
std::vector<double>& operator*=(double); 

那麼你可以做：

k += 0.0001*q; 
n *= 2; 
// or: 
n += n; 

上做k和n就地最終計算。不過，這並不容易幫助表達0.0001*q。

另一個有時可以幫助的選項是重載操作符以接受右值以重用屬於臨時對象的存儲。如果我們有一個過載：

std::vector<double> operator+(const std::vector<double>& a, std::vector<double>&& b); 

它會被調用在表達k + 0.0001*q的+，以及實施可以從std::move(b)創造的返回值，再利用它的存儲。不過，這樣做會變得棘手，以致既靈活又正確。它仍然不會消除代表0.0001*q或其分配和釋放的臨時數據。

另一種允許在最常見情況下就地計算的解決方案稱爲表達式模板。這是相當多的工作要實現，但如果你真的需要方便的語法和效率的組合，有一些現有的庫可能值得研究。

Answer 2

編輯：

我應該採取你如何進行C-數組操作仔細一看...查看aschepler的爲什麼越來越多的載體是至少你的問題的答案。

---

如果您有任何想法，你有多少個元素要添加到vector，你應該總是將他們面前呼籲矢量reserve。否則，你將觸發潛在的大量重新分配，這是昂貴的。

A vector佔用連續的內存塊。爲了增長，它必須分配更大的內存塊並將其全部內容複製到新的位置。爲了避免每次添加元素時發生這種情況，向量通常會分配比存儲其所有元素所需的內存更多的內存。無需重新分配就可以存儲的元素數量是其容量。這個容量應該多大，當然是在避免潛在的未來重新分配和浪費內存之間進行權衡。 但是，如果您知道（或有個好主意）最終將在vector中存儲多少個元素，則可以致電reserve(n)將其容量設置爲（至少）n，並避免不必要的重新分配。

編輯：

也here見。 push_back執行綁定檢查，因此比寫入vector到operator[]稍慢。在你的情況下，它可能是最快的直接構建大小（不只是容量）的vectorn，因爲doubles是POD和便宜構造，並通過operator[]插入正確的值。