挿入よりもPush_backが速いですか？

Question

私はstd::dequeを使用しています。 push_backと1つのinsertのループを置き換えると、パフォーマンスが向上すると確信していました。また、例えばhereのように推奨されます。

しかし、私はもはやこれ以上は分かりません。

テストコードでベンチマークを実行しました。

MAIN.CPP：

#include"queueInsert.h" 

#include<Windows.h> 

std::deque<int> queue; 

constexpr size_t len = 64; 

int arr[len]; 

int main() 
{ 
    DWORD startTime = GetTickCount(); 
    for (int i = 0; i < 100000; ++i) 
    { 
     insert(queue, arr, len); 
    } 
    DWORD endTime = GetTickCount(); 

    return endTime - startTime; 
} 

queueInsert.h：

#include<deque> 

void insert(std::deque<int>&, int* arr, int n); 

queueInsert.cpp -pushバージョン

#include "queueInsert.h" 

void insert(std::deque<int>& queue, int* arr, int n) 
{ 
    for (int i = 0; i < n; ++i) 
    { 
     queue.push_back(arr[i]); 
    } 
} 

queueInsert.cpp -insertバージョン

#include "queueInsert.h" 

void insert(std::deque<int>& queue, int* arr, int n) 
{ 
    queue.insert(queue.end(), arr, arr + n); 
} 

push_backでは203ミリ秒ですが、218ではinsertとなります。 219pushのための工場やinsertため266：

、6にlenを変更し、1百万回の反復を増やすには、同じ結果を保持します。のみlen = 640と

はpushは非常に少ないことで、その後も負ける、とん：insertため1437に対するpushため1531を。

私は、コンパイラは私が変更するたびとして、反復の一定の数をインライン化やループを融合としての最適化を行っていません確信しているWindowsの10

下VisualStudioを2015年にリリースしてコンパイルしています実装はqueueInsert.cppのみが再コンパイルされます。

プロファイリングが間違っていますか？または、挿入する要素の量が大きくない可能性がある場合は、実際にはpush_backを保持する必要がありますか？

Answer 1

deque::insertには、一般的な挿入方法、挿入方法、挿入方法があります。そのため、insertに電話するたびに、挿入する必要があるかどうかを確認するテストを行う必要があります。だから、あなたは前と後ろに渡る反復子をテストしなければなりません。

deque::push_backは、1つの操作モードしかありません。

一括挿入操作を使用する利点は、反復子範囲の長さを取得できるため、コンテナが挿入全体を実行するために割り当てるメモリの量を正確に検出できることです。バルクインサートが大きいほど、より良いinsertになります。

よく、vectorの方が良いです。

vectorを参照してください。一度に30,000個の要素を挿入すると、14〜15回の再割り当てが実行されます。つまり、新しいメモリを割り当てて古いデータをそのメモリにコピーすることを意味します。一方、30,000個の要素を一度に挿入すると、の再割り当てが発生します。

dequeは、通常、固定サイズブロ​​ックのアレイとして実装されます。そのため、一度に1つずつ30,000個の要素を挿入すると、ブロックサイズに応じて約3,000の割り当てが行われます。 30,000の要素を一度に挿入すると、〜3,000の割り当てが得られます。だからあなたは本当に多くを節約していません。

バルクインサートはdequeの1つのインサートとあまり変わらないので、マイクロ最適化の問題との戦いはどうなりますか。すべてのinsert呼び出しはその挿入を実行する方法を見るためにイテレータの比較を行う必要があります。したがって、挿入が小さいほど、効率が悪くなります。insertpush_backにはそのオーバーヘッドはありませんが、各要素の関数呼び出しです。だから、そのオーバーヘッドがあります。

したがって、insertは、1つのインサートに追加される要素の数が多い場合にはおそらく勝つでしょう。