vector: Iterator vs Index Operator

Abend,

eine kurze Frage: Was ist effizienter, wenn ich über einen Vektor komplett iterieren muss (und jedes Element lese): Per Iterator oder per operator[]?

Danke!

volkard

gleich schnell.
nimm im zweifel iterator, damit du den vector später gegen eine deque austauschen kannst oder so, ohne daß sich was ändert.

Nexus

Gleich. Ich habe aber erst kürzlich unter MSVC++ eine oberflächliche Messung durchgeführt, bei der der Iterator 3 mal langsamer als der Zugriff über Index war. Die Geschwindigkeiten waren allerdings identisch, nachdem ich folgendes Makro definiert hatte:

#define _SECURE_SCL 0

Daran sollte man bei der STL-Implementierung des MSVC++ denken, wenn man im Release-Modus performanten Code braucht (dafür werden die Sicherheitschecks abgeschaltet).

Edit: Von daher würde ich wie volkard erwähnte ruhig zu Iteratoren greifen. Allerdings ist die Deque nicht unbedingt das beste Beispiel.

unskilled

das beste Bsp. wäre hier vrmtl eine Liste - da die keinen op[] anbietet : P
so bald der container einen op[] anbietet, wird der compiler das vermutlich eh wegoptimieren können...

bb

volkard

unskilled schrieb:

das beste Bsp. wäre hier vrmtl eine Liste - da die keinen op[] anbietet : P
so bald der container einen op[] anbietet, wird der compiler das vermutlich eh wegoptimieren können...

bb

map

DeepCopy

Ein Sinn und Zweck von Iteratoren ist u.a. die Bereichsprüfung bei 100% gleicher Performance wie bei rohen Arrays, da der std::vector intern ebenfalls auf einem solchen Array basiert sollte der index operator keine Performanceverluste gegenüber dem Iterator aufweisen, ist aber immer Implementierungsabhängig, z.B. durch eingebaute Bereichsprüfung im index operator kann die Performance bei Iteratoren etwas besser sein.

Nexus

DeepCopy schrieb:

z.B. durch eingebaute Bereichsprüfung im index operator kann die Performance bei Iteratoren etwas besser sein.

Wahrscheinlicher ist aber, dass durch zusätzliche Iteratorprüfungen der Indexoperator schneller ist, beim Index reicht schliesslich ein assert(index < size) , was bei Iteratoren schon komplizierter ist (Iterator innerhalb gültiger Range, zeigt in richtigen Container, ist inzwischen nicht durch eine Container-Operation invalidiert worden). Im Falle des MSVC++ und eingeschalteten Checked-Iterators sieht man diesen Unterschied eben schön - zugunsten des operator[] .

DeepCopy

@Nexus

Dafür entfällt beim Iterator die aufwendige Brechnung der richtigen Adresse gerechnet vom Array-Anfang, er nimmt bei Vor- und Rückwärtsbewegungen einfach den gespeicherten Prev- Next-Zeiger des aktuellen Objekts (weist du ja selbst ), ob das allerdings ausreicht die von Dir genannten möglichen Iterator-Prüfungen zu eliminieren weiß ich jetzt aus dem Stehgreif auch nicht.

EDIT: Typo!

Nexus

DeepCopy schrieb:

Dafür entfällt beim Iterator die aufwendige Brechnung der richtigen Adresse gerechnet vom Array-Anfang

Aufwändige Berechnung? Bei std::vector eine Addition, bei std::deque vielleicht etwas mehr.

DeepCopy schrieb:

er nimmt bei Vor- und Rückwärtsbewegungen einfach den gespeicherten Prev- Next-Zeiger des aktuellen Objekts (weist du ja selbst )

Das ist vielleicht bei einer doppelt verketteten Liste so. Ein Neu-Setzen von mehreren Zeigern schätze ich aber nicht als schneller ein als eine einfache Zeiger-Inkrementierung.

DeepCopy schrieb:

ob das allerdings ausreicht die von Dir genannten möglichen Iterator-Prüfungen zu eliminieren weiß ich jetzt aus dem Stehgreif auch nicht.

Ich denke nicht. Wie gesagt sind Index- und Iteratorzugriff im Allgemeinen etwa gleich schnell. Das heisst, man sollte nicht aus Geschwindigkeitsgründen eine Möglichkeit bevorzugen. Es sei denn, man macht wirkliche Messungen und braucht eventuelle Geschwindigkeitsgewinne um jeden Preis (von denen ich aber ausgehe, dass sie sehr klein bis nicht vorhanden sind). Im Normalfall ist das entscheidende Kriterium aber Wiederverwendbarkeit, und da haben Iteratoren in einer einfachen Schleife mit Foreach-Semantik die Nase eindeutig vorn.

DeepCopy

Jeder nimmt das woran er halt glaubt!

hustbaer

DeepCopy schrieb:

Ein Sinn und Zweck von Iteratoren

ist Abstraktion

ist u.a. die Bereichsprüfung bei 100% gleicher Performance wie bei rohen Arrays,

unmöglich

da der std::vector intern ebenfalls auf einem solchen Array basiert sollte der index operator keine Performanceverluste gegenüber dem Iterator aufweisen, ist aber immer Implementierungsabhängig,

ist implementierungs-abhängig, genau.

z.B. durch eingebaute Bereichsprüfung im index operator kann die Performance bei Iteratoren etwas besser sein.

ja, checks kosten zeit. aber nicht nur im index-operator, sondern auch in den iteratoren.

hustbaer

die schnellste variante über alle elemente eines std::vector zu iterieren ist so-gut-wie immer:

if (!vec.empty())
{
    T* const ptr = &vec[0];
    size_t const size = vec.size();

    for (size_t idx = 0; idx < size; ++idx)
        mach_was_mit(ptr[idx]);
}

der zugriff über iteratoren oder den index-operator der klasse kann gleich schnell sein, kann aber auch langsamer sein. u.u. deutlich langsamer.

EDIT: so könnte es u.u. noch um einen viertel tick schneller sein:

if (size_t const size = vec.size())
{
    T* const ptr = &vec[0];

    for (size_t idx = 0; idx < size; ++idx)
        mach_was_mit(ptr[idx]);
}

DeepCopy

Na dann wissen wir es ja jetzt ganz genau

Erstmal danke für die Antworten. Leuchtet mir ein, dass der Code von hustbaer vermutlich mit der schnellste ist, aber er ist mir etwas zu... frickelig.

Noch eine konkrete Frage zu meinem Code:

for(int i = 0; i < verts.size(); i++) {
   int row = verts[i].vertexRow - mIndexStartRow;
   int col = verts[i].vertexCol - mIndexStartCol;
   int index = row * getPatchSize() + col;
   heightData[index] = verts[i].vertexHeight;
}

verts ist vom Typ std::vector<IndexHeightPair> und IndexHeightPair ist ein struct mit 3 Werten.
Meine 2 Fragen:
1. Ist es schlecht, wenn ich in der Schleifenbedingung das verts.size() stehen habe? Wird dann in JEDEM Durchlauf wieder vector::size() aufgerufen?

2. Ich greife im Schleifenrumpf auf alle 3 Member des vectors zu, sprich es wird 3mal dereferenziert. Sollte ich lieber zu Beginn der Schleife das ganze IndexHeightPair auslesen (IndexHeightPair ip = verts[i]) und dann nur noch darauf zugreifen? Oder wird das eh so optimiert, dass nur noch einmal dereferenziert wird?

asc

performancer schrieb:

1. Ist es schlecht, wenn ich in der Schleifenbedingung das verts.size() stehen habe? Wird dann in JEDEM Durchlauf wieder vector::size() aufgerufen?

Ja, es wird in jedem Durchlauf die Methode erneut aufgerufen (Compilermagie lasse ich mal außen vor, glaube hier aber nicht an eine Optimierung).

Falls sich die Anzahl der Elemente nicht ändert kannst du es wie folgt auflösen:

for(int i = 0, size=verts.size(); i < size; ++i)

Nexus

Was asc gesagt hat, gilt auch für Iteratoren, da sollte man sich wenn möglich auch end() merken:

for (Container::iterator itr = c.begin(), end = c.end(); itr != end; ++itr)

performancer schrieb:

2. Ich greife im Schleifenrumpf auf alle 3 Member des vectors zu, sprich es wird 3mal dereferenziert. Sollte ich lieber zu Beginn der Schleife das ganze IndexHeightPair auslesen (IndexHeightPair ip = verts[i]) und dann nur noch darauf zugreifen? Oder wird das eh so optimiert, dass nur noch einmal dereferenziert wird?

Ich nehme nicht an, dass die Dereferenzierungen stark ins Gewicht fallen, aber du kannst zum Beispiel auch eine Referenz deklarieren (musst du zwar immer noch dereferenzieren, aber nur einmal und ohne Offset), aber das ist letzten Endes etwas Geschmackssache. Mach dir um solche Dinge am besten keine grosse Gedanken. Wenn du es genau wissen willst, gibts wieder nur eins: messen.

hustbaer

performancer schrieb:

Erstmal danke für die Antworten. Leuchtet mir ein, dass der Code von hustbaer vermutlich mit der schnellste ist, aber er ist mir etwas zu... frickelig.

Was ist da dran frickelig?
Solange T von std::vector<T> nicht bool ist, ist vom Standard garantiert dass der Code funktioniert.

Entweder du willst optimieren, oder nicht. Wenn nicht, dann schreib den Code so wie er schön/lesbar/sauber ist. Wenn schon, dann nimm die von mir vorgeschlagene Variante.

knivil

Hat mal jemand gegen std::for_each getestet? Persoenlich mag ich ja bei rohen Arrays:

ar = &vec[0] // oder vergleichbares
std::for_each( ar, ar + 32, function/functor );

Ziehe aber stl-Containern die Iteratorvariante vor.

drakon

performancer schrieb:

Noch eine konkrete Frage zu meinem Code:

for(int i = 0; i < verts.size(); i++) {
   int row = verts[i].vertexRow - mIndexStartRow;
   int col = verts[i].vertexCol - mIndexStartCol;
   int index = row * getPatchSize() + col;
   heightData[index] = verts[i].vertexHeight;
}

Ich denke mal ich weiss, was du hier machst und glaub mir, dass du andere Probleme hast, als das befüllen eines Vertexbuffers (auch/vor allem in Echtzeit). In Debug mag das ja einiges an Ressourcen fressen, aber sobald du (wie schon oft gesagt) auf Release umstellst, wird das meiste so performant, als würdest du direkt mit Arrays arbeiten. Das setzen eines anderen Vertexbuffers ist ein grösserer Performance Fresser, als das befüllen eines solchen.
(Ich will dir nur sagen, dass du hier nicht in Versuchung kommen sollst eine unsicherer Variante zu nehmen, weil du glaubst, dass du damit auf die Dauer besser fährst.. )

drakon schrieb:

In Debug mag das ja einiges an Ressourcen fressen, aber sobald du (wie schon oft gesagt) auf Release umstellst, wird das meiste so performant...

Könnte man mal in ne Performance FAQ schreiben.