Warum push_back ist langsamer als der operator[] bei einer zuvor zugewiesenen Vektor
Gerade lese ich diesen blog http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/ Vergleich der Leistung von operator[]
Zuordnung und push_back
auf Speicher vorreserviert std::vector
und ich beschlossen, es zu versuchen mich. Die Bedienung ist einfach:
//for vector
bigarray.reserve(N);
//START TIME TRACK
for(int k = 0; k < N; ++k)
//for operator[]:
//bigarray[k] = k;
//for push_back
bigarray.push_back(k);
//END TIME TRACK
//do some dummy operations to prevent compiler optimize
long sum = accumulate(begin(bigarray), end(array),0 0);
Und hier ist das Ergebnis:
~/t/benchmark> icc 1.cpp -O3 -std=c++11
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.789123s --> C++ new
[ 1.cpp: 52] 0.774049s --> C++ new
[ 1.cpp: 66] 0.351176s --> vector
[ 1.cpp: 80] 1.801294s --> reserve + push_back
[ 1.cpp: 94] 1.753786s --> reserve + emplace_back
[ 1.cpp: 107] 2.815756s --> no reserve + push_back
~/t/benchmark> clang++ 1.cpp -std=c++11 -O3
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.592318s --> C++ new
[ 1.cpp: 52] 0.566979s --> C++ new
[ 1.cpp: 66] 0.270363s --> vector
[ 1.cpp: 80] 1.763784s --> reserve + push_back
[ 1.cpp: 94] 1.761879s --> reserve + emplace_back
[ 1.cpp: 107] 2.815596s --> no reserve + push_back
~/t/benchmark> g++ 1.cpp -O3 -std=c++11
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.617995s --> C++ new
[ 1.cpp: 52] 0.601746s --> C++ new
[ 1.cpp: 66] 0.270533s --> vector
[ 1.cpp: 80] 1.766538s --> reserve + push_back
[ 1.cpp: 94] 1.998792s --> reserve + emplace_back
[ 1.cpp: 107] 2.815617s --> no reserve + push_back
Für alle Compiler vector
mit operator[]
ist viel schneller als raw-pointer mit operator[]
. Dies führte zu der ersten Frage: warum? Die zweite Frage ist, habe ich bereits "reserviert", die Erinnerung, warum also opeator[]
ist schneller?
Die nächste Frage ist, da der Arbeitsspeicher bereits zugewiesen ist, warum push_back
ist-mal langsamer als operator[]
?
Den test-code ist unten angehängt:
#include <iostream>
#include <iomanip>
#include <vector>
#include <numeric>
#include <chrono>
#include <string>
#include <cstring>
#define PROFILE(BLOCK, ROUTNAME) ProfilerRun([&](){do {BLOCK;} while(0);}, \
ROUTNAME, __FILE__, __LINE__);
template <typename T>
void ProfilerRun (T&& func, const std::string& routine_name = "unknown",
const char* file = "unknown", unsigned line = 0)
{
using std::chrono::duration_cast;
using std::chrono::microseconds;
using std::chrono::steady_clock;
using std::cerr;
using std::endl;
steady_clock::time_point t_begin = steady_clock::now();
//Call the function
func();
steady_clock::time_point t_end = steady_clock::now();
cerr << "[" << std::setw (20)
<< (std::strrchr (file, '/') ?
std::strrchr (file, '/') + 1 : file)
<< ":" << std::setw (5) << line << "] "
<< std::setw (10) << std::setprecision (6) << std::fixed
<< static_cast<float> (duration_cast<microseconds>
(t_end - t_begin).count()) / 1e6
<< "s --> " << routine_name << endl;
cerr.unsetf (std::ios_base::floatfield);
}
using namespace std;
const int N = (1 << 29);
int routine1()
{
int sum;
int* bigarray = new int[N];
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray[k] = k;
}, "C++ new");
sum = std::accumulate (bigarray, bigarray + N, 0);
delete [] bigarray;
return sum;
}
int routine2()
{
int sum;
vector<int> bigarray (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray[k] = k;
}, "vector");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int routine3()
{
int sum;
vector<int> bigarray;
bigarray.reserve (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "reserve + push_back");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int routine4()
{
int sum;
vector<int> bigarray;
bigarray.reserve (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray.emplace_back(k);
}, "reserve + emplace_back");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int routine5()
{
int sum;
vector<int> bigarray;
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "no reserve + push_back");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int main()
{
long s0 = routine1();
long s1 = routine1();
long s2 = routine2();
long s3 = routine3();
long s4 = routine4();
long s5 = routine5();
return int (s1 + s2);
}
- Dein code ist verbuggt, über operator[] auf " zero sized vector (auch wenn der Speicher reserviert wurde mit reserve) ist kein gültiges C++. Nur nicht Abstürzen, denn der Vektor ist ein primitiver Typ.
- Er ist nur die Zuordnung der Werte (das ist tatsächlich setzen, um gültige Eingaben), so dass die Regel gilt hier nicht. Das heißt, die
size
wird nicht ordnungsgemäß aktualisiert werden, so dass der rest der Vektor der Funktionen nicht richtig funktionieren, es sei denn, Sie rufenresize
. - Durch die änderung der
reserve
zu einemresize
in routine 4, bekomme ich die gleichen Zeiten wie bei routine 2 (!). (Ja, es wird schneller durch eine um eine Größenordnung.) - Einfügen eines
memset(bigarray, 0, sizeof(int)*N);
inroutine1
macht es so schnell wie routine2. Ich denke, der Grund, warumroutine2
ursprünglich wurde schneller alsroutine1
ziemlich überraschend; ich wage eine Vermutung: einige spezielle Operationen werden ausgeführt, um führen Sie die Schleife, und Sie können nicht oder sind nicht in derpush_back
Fällen, die einen Beitrag zu Ihrer Langsamkeit. - Ich denke, du hast ein copy+Abfall Fehler in
routine4
(Revisionen), aber es wirkt sich auf Ihre timings. - Nein, den Zugriff auf Elemente zwischen
size
undcapacity
kann man alles machen. Der compiler behandeln könnte diese Operationen als noops, wenn es erkennt, als ein Beispiel. Als eine einfache Optimierung, es könnte statisch bestimmen, dass dievector
hatsize()=0
, und als solche alle[]
Aufrufe sind nicht definiertes Verhalten, und nur Sie überspringen wenn Optimierungen aktiviert sind. gcc getan hat, etwas ähnliches mit integer-überlauf-Operationen (Umwandlungint
zuunsigned int
an, dass das Ergebnis nicht<0
, und beseitigen Sie solche Kontrollen danach). resize
berühren wird der gesamte block des Speichers.reserve
zugewiesen werden, ohne Sie zu berühren. Wenn Sie haben ein faul-Zuweisung nicht abrufen oder zuweisen von physischen Speicher-Seiten, bis auf Sie zugegriffen wird,reserve
auf eine leere vector-kann fast kostenlos (sogar nicht zu finden, physischen Speicher für die Seiten!) erst schreibst du an den Seiten (an welcher Stelle Sie gefunden werden). Auf top von, dass, nachdem Lesen der Seiten außerhalb des timing, Sie sind eher im cache: eine sofortige Lesen, danach vielleicht keine cache-misses (wennN
ist klein genug).- Tut
now()
einzuführen eine Anleitung Neuordnung Zaun? Dh, können die Anweisungen innerhalb des Profils verschoben werden, außerhalb davon, oder Umgekehrt, durch den compiler? - Ich hatte gerade eine ähnliche Idee, getestet und die Hypothese. Austausch der
memset
mit einem "strided memset" (for(int k=0; k<N; k+=stride) bigarray[k]=0;
). Beim Zugriff auf alle Speicher-Seiten, eine riesige speed-up-Auftritt, in der Erwägung, dass beim Zugriff auf nur jeder zweiten Seite, es ist etwa 2 mal langsamer. Das gleiche natürlich geschieht für allepush_back
s. W/o-memset, routine 1 und 3 sind etwa im gleichen Tempo, so dass ich denke, es könnte ein wichtiger Faktor sein, und nicht die Niederlassung inpush_back
, die Dinge verlangsamt. - Ich wollte nicht nennen es nach der Tat - ich meinte, Sie nennen es statt
reserve
. - Sorry, dass ich dich missverstanden. Ich hätte es wissen müssen Sie sind nicht so dumm.
- Ja, ich habe einen Tippfehler. Korrigiert jetzt.
Du musst angemeldet sein, um einen Kommentar abzugeben.
push_back
macht einen bounds-check.operator[]
nicht. Also selbst wenn Sie reserviert haben den Raum,push_back
wird ein extra-bedingte überprüfen Sie, dassoperator[]
nicht haben. Darüber hinaus wird es erhöhen Sie diesize
Wert (reserve stellt nur diecapacity
), so wird es von update zu jeder Zeit.Kurz
push_back
tut mehr als das, wasoperator[]
tut - das ist, warum es langsamer ist (und genauer).Wenn Sie zuweisen, das array im Konstruktor, den der compiler/library kann im Grunde
memset()
den ursprünglichen füllen-und dann setzen Sie einfach jeden einzelnen Wert. Wenn Siepush_back()
, diestd::vector<T>
Klasse müssen:Der Letzte Schritt ist die einzige Sache, die getan werden muss, wenn der Speicher zugeordnet ist, in einem Rutsch.
push_back()
verwendet wird, werden die Schritte 1. und 2. müssen getan werden, neben der Festlegung der tatsächlichen Werte; bei Verwendungoperator[]()
nur die Einstellung der Letzte Wert ist getan. Ich denke, das erklärt den Zeitunterschied. Welchen Teil dieser Antwort ist falsch? Vorausgesetzt, Ihr Kommentar ist zu erklären, die downvote, können Sie mir bitte erklären, wie dass falsch ist, garantieren einen downvote? Mein letzter Satz zum initialisieren ein array mit Werten, zu schnell ist nicht falsch, aber entweder tut, in der Tat, nicht brauchen, dort zu sein, und ich werde es entfernen.Kann ich die Antwort auf Ihre zweite Frage. Obwohl der Vektor ist vorbelegt, push_back noch braucht, um den verfügbaren Speicherplatz überprüfen jedes mal, wenn Sie rufen push_back. Auf der anderen Seite operator[] führt keine Kontrollen durch und nimmt einfach den Platz zur Verfügung steht.
operator[]
push_back
werden nicht eingebettet, sondernoperator[]
.push_back
tut viel mehr alsoperator[]
tut.Dies ist ein erweiterter Kommentar, keine Antwort, soll dazu beitragen, die Frage.
Routine 4 ruft Undefiniertes Verhalten. Sie schreiben über das Ende der
size
des Arrays. Ersetzen reservieren Sie mit Größenanpassung zu beseitigen, dass.Routine 3 bis 5 nichts tun konnte-post-Optimierung, denn Sie haben keine sichtbaren Ausgang.
Einer
insert( vec.end(), src.begin(), src.end() )
wosrc
ist ein random access generator range (boost
wahrscheinlich hat es) könnte emulierennew
version, wenn Ihrinsert
ist smart.Die Vervielfältigung von
routine1
scheint lustig ist-durch Zufall hat das ändern der timings?N
im Konstruktor.