Vector Elementzugriff - Index vs. Iterator

Luzzifus

Wie bitte?

Luzzifus schrieb:

Der Indexoperator erzeugt nach meinem Verständnis bei jedem Zugriff einen neuen begin() Iterator,

Nein.

Fellhuhn

Ein Profiler sagt dir unter anderem wie oft er welche Funktion/welchen Operator genutzt und wie viel Zeit damit verbraucht wurde.

Luzzifus

Das weiß ich doch längst, ich weiß bloß nicht warum b langsamer ist als a.

CptC schrieb:

Luzzifus schrieb:

Der Indexoperator erzeugt nach meinem Verständnis bei jedem Zugriff einen neuen begin() Iterator,

Nein.

Aha. Trotzdem müsste er in etwa das gleiche tun was ich manuell versuche, oder?

Tachyon

Übersetz mal im Release-Mode.

Luzzifus

Tachyon schrieb:

Übersetz mal im Release-Mode.

Iteratoren immer noch langsamer als Index, allerdings ist der Unterschied geringer.

Tachyon

Luzzifus schrieb:

Tachyon schrieb:

Übersetz mal im Release-Mode.

Iteratoren immer noch langsamer als Index, allerdings ist der Unterschied geringer.

Wenn Du den Microsoftschen Compiler benutzt, sind vielleicht noch checked Iterators an. Guck Dir in dem Fall mal diesen Artikel an.

Luzzifus

Tachyon schrieb:

Wenn Du den Microsoftschen Compiler benutzt, sind vielleicht noch checked Iterators an. Guck Dir in dem Fall mal diesen Artikel an.

Danke für den Artikel, sehr interessant! Ja, ich benutzt Visual Studio 2005.

Ich habs mal explizit deaktiviert. Im Debug Mode hats keinen Unterschied gebracht, im Release Mode sind jetzt alle drei Varianten zumindest gleich schnell.

Tachyon

Luzzifus schrieb:

Tachyon schrieb:

Wenn Du den Microsoftschen Compiler benutzt, sind vielleicht noch checked Iterators an. Guck Dir in dem Fall mal diesen Artikel an.

Danke für den Artikel, sehr interessant! Ja, ich benutzt Visual Studio 2005.

Ich habs mal explizit deaktiviert. Im Debug Mode hats keinen Unterschied gebracht, im Release Mode sind jetzt alle drei Varianten zumindest gleich schnell.

Schneller als äquivalente Indexzugriffe kanns auch nicht sein. Unter der Haube läuft schließlich das Selbe ab.

Luzzifus

Ich hatte halt in einer seriös wirkenden Quelle gelesen dass der Index-Operator bei jedem Zugriff einen neuen begin() Iterator erzeugt, daher hatte ich durchaus Hoffnungen.

pumuckl

Luzzifus schrieb:

Ich hatte halt in einer seriös wirkenden Quelle gelesen dass der Index-Operator bei jedem Zugriff einen neuen begin() Iterator erzeugt, daher hatte ich durchaus Hoffnungen.

Dann hat die Quelle aber nur seriös gewirkt. Warum sollte da jedesmal ein iterator erzeugt werden?
std::vector ist ja nicht viel mehr als ein gekapseltes dynamisches Array. der Indexzugriff dürfte daher ein entsprechender Indexzugriff auf das zugrundeliegende Array sein. Da std::vector ein Template ist wird der Compiler alle Möglichkeiten haben diesen Indexzugriff zu inlinen.
Ein std::vector<>::iterator dürfte kaum mehr sein als ein gekapselter Pointer auf das Array. Wenn du die ganzen Sicherheitsabfragen ausbaust, die beim MSVC drin sind, dürfte im Releasemodus nach dem (relativ einfachen) Wegoptimieren der ganzen Indirektionen über die Iteratormethoden auch nurnoch ein entsprechend indizierter Zugriff über den internen Pointer des Iterators übrigbleiben.

ipsec

Luzzifus schrieb:

Ich hatte halt in einer seriös wirkenden Quelle gelesen dass der Index-Operator bei jedem Zugriff einen neuen begin() Iterator erzeugt, daher hatte ich durchaus Hoffnungen.

Das ist eigentlich nicht falsch. operator[] macht ja eigentlich nix anderes, als (vorrausgesetzt, die Iteratoren seien einfache Pointer):

reference operator[] ( size_type n )
{
    return *(begin() + n); // begin() wird hier eventuell direkt durch den internen Anfangspointer ersetzt
}

Iteriert werde dabei z.B. folgendermaßen:

vector<int> v;

// []-Variante
for(size_t i = 0; i < v.size(); ++i) cout << v[i] << endl;

// Iteratorvariante
for(vector<int>::iterator i = v.begin(); i != v.end(); ++i) cout << *i << endl;

Bei der []-Variante muss also bei jedem Iterationschritt eine Addition mit 0 bis v.size()-1 durchgeführt werden, bei der Iteratorvariante jeweils eine Addition mit 1 (da ++i). Ich kenne mich jetzt mit den CPU-Implementierung für die Addition nicht so aus, aber wenn es da einen Unterschied gibt, wird der denk ich minimal sein (wobei dann wahrscheinlich die Iteratorvariane sogar schneller wäre).

volkard

XMaster schrieb:

Luzzifus schrieb:

Ich hatte halt in einer seriös wirkenden Quelle gelesen dass der Index-Operator bei jedem Zugriff einen neuen begin() Iterator erzeugt, daher hatte ich durchaus Hoffnungen.

Das ist eigentlich nicht falsch. operator[] macht ja eigentlich nix anderes, als (vorrausgesetzt, die Iteratoren seien einfache Pointer):
reference operator[] ( size_type n )
{
    return *(begin() + n); // begin() wird hier eventuell direkt durch den internen Anfangspointer ersetzt
}
Iteriert werde dabei z.B. folgendermaßen:
vector<int> v;

// []-Variante
for(size_t i = 0; i < v.size(); ++i) cout << v[i] << endl;

// Iteratorvariante
for(vector<int>::iterator i = v.begin(); i != v.end(); ++i) cout << *i << endl;
Bei der []-Variante muss also bei jedem Iterationschritt eine Addition mit 0 bis v.size()-1 durchgeführt werden, bei der Iteratorvariante jeweils eine Addition mit 1 (da ++i). Ich kenne mich jetzt mit den CPU-Implementierung für die Addition nicht so aus, aber wenn es da einen Unterschied gibt, wird der denk ich minimal sein (wobei dann wahrscheinlich die Iteratorvariane sogar schneller wäre).

Im Prinzip richtig. Aber das AMD Assembler-Optimierungshandbuch sagt, es ist im Prinzip Wurstegal, weil genau gleichschnell, außer natürlich, wenn man einen Schritt weiterdenkt, und bemerkt, daß die []-Variante gerne mal ein Register weniger braucht, und weniger register pressure ist was tollen, dadurch können globalere Sachen in Register hüpfen.