Ich habe eine Frage, um mein Verständnis der Effizienz beim Zugriff auf Elemente eines Vektors zu korrigieren, indem ich den Indexzugriff (mit operator []) verwende oder einen Iterator verwende.
Mein Verständnis ist "Iterator" ist effizienter als "Indexzugriff".
(Ich denke auch vector::end() ist effizienter als vector::size() ).
Jetzt habe ich einen Beispielcode geschrieben (unter Windows 7 mit Cygwin, mit g ++ 4.5.3)
Die Index Access Loop-Version (früher als zufälliger Zugriff bezeichnet):
%Vor%Der Iterator-Schleifencode ist dies:
%Vor% Ich bin überrascht, dass die "Indexzugriff" -Version viel schneller ist. Ich habe den Befehl time verwendet, um "zu messen". Die Zahlen waren:
Ergebnisse mit
g++ source.cpp(keine Optimierungen) Indexzugriffechte 800ms
Iteratorzugriff
echte 2200ms
Machen diese Zahlen Sinn? (Ich wiederholte die Läufe mehrere Male) Und ich fragte mich welche Details ich vermisse und warum ich mich irre ...
Ergebnisse mit g ++ -O2 Indexzugriff, reale Zeit: ~ 200ms
Iteratorzugriff, Zeit real: ~ 200ms
Ich habe Tests auf verschiedenen Plattformen (amd64 w / g ++ und power7 w xlC) wiederholt und festgestellt, dass die Beispielprogramme während der gesamten Zeit, in der optimierter Code verwendet wurde, eine ähnliche Ausführungszeit haben.
Bearbeiten Geänderter Code zum Hinzufügen von Werten ( value += *iter ) anstatt nur die Zuweisung zu verwenden. Details zu den Compileroptionen hinzugefügt. Neue Nummern für die Verwendung von -O2 hinzugefügt.
* edit2 hat die Titelkorrektur "Iterator-Effizienz" in "Zugriff auf Effizienz" geändert.
Ohne die Test-Kabelbäume, die Compiler-Optionen und wie Sie sehen gemessen die Zeit, es ist schwer etwas zu sagen. Auch ein guter Compiler kann in der Lage sein, die Schleife in dem einen oder anderen Fall zu beseitigen, da die Schleife hat keine Auswirkung auf den zurückgegebenen Wert. Immer noch, abhängig von der Implementierung, würde es mich nicht überraschen, Iteratoren signifikant zu sehen schneller als die Indizierung (oder umgekehrt).
In Bezug auf Ihr "Verständnis", gibt es nichts inhärent an der Art des Iterators und seine Leistung. Sie können Iteratoren vorwärts schreiben die sind sehr schnell oder sehr langsam, genauso wie Sie wahlfreien Zugriff schreiben können Iteratoren, die sehr schnell oder sehr langsam sind. Global, die Arten von Daten Strukturen, die Random-Access-Iteratoren unterstützen werden wahrscheinlich haben bessere Lokalität als diejenigen, die nicht funktionieren könnten Random-Access-Iteratoren; aber das ist wirklich nicht genug zu machen irgendwelche vernünftigen Verallgemeinerungen.
Wenn ich beide Programme mit -O2 (Linux, GCC 4.6.1) kompiliere, laufen sie gleich schnell.
Dann: Ihr erstes Programm ist nicht mit Iteratoren, es verwendet Indizes . Dies sind unterschiedliche Konzepte.
Ihr zweites Programm verwendet tatsächlich Random-Access-Iteratoren, weil das std::vector<T>::iterator s sind. Die Einschränkungen für std::vector sind so ausgelegt, dass ein Iterator als einfacher Zeiger in das dynamische Array implementiert werden kann, den ein vector einkapselt.
begin sollte genauso schnell sein wie size . Der einzige Unterschied zwischen den beiden in einer typischen Implementierung von std::vector ist, dass end möglicherweise begin() + size() berechnen muss, obwohl size auch als (grob) end() - begin() implementiert werden kann. Der Compiler könnte jedoch beide in der Schleife optimieren.
Bei Optimierungen sollten die beiden Codes (fast) identisch sein. Probieren Sie -O2 .
Ohne Optimierungen und zusätzliche Debug-Informationen werden Ihre Messungen ziemlich irreführend sein.
Im ersten Beispiel dereferenzieren Sie jedes einzelne Element mit value = vec[idx]; , wodurch bei jedem Zugriff auf ein Element ein Offset von element_size * index berechnet wird.
Da ein Vektor aus Elementen besteht, die in einem fortlaufenden Speicherblock angeordnet sind, wird ein Vektoriterator normalerweise einfach als einfacher Zeiger implementiert, so dass das Iterieren durch einen Vektor (wie in Ihrem zweiten Beispiel) nur das Vorrücken des Zeigers um ein Element nach sich zieht jede Iteration.
Wenn Sie Optimierungen aktivieren (versuchen Sie -O2 oder -O3 ), optimiert der Compiler Ihre Schleife im ersten Beispiel wahrscheinlich auf etwas, das dem zweiten Beispiel ähnlich ist, was die Leistung nahezu identisch macht.
Ich habe Iteratoren tatsächlich schneller gefunden. Versuchen Sie, Ihre Iterator-Schleife zu etwas wie der folgenden zu refactoring und Sie können dies auch sehen:
%Vor%Das Ergebnis ist das Folgende auf meinem PC, was zeigt, dass Iteratoren einen leichten Vorsprung haben:
%Vor%Sie sollten beachten, dass ich einen Zusatz von rand () verwendet habe; das hindert den Compiler daran, etwas zu optimieren, das es zur Kompilierzeit berechnen kann. Compiler scheinen es mit intrinsischen Arrays viel leichter zu haben als mit Vektoren, und dies kann Array Arrays einen irreführenden Vorteil gegenüber Vektoren verleihen.
Ich habe das oben mit "icpc -fast" zusammengestellt. Slavik hatte recht damit, Berechnungen mit Indizes zu machen anstatt mit Iteratoren (ala pointer) zu inkrementieren.