vector: Iterator vs Index Operator

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.

unskilled

____ schrieb:

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.

Mal ehrlich - wenn die jetzige FAQ nicht so zugemüllt wäre, würde sich die vll auch mal jmd durchlesen...
Aber der Großteil der User wird auch dann, ohne sich die FAQ durchzulesen, posten...

bb

drakon

unskilled schrieb:

Mal ehrlich - wenn die jetzige FAQ nicht so zugemüllt wäre, würde sich die vll auch mal jmd durchlesen...
Aber der Großteil der User wird auch dann, ohne sich die FAQ durchzulesen, posten...

bb

Bin auch der Meinung, dass das Teil man ein wenig aufgeräumt werden würde.. (so in die Richtung, wie es in "Die meistgestellten Fragen" gemacht ist. Weil gewisse Titel nicht wirklich mit dem FAQ-Material zusammen passt..

Blue-Tiger

asc schrieb:

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).

Warum nicht? Den Aufruf von size() inlinen ist kein Problem (wuerd mich sehr wundern wenn das nicht gemacht wird), und ein std::vector koennte die Anzahl Elemente durchaus als Member speichern. In dem Fall hat man (schlimmstenfalls) 1 Load pro Schleifendurchlauf (da der Compiler idR nicht weiss dass die Groesse des vectors sich nicht aendert, kann er den wohl nicht wegoptimieren).
In der GCC-Implementierung besteht size() aus einer einzelnen Subtraktion. Also 2 Loads und 1 Subtraktion pro Schleifendurchlauf. Faellt wohl auch nie ins Gewicht. IMO ist das overengineering und blaeht den Code nur unnoetig auf, wenn man das size() aus der Schleife rauszieht.

hustbaer schrieb:

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.

Irgendwann hat irgendwer mal behauptet

T* const ptr = &vec

waere vom Standard auch garantiert. Stimmt das?