Performancefrage: Iteratoren



  • Welche dieser Varianten ist die performanteste?

    for(size_t i = 0, j = vec.size(); i < j; i++) {
        vec[i].TuIrgendWas();
    }
    
    for(size_t i = 0; i < vec.size(); i++) {
        vec[i].TuIrgendWas();
    }
    
    for(std::vector<XYZ>::iterator i = vec.begin(), j = vec.end(); i != j; ++i) {
        i->TuIrgendWas();
    }
    
    for(std::vector<XYZ>::iterator i = vec.begin; i != vec.end(); ++i) {
        i->TuIrgendWas();
    }
    

    Ich tippe auf die dritte, weil bei den ersten Beiden jeweils immer erst das i-te Element gesucht werden muss, während die Iteratorn (hoffentlich) ohne derartige Operationen auskommen. Das zweite und vierte Beispiel erfordert ggü. den anderen beiden allerdings noch deutlich mehr Funktionsaufrufe.
    Stimmt Ihr mir zu? Gibts irgendwelche Stolperfallen?



  • Nicht dass ich Ahnung von der tatsächlichen Realisierung hätte aber du arbeitest mit vektoren, sprich arrays, sprich der operator[] muss da überhaupt nichts suchen, das läuft ganz einfach über den Offset, anstatt suchen also ne simple Multiplikation. Und da der Iterator da auch nicht gross was anderes macht, glaub ich nicht, dass du da irgendwelche (bedeutenden) Geschwindigkeitsunterschiede wirst feststellen können.



  • naja schrieb:

    Multiplikation

    ähm, Addition natürlich 😃



  • Es kommt darauf an wie gut dein Compiler optimiert und wie groß (von der Anzhal) her vec ist. Mit weniger Optimierung würde ich auf jeden Fall zum ersten tendieren . Bei guter Optimierung würden glaube ich die ersten Zwei und die letzten Zwei das gleiche ergeben. Ich bin mit aber unsicher ob die Iteratoren wirklich wegoptimiert werden können. (Würde mich aber auch interessieren 🙂 )

    Grundsätzlich wird dies aber wahrschinlich keinen großen Geschwindigkeitsvorteil geben, wichtiger wäre (wenn überhaupt) .TuIrgendWas(); zu optimieren.


  • Mod

    Du darfst davon ausgehen, dass dies bei solch grundlegenden Sachen gänzlich wegoptimiert wird. ein vector<T>::iterator dürfte nicht viel mehr sein als ein typedef auf T*.



  • SeppJ schrieb:

    Du darfst davon ausgehen, dass dies bei solch grundlegenden Sachen gänzlich wegoptimiert wird. ein vector<T>::iterator dürfte nicht viel mehr sein als ein typedef auf T*.

    Na dann guck dir mal die Iteratoren von MSVC an 😉

    ----

    @ttttt:
    Was schneller ist, kommt auf so unglaublich viele Faktoren an, dass man es unmöglich voraussagen kann. Wenn es an einer Stelle wirklich wichtig ist, dann probier es an genau der Stelle in deinem Programm aus. Mit genau dem Compiler/Einstellungen/CPU/... wo es endgültig laufen soll. D.h. Release-Build und eben auf der Zielplattform testen.

    Was auf jeden Fall was bringen kann, ist den vector gänzlich aus dem Spiel zu nehmen, und rohe Pointer-Arithmetik zu verwenden.
    Also...

    size_t const size = vec.size();
    if (size) {
        T* data = &vec[0];
    
        for(size_t i = 0; i < size; i++) {
            data[i].TuIrgendWas();
        }
    
        // bzw.
    
        T* end = data + size;
        for(T* it = data, it != end; it++) {
            it->TuIrgendWas();
        }
    }
    

  • Mod

    hustbaer schrieb:

    SeppJ schrieb:

    Du darfst davon ausgehen, dass dies bei solch grundlegenden Sachen gänzlich wegoptimiert wird. ein vector<T>::iterator dürfte nicht viel mehr sein als ein typedef auf T*.

    Na dann guck dir mal die Iteratoren von MSVC an 😉

    Oh, ach ja. Hab ich irgendwie verdrängt 😃 . Die STL von Microsoft. Bestätigt seit 1992 immer wieder das C++ langsamer sein kann als C 😡 .



  • SeppJ schrieb:

    hustbaer schrieb:

    SeppJ schrieb:

    Du darfst davon ausgehen, dass dies bei solch grundlegenden Sachen gänzlich wegoptimiert wird. ein vector<T>::iterator dürfte nicht viel mehr sein als ein typedef auf T*.

    Na dann guck dir mal die Iteratoren von MSVC an 😉

    Oh, ach ja. Hab ich irgendwie verdrängt 😃 . Die STL von Microsoft. Bestätigt seit 1992 immer wieder das C++ langsamer sein kann als C 😡 .

    Und welche STL tut das nicht?


  • Mod

    hustbaer schrieb:

    Und welche STL tut das nicht?

    GNU? Und vermutlich auch die kommerziellen STLs (naja MS ist prinzipiell kommerziell), aber die kenne ich nicht aus eigener Erfahrung. Irgendwo geistert im Netz doch auch eine Implementierung von EA herum die auf gewisse Techniken in der Spieleentwicklung optimiert ist.



  • SeppJ schrieb:

    hustbaer schrieb:

    Und welche STL tut das nicht?

    GNU? Und vermutlich auch die kommerziellen STLs

    Äh.
    2x nein 🙂

    Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet. Trotzdem ist die an genug Stellen langsamer als vergleichbarer C-Code. Denk bloss mal an iostreams...


  • Mod

    hustbaer schrieb:

    Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet. Trotzdem ist die an genug Stellen langsamer als vergleichbarer C-Code. Denk bloss mal an iostreams...

    😮 Du willst doch wohl nicht ernsthaft die popeligen IO-Funktionen aus der C-Standardbibliothek mit den mächtigen IO-Streams vergleichen?

    edit: Vergleichen darfst du sie natürlich 😃 . Aber wenn du dabei feststellst, dass sie vergleichbar sind, dann ist dir nicht mehr zu helfen



  • Du willst doch wohl nicht ernsthaft behaupten dass man mit der Standard C++ Library alles gleich schnell (oder schneller) machen kann als mit vergleichbaren C-Konstrukten, wo man alles zu Fuss programmiert (weil man es muss)?

    EDIT: und natürlich sind die vergleichbar, was bist denn du für ein Vogel. OK, sie können mehr. Diese Feststellung ist das Resultat eines Vergleichs. Was impliziert dass sie vergleichbar sind, denn sonst ... alles klar? Mir ist schon klar was du meinst, nur mit vector+Iteratoren vs. nackte Arrays ist es nichts anderes.


  • Mod

    hustbaer schrieb:

    Du willst doch wohl nicht ernsthaft behaupten dass man mit der Standard C++ Library alles gleich schnell (oder schneller) machen kann als mit vergleichbaren C-Konstrukten, wo man alles zu Fuss programmiert (weil man es muss)?

    Natürlich sind die Sachen genauso schnell wie C-Konstrukte die das gleiche tun. Zumindest wenn die STL-Bauer keine ungeforderten Checks einbauen. Ein gut programmierter Vector mit Iteratoren ist exakt so schnell wie ein dynamisches Array mit Zählvariable, weil sie genau das gleiche machen. Das gilt auch für die anderen Teile der C++-Bibliothek.

    IO-Streams sind langsamer eben weil sie viel mehr können. Wenn man z.B. Zeichenfolgen in Zahlen umwandeln kann, kann man ein flottes atoi nehmen. Dann geht das aber nur mit ASCII-Dezimalzahlen. Will man alle möglichen Zahlenformate (eventuell sogar lokalisiert) als Quelle zulassen, muss man in C ordentlich dazu programmieren. Das Ergebnis dürfte in etwa so schnell sein wie ein ostream::operator>>(int). Da man dies nicht immer unbedingt braucht ist atoi auch nach wie vor ein Teil von C++.

    edit: Und du hast damit angefangen die umgangssprachliche Bedeutung von "vergleichbar" zu benutzen und solltest daher ganz genau wissen, was damit gemeint ist.



  • int main() 
    {
        const size_t size = 10000000;
        typedef std::vector<int> Vector;
        Vector a(size), b(size), c(size, 0);
        std::generate(a.begin(), a.end(), rand);
        std::generate(b.begin(), b.end(), rand);
        {
            HrTimer t;
            for(size_t n = 0; n < size; ++n)
                c[n] = a[n] * b[n];
        }
        {
            HrTimer t;
            for(Vector::iterator ia = a.begin(), ib = b.begin(), ic = c.begin(), ea = a.end();
                ia != ea; ++ia, ++ib, ++ic)
                *ic = *ia * *ib;
        }
        {
            HrTimer t;
            for(Vector::iterator ia = a.begin(), ib = b.begin(), ic = c.begin();
                ia != a.end(); ++ia, ++ib, ++ic)
                *ic = *ia * *ib;
        }
        {
            HrTimer t;
            std::transform(a.begin(), a.end(), b.begin(), c.begin(), std::multiplies<int>());
        }
        return 0;
    }
    
    // msvc10 #define _SECURE_SCL 0
    47.0475 ms
    45.8322 ms
    45.9266 ms
    46.7511 ms
    // msvc10 #define _SECURE_SCL 1
    49.4768 ms
    105.436 ms
    129.12 ms
    46.0183 ms
    

    Ich hab mir den Code nicht angeguckt, aber ich vermute mal das alle Versionen mehr oder weniger den gleichen Code generieren, wenn checked Iteratoren deaktiviert sind.
    In diesem Fall ist es also performance technisch völlig wurst.
    Ansonsten sind immer zunächst STL Algorithmen zu bevorzugen (dort gibt es oft für Spezialfälle effizientere Überladungen), wenn da nichst passt nehm ich die die Form for(Iter i = v.begin(), e = v.end(); i!=e; ++i) . Ich kann jetzt zwar keinen Fall konstruieren, wo der Aufruf von end() nicht wegoptimiert wird, aber diese Version gibt bei einfach ein besseres Gefühl;)



  • @HustBaer:

    Deine Aussage widerspricht aber der landläufigen Meinung im C++-Forum dass absolut nichts aber auch garnichts schneller ist, als die STL ( in jeglicher Form der Implementierung ) und was man auf keinen Fall tun sollte, ist irgendwelche Dinge, auf keinen Fall Container, selber zu programmieren... Auf gar keinen Fall!!!

    [Vorsicht, dieser Beitrag könnte ein gewisses Maß an Ironie enthalten] 😃


  • Mod

    It0101 schrieb:

    ( in jeglicher Form der Implementierung )

    Nee, das ist bekannt das dies nicht so ist. Es kommt schließlich jeden Monat jemand daher der die MSVC-STL mit C vergleicht und sich wundert warum diese im Releasemodus so langsam ist.



  • hustbaer schrieb:

    Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet.

    libstdc++ bietet beides. Den STL-Debug-Modus kann man per -D_GLIBCXX_DEBUG aktivieren.



  • Ja Blubb.

    Die C++ Std.Lib. macht diverse Vorgaben, die es nahezu bis gänzlich unmöglich machen eine performante Implementierung zu schreiben. Iostreams ist ein gutes Beispiel - das ganze Streambuffer Interface, die Locales etc.

    Die Behauptung dass eine C++ Std.Lib. Implementierung gleich schnell (oder schneller) sein kann, wie (als) "vergleichbarer" C-Code, ist daher mMn. sinnlos oder falsch.
    Sinnlos wenn man eine sinnlose Definition von "vergleichbarem" C-Code verwendet (die z.B. keinen C-Code erlaubt, der Features die nicht benötigt werden einfach weglässt).
    Und falsch wenn man eine sinnvolle Definition von "vergleichbarem" C-Code verwendet.

    Wer das anders sieht soll es anders sehen, ich bin die Diskussion ziemlich leid.

    Blubb.



  • SeppJ schrieb:

    Es kommt schließlich jeden Monat jemand daher der die MSVC-STL mit C vergleicht und sich wundert warum diese im Releasemodus so langsam ist.

    Und bemerkenswert ist auch, dass nur 95% dieser Leute vergessen, die Debug-Laufzeitumgebung und _SECURE_SCL abzuschalten. Ja, im Release-Modus.

    Aber trotzdem ein guter Grund für einen Microsoft-Flame. 👍


  • Mod

    It0101 schrieb:

    @HustBaer:

    Deine Aussage widerspricht aber der landläufigen Meinung im C++-Forum dass absolut nichts aber auch garnichts schneller ist, als die STL ( in jeglicher Form der Implementierung ) und was man auf keinen Fall tun sollte, ist irgendwelche Dinge, auf keinen Fall Container, selber zu programmieren... Auf gar keinen Fall!!!

    [Vorsicht, dieser Beitrag könnte ein gewisses Maß an Ironie enthalten] 😃

    Es ist tatsächlich schwer vorstellbar, dass das Programm schneller fertig wird, wenn zuerst grundlegende Datenstrukturen wie Container selbst entwickelt werden müssen.



  • Hab gerade mal getestet, wie VC++ (2005 Express) Vektoren mit Iteratoren umsetzt, und mir die Assemblerausgabe angeguckt (release, mit Optimierungen, kein secure_sonstwas_Brei).

    #include <vector>
    #include <iostream>
    using namespace std;
    int main() {
    
        int csize = 10000;
        int* c = (int*) malloc (csize*sizeof(int));
        int* cend = c + csize;
        int sc = 0;
        for( int* ip = c; ip < cend; ++ip )
            sc += *ip;
        printf("%d", sc);
        free(c);
    
        typedef vector<int> TV;
        TV cpp(10000);
        int scpp(0);
        for( TV::const_iterator it( cpp.begin() ); it != cpp.end(); ++it )
            scpp += *it;
        cout << scpp << endl;
    
        return 0;
    }
    
    ; Line 10
        cmp    esi, edx
        jae    SHORT $LN4@main
        npad    4
    $LL6@main:
    ; Line 11
        add    ecx, DWORD PTR [eax]
        add    eax, 4
        cmp    eax, edx
        jb    SHORT $LL6@main
    $LN4@main:
    
    ; Line 18
        mov    esi, DWORD PTR _cpp$[esp+52]
        mov    edx, DWORD PTR _cpp$[esp+56]
        xor    ecx, ecx
        cmp    esi, edx
        mov    eax, esi
        je    SHORT $LN1@main
        npad    4
    $LL24@main:
    ; Line 19
        add    ecx, DWORD PTR [eax]
        add    eax, 4
        cmp    eax, edx
        jne    SHORT $LL24@main
    $LN1@main:
    

    Zumindest für die Schleife (ohne Initialisierung) ist hier komplett das selbe bei rausgekommen (Line 11 und Line 19).
    Wie das bei komplexeren Geschichten aussieht, weiß ich nicht. Ich bin aber oft überrascht, was Compiler so für Optimierungen hinbekommen.
    Zur Streamfrage kann ich leider nix beitragen.


Anmelden zum Antworten