3. Performance beim Iterieren über Vektorelemente

Performance beim Iterieren über Vektorelemente


  • Hallo zusammen,

    ich bin gerade etwas darüber entsetzt, wie lange das Iterieren über Vektorelemente dauert. Übersetzt und getestet mit Codegear RAD Studio 2007 im Releasemodus:

    // Testmenge mit 2.500.000 Elementen
vector<unsigned int> v( 2500000 );

TStopWatch W;
W.start();
unsigned int x = 0;
for( vector<unsigned int>::const_iterator i = v.begin(); i != v.end(); ++i )
{
   x += *i;
}
W.stop();
add_message( "Naive iterator", W, Memo );

W.start();
x = 0;
for( vector<unsigned int>::const_iterator i = v.begin(), e = v.end(); i != e; ++i )
{
   x += *i;
}
W.stop();
add_message( "Prefetched end iterator", W, Memo );

W.start();
x = 0;
for( unsigned int i = 0; i < v.size(); ++i )
{
   x += v[i];
}
W.stop();
add_message( "Naive index", W, Memo );

W.start();
x = 0;
for( unsigned int i = 0, e = v.size(); i < e; ++i )
{
   x += v[i];
}
W.stop();
add_message( "Prefetched end index", W, Memo );

W.start();
for( unsigned int* i = &(*v.begin()), *e = &(*v.end()); i != e; ++i )
{
   x += *i;
}
W.stop();
add_message( "Prefetched end pointer", W, Memo );

W.start();
x = 0;
BOOST_FOREACH( unsigned int Value, v )
{
   x += Value;
}
W.stop();
add_message( "BOOST_FOREACH", W, Memo );

    Naive iterator took 0,0264539641869573 seconds.
Prefetched end iterator took 0,00462016474076954 seconds.
Naive index took 0,00191710601496845 seconds.
Prefetched end index took 0,000640968461645314 seconds.
Prefetched end pointer took 0,000638759177848174 seconds.
BOOST_FOREACH took 0,00569001041953471 seconds.

    Die Ergebnisse verwundern schon etwas. Dass die Pointer-Variante die schnellste ist ist klar, aber dass fast alle Versionen, die Iteratoren benutzen im Vergleich so schlecht abschneiden ist schon erstaunlich. Hat da jemand eine Erklärung/Idee zu den Ergebnissen?

    0
  • ?

    Assembler mal angeschaut?
    Vielleicht hat auch das warmlaufen aller Caches einen (kleinen) Einfluss, die Zeiten sind eigentlich auch recht kurz gewählt für aussagekräftiges Timing.
    Ansonsten würde ich auf den Faktor CodeGear RAD Studio tippen...

    0
  • ?

    DocShoe schrieb:

    Hat da jemand eine Erklärung/Idee zu den Ergebnissen?

    1. Zeiten zu klein, da kommt es zu Messungenauigkeiten.
    2. Je öfters du drüberiterierst, desto besser wird es gecached und deshalb wird es immer schneller gegen unten.

    Wenn du einen echten Performancevergleich machen willst, dann
    1. Zeig uns den generierten Assemblercode
    2. Wenn du Zeiten messen willst, miss grössere Datenmengen und öfters (mind. 100 mal jeden Typ) und alterniere die Reihenfolge.

    0
  • O

    DocShoe schrieb:

    Die Ergebnisse verwundern schon etwas.

    Hast du auch etwaige debugflags deiner standardbibliothek ausgemacht? Release Modus reicht beim VC++ zum Beispiel nicht. Keine Ahnung, was dein Compiler verwendet. Eventuell auch alter compiler. Mehr als eine Größenordnung Unterschied sind einfach nur unwahrscheinlich.

    Dass die Pointer-Variante die schnellste ist ist klar

    Für dich vielleicht, ich messe da keinen Geschwindigkeitsunterschied.

    0

  • So, ich habe das noch mal mit dem Visual Studio 2013 getestet und bin auf völlig andere Ergebnisse gekommen. Die Pointer Variante ist immer noch die schnellste, allerdings nur so geringfügig, dass das durchaus auch andere Ursachen haben könnte. Die einzelnen Ergebnisse schwanken zudem noch etwas, aber letztendlich benötigen der naive Indexzugriff und range-based for ca. 50% bzw. 60% länger als die übrigen Testfälle.

    Vermutlich treffen für diese Tests alle eure Vermutungen zu:

    1. der Testaufbau ist nicht gut
    2. der CG2007 optimiert nicht gut

    Ich war nur neugierig, weil ein Arbeitskollege berichtet hat, dass er Vektordurchläufe beschleunigen konnte, indem er Zeiger benutzt und keine Iteratoren. Für das CG2007 scheint das tatsächlich der Fall zu sein.

    PS:
    Das VS2013 hat sogar festgestellt, dass x nach den Schleifendurchläufen nicht mehr benutzt wird und das komplett rausoptimiert. Damit gab´s auch nur noch leere Schleifenkörper, die ebenfalls rausoptimiert wurden, sodass für alle Testfälle eine Laufzeit von 0s herauskam.

    0
  • ?

    otze schrieb:

    Hast du auch etwaige debugflags deiner standardbibliothek ausgemacht? Release Modus reicht beim VC++ zum Beispiel nicht.

    Interessant. Das wusste ich nicht. Was muss man denn noch setzen, damit die Debugflags ausgeschaltet sind?

    0
  • ?

    VCUser schrieb:

    Interessant. Das wusste ich nicht. Was muss man denn noch setzen, damit die Debugflags ausgeschaltet sind?

    Er meint das hier
    http://msdn.microsoft.com/de-de/library/aa985896%28v=vs.120%29.aspx
    Wenn du da die Doku auf frühere Versionen umschaltest, siehst du, dass bis 2008 das Iterator-Debugging auch im Releasemodus standardmäßig eingeschaltet war. Das betraf wohl VS2002 bis VS2008.

    0
  • ?

    Er meint das hier
    http://msdn.microsoft.com/de-de/library/aa985896(v=vs.120).aspx
    Wenn du da die Doku auf frühere Versionen umschaltest, siehst du, dass bis 2008 das Iterator-Debugging auch im Releasemodus standardmäßig eingeschaltet war. Das betraf wohl VS2002 bis VS2008.

    Ah OK. Aber das ist ja seit VS2010 "korrigiert"

    0
Anmelden zum Antworten