Push_back schneller als einfügen?

Question

Ich verwende std::deque. Ich war sicher, dass das Ersetzen einer Schleife mit einer push_back durch eine einzelne insert eine Leistungssteigerung ergeben würde. Es wird auch empfohlen, zum Beispiel here.

Aber jetzt bin ich mir nicht mehr so ​​sicher.

Ich habe einige Benchmarks auf Testcode ausgeführt.

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 Version

#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 Version

#include "queueInsert.h" 

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

Ich bekomme 203 Millisekunden mit push_back, aber 218 mit insert.

Ändern len-6, und die Erhöhung der Iterationen auf eine Million, hält das gleiche Ergebnis: 219 Mühlen für push und 266 für insert.

Nur mit len = 640 tut push zu verlieren, und selbst dann nur sehr wenig: 1531 für push gegen 1437 für insert.

Ich bin in Release in Visual Studio 2015 unter Windows kompilieren 10.

Ich bin sicher, dass der Compiler nicht Optimierungen tut, um die konstante Anzahl von Iterationen als inlining oder die Schlaufen Absicherungen, wie jedes Mal, wenn ich das ändern Implementierung wird nur queueInsert.cpp neu kompiliert.

Mache ich Profiling falsch? Oder sollte ich eigentlich push_back behalten, wenn die Menge der einzufügenden Elemente wahrscheinlich nicht groß ist?

Answer 1

deque::insert hat effektiv 3 mögliche Betriebsweisen: allgemeiner Einsatz, Einsatz vorne, Einsatz hinten. Aus diesem Grund muss jedes Mal, wenn Sie insert aufrufen, ein Test durchgeführt werden, um zu sehen, welche Art und Weise es eingefügt werden muss. Also muss es den Iterator testen, den Sie gegen die Front und die Rückseite übergeben.

deque::push_back hat nur 1 Betriebsart: auf der Rückseite einfügen. Der Vorteil der Verwendung eines Masseneinfügevorgangs besteht darin, dass der Container genau ermitteln kann, wie viel Arbeitsspeicher er für die gesamte Einfügung reservieren muss, da er die Länge des Iteratorbereichs ermitteln kann. Je größer der Bulk-Insert, desto besser wird insert sein.

Nun, desto besser für vector mindestens.

Siehe mit vector, wenn Sie 30.000 Elemente nacheinander einfügen, werden Sie wahrscheinlich eine Neuzuweisung ~ 14-15 Mal durchführen. Das bedeutet, dass neuer Speicher zugewiesen und die alten Daten in diesen Speicher kopiert werden. Wenn Sie jedoch 30.000 Elemente auf einmal einfügen, erhalten Sie eine einzelne Neuzuweisung.

deque wird normalerweise als ein Array von Blöcken fester Größe implementiert. Wenn Sie also 30.000 Elemente nacheinander einfügen, erhalten Sie ~ 3.000 Zuordnungen (abhängig von der Blockgröße). Wenn Sie 30.000 Elemente auf einmal einfügen, erhalten Sie ... ~ 3.000 Zuweisungen. Du sparst also nicht wirklich viel.

Da Bulk-Insert unterscheidet sich nicht viel von einzelnen einfügen für deque, was passiert ist ein Kampf zwischen Mikro-Optimierungsprobleme. Jeder Aufruf von insert muss einen Iteratorvergleich durchführen, um zu sehen, wie diese Einfügung durchgeführt wird. Je kleiner die Einfügungen sind, desto weniger effizient wird insert sein. push_back hat diesen Overhead nicht, aber es ist ein Funktionsaufruf für jedes Element. Also hat es diesen Overhead.

Daher wird insert wahrscheinlich gewinnen, wenn die Anzahl der pro Insert hinzugefügten Elemente hoch ist.