Geschwindigkeit rekursiver Funktionen mit und ohne STL



  • Hallo,

    versuchte eine rekursive Prozedur zu optimieren und es passierte folgendes:
    (>>>Relativer PseudoCode, nur um Idee zu zeigen<<<<)

    Die Ausgangsproz. belegt immer Speicher, der nicht benötigt wird
    (Normalverteilung, im Mittel hat die intlist ca. 40 Einträge),
    daher der Versuch mit Vector Containern variablen Speicher zu nutzen,
    der der Größe der Integerliste entspricht.

    Problem:
    a)
    Der STL-Code ist doppelt so langsam wie die speicherverschwendende
    Prozedur
    (Ausgangsprozedur wird 12 Mio. mal / Sekunde durchlaufen :D,
    STL-prozedur wird 6 Mio. mal / Sekunde durchlaufen 😞 ).
    b)
    Auch auf meinem Rechner mit 2GB-RAM kann ich mir so eine Speicherverschendung
    nicht leisten (ist keine INT-Liste, sondern größer)

    Frage:

    Welche Optimierungsmöglichkeiten gibt es, andere STL-Container?
    Was könnte verbessert werden ?

    Ziel:
    Gleiche Geschwindigkeit (max. 5-10% Einbusse) ohne Speicherverschwendung.

    Besten Dank,
    Björn

    Ausgangsprozedur:

    void fct (int zahl)
    {
    intlist int[200];
    fct(zahl+1)
    }

    Versuchte Optimierung mit STL:

    void fct (int zahl)
    {
    vector<int> intlist;
    fct(zahl+1)
    }



  • Du solltest schon deine Original-Datenklasse sowie den gesamten Code zeigen, ansonsten kann man pauschal dir keine Optimierungsvorschläge machen.
    Bei dem bisherigen Code mit 'int' dürfte es keinen Geschwindigkeitsunterschied geben (zumindestens im optimierten Release-Modus).
    Ich denke, du benutzt evtl. den STL-Vektor falsch.

    Du wirst aber immer eine Entscheidung Speicherplatz gegen Performance treffen müssen...

    Kannst du denn nicht vorher berechnen, wie groß deine Liste wird?
    Alternativ kannst du auch den STL-Vector mit 'reserve()' einen Startwert für den Speicher mitgeben, damit der Vector bei Größenänderung nicht zu oft umkopiert wird (Intern arbeiten die meisten STL-Implemenationen mit einer vorausschauenden Taktik, d.h. sie reservieren immer den doppelten Speicherplatz).



  • Danke für die Antwort.

    Ich benutze schon die <<Reserve>> Funktion von STL.

    Kann ich in der rekursiven Funktion ohne STL einen Trick
    anwenden, um nur die bestimme Anzahl an Datenplätzen
    für diese Prozedur anzufragen ?
    <<<

    Unten der etwas erweiterte Code, was meines derachtens
    aber nicht hilfreich sein wird.

    Der Hauptcode ist in 64bit Assembler und Besprechung hier wohl nicht
    zielführend. Mir geht es hauptsächlich um die rekursive
    Datenverarbeitung, wobei die Daten jeweils übergeben werden
    müssen.

    Um eine Programmierung von dynamischer Speicherplatzallokierung
    in Assembler zu umgehen, sollte mir C++ helfen, momentan tut es
    das aber nicht.

    Ohne die C++ Speicher-Hilfestellung wird der Code 40 Mio./Sek.
    ausgeführt. Der Abfall auf 12 Mio./Sek bzw. 6 Mio/Sek. ist schon bedauerlich.

    -----------
    struct value
    {
    long value1;
    long value2;
    signed long value3;
    signed long value4;
    signed long value5;
    signed long value6;
    };

    struct list
    {
    long count;
    value values [200];
    };

    Ursprungsroutine:

    void fct (int zahl)
    {
    list valueliste;

    CALL Erzeuge-Valuewerte
    for (long i=1; i<=anzahl; i++)
    {
    tmpvalue = ....
    valuelist.value...=tmpvalue;
    }
    fct(zahl+1)

    }

    Versuchte Optimierung mit STL:

    void fct (int zahl)
    {
    vector<value> valuelist;
    CALL Erzeuge-Valuewerte
    valuelist.reserve(anzahl);
    for (long i=1; i<=anzahl; i++)
    {
    tmpvalue = ....
    valuelist.push_back(tmpvalue);
    }
    fct(zahl+1)

    }



  • Kopfzerbrechen schrieb:

    Ausgangsprozedur:

    void fct (int zahl)
    {
    intlist int[200];
    fct(zahl+1)
    }

    Versuchte Optimierung mit STL:

    void fct (int zahl)
    {
    vector<int> intlist;
    fct(zahl+1)
    }

    1. Wie schon von Th69 gesagt: Vergleiche nur im Releasemodus ziehen
    2. Wenn du einen aktuellen MSVC verwendest solltest du zudem das Makro "#define SECURE_SCL 0" zumindestens für den Releasemodus verwenden.
    3. Das wird mit Sicherheit nicht deine Ausgangsprozedur sein. Oder sag mir mal was für ein Typ intlist ist ("intlist int[200];" sollte wohl eher "int intlist[200];" heißen).
    4. vectoren werden vorinitialisiert (Alle int-Werte sind 0), in dem Arrayfall findet keine solche Initialisierung statt. Dies macht schon einen Geschwindikeitsunterschied aus (nach meinen eigenen Tests der einzige wirkliche Unterschied, wenn man ansonsten vector richtig bedient). Wenn du das Array auch vorinitialisierst ("int intlist[200]();") wirst du vielleicht schon kleinere Unterschiede bemerken... Zudem (auch von Th69 gesagt: vectoren wenn man die Größe abschätzen kann mit reserve anpassen).
    5. Zu allen restlichen kann man sich nur unterhalten wenn man _echten_ Code sieht.

    cu André



  • Besten Dank, vielleicht bringts im Detail der Code.
    Unterschied bleibt in Geschwindigkeit bleibt bestehen, nach zahlreichen
    weiteren Untersuchungen.

    Der einzige Unterschied ist in den Speicheraufrufen meiner Meinung
    nach.

    Wieso ist STL so langsam?

    struct value
    {
    long valueinfo;
    };

    struct valuelist
    {
    long valuecount;
    value values [200];

    };

    void recursivenormal (signed long flag, long depth, long maxdepth)
    {
    valuelist pmlist;
    long start,end,anzahl,wert,empty;
    long* pointer;
    if (depth==maxdepth) {
    return;
    };
    if (flag==1) {
    depth+=1;
    genwvalues();
    pointer=&values;
    start=long(pointer);
    end=valuesoffset;
    anzahl=(end-start)/8;
    pmlist.valuecount=anzahl;
    for (long i=1; i<=anzahl; i++)
    {
    wert=*pointer;
    pointer=pointer+1;
    pmlist.values[i].valueinfo=wert;
    }
    for (long i=1; i<=anzahl; i++)
    {
    pmlist.values[i]=executewvalue(pmlist.values[i]);
    flag=-1;
    perftnormal(flag,depth,maxdepth);
    undowvalue(pmlist.values[i]);
    }
    } else {
    depth+=1;
    genbvalues();
    pointer=&values;
    start=long(pointer);
    end=valuesoffset;
    anzahl=(end-start)/8;
    for (long i=1; i<=anzahl; i++)
    {
    wert=*pointer;
    pointer=pointer+1;
    pmlist.values[i].valueinfo=wert;
    }
    for (long i=1; i<=anzahl; i++)
    {
    pmlist.values[i]=executebvalue(pmlist.values[i]);
    flag=1;
    perftnormal(flag,depth,maxdepth);
    undobvalue(pmlist.values[i]);
    }
    }
    };

    void recursivestl (signed long flag, long depth, long maxdepth)
    {
    value tmpvalue;
    vector<value> vvaluelist;
    long start,end,anzahl,wert,empty;
    long* pointer;

    if (depth==maxdepth) {
    return;
    };
    if (flag==1) {
    depth+=1;
    genwvalues();
    pointer=&values;
    start=long(pointer);
    end=valuesoffset;
    anzahl=(end-start)/8;
    nodes+=anzahl;
    vvaluelist.reserve(anzahl);
    for (long i=1; i<=anzahl; i++)
    {
    wert=*pointer;
    pointer=pointer+1;
    tmpvalue.valueinfo=wert;
    vvaluelist.push_back(tmpvalue);
    }
    for (long i=0; i<anzahl; i++)
    {
    tmpvalue=vvaluelist[i];
    tmpvalue=executewvalue(tmpvalue);
    flag=-1;
    perft(flag,depth,maxdepth);
    undowvalue(tmpvalue);
    }
    } else {
    depth+=1;
    genbvalues();
    pointer=&values;
    start=long(pointer);
    end=valuesoffset;
    anzahl=(end-start)/8;
    vvaluelist.reserve(anzahl);
    for (long i=1; i<=anzahl; i++)
    {
    wert=*pointer;
    pointer=pointer+1;
    tmpvalue.valueinfo=wert;
    vvaluelist.push_back(tmpvalue);
    }
    for (long i=0; i<anzahl; i++)
    {
    tmpvalue=vvaluelist[i];
    tmpvalue=executebvalue(tmpvalue);
    flag=1;
    perft(flag,depth,maxdepth);
    undobvalue(tmpvalue);
    }
    }
    };

    int main(void)
    {
    struct tms t,u;
    long r1,r2,r3,r4;
    char tchar;

    maxdepths=6;
    r3 = times(&t);
    recursivenormal(1,0,maxdepths);
    r4 = times(&u);
    cout << "REKURSIV - NORMAL" << endl;
    printf("user time=%f\n",((float)(u.tms_utime-t.tms_utime))/(HZ));
    printf("system time=%f\n",((float)(u.tms_stime-t.tms_stime))/(HZ));
    printf("real time=%f\n",((float)(r4-r3))/(HZ));

    cout << endl;
    showboard();
    cin.get(tchar);

    r1 = times(&t);
    recursivestl(1,0,maxdepths);
    r2 = times(&u);
    cout << "REKURSIV - STL" << endl;
    printf("user time=%f\n",((float)(u.tms_utime-t.tms_utime))/(HZ));
    printf("system time=%f\n",((float)(u.tms_stime-t.tms_stime))/(HZ));
    printf("real time=%f\n",((float)(r2-r1))/(HZ));
    cout << endl;
    cin.get(tchar);

    }



  • Kopfzerbrechen schrieb:

    Wieso ist STL so langsam?

    Ich tippe mal auf falsche Benutzung. Die STL ist an sich recht schnell (wobei in einzelnen Bereichen unterschiedliche STL-Implementierungen langsam sind, beispielsweise wurde vor einiger Zeit hier im Forum etwas über Streams und MSVC geschrieben - Am Schluß mit einer Lösung).

    Könntest du aber bitte mal die C/C++ Tags verwenden, dein Code lässt sich so, gelinde gesagt nicht sinnvoll lesen. Ganz davon abgesehen das du C und C++ recht wild mischst.
    Und: Da ich den Code nicht ausgeführt bekomme (ist unvollständig), werde ich jetzte nicht versuchen dein Codekauderwelsch zu interpretieren.

    cu André



  • schon mal im Release modus kompiliert oder nur debug?



  • Debug oder Release Modus zeigen keinen signifikanten Unterschied.
    😞

    C/C++ ist nicht meine "Heimatsprache" ( 😕 ) , sonst würde mein Code nicht
    "gemischt" sein, was immer das bedeuten mag (Hinweis, wo ich denn
    "gemischt" habe?).

    Dennoch, so schlecht scheint es nicht zu sein:
    der Compiler g++ beschwert sich auch im WALL-Mode nicht (keine Meldungen!).

    Noch einmal der Hinweis, der Code ist gleich bis auf die Speicherallokierung.

    Wo könnte denn der STL-Container Vector nicht korrekt angesprochen sein
    (z.B. C konform, aber nicht C++ konform ?) ?

    Einen Vergleich allein mit "INT" als Speicherwert brachte in der Tat eine
    gleiche Performance. Die Reihenfolge in der ich den Code ausführe (zuerst
    STL-Code und dann Normal oder anders herum) brachte das gleiche Ergebnis.
    (Hypothese von wegen Cache, etc. + interessanterweise ein Unterschied vom
    Faktor 2, was immer verdächtig ist).

    Habe hier aber keine Lösung gefunden, warum es ausgerechnet ein Faktor zwei
    ist. Auch der Code zeigt keinen Hinweis darauf. In beiden Fällen wird die
    Schleife gleich oft durchlaufen (Überprüfung durch Zähler).



  • Trotzdem nutze doch bitte endlich mal die C/C++-Tags. Dazu schaust Du Dir am besten mal ein paar der anderen Beiträge an, wunderst Dich, wieso der Code dort immer so schön eingerückt in einem weissen Kasten steht, und beachtest dann mal die Knöpfe unterhalb des Editors, wenn Du einen Beitrag schrteibst.



  • Danke für die Anregungen, wie schon gesagt, der gezeigte Code war vollkommen
    ausreichend um einen Lösungsansatz aufzuzeigen / Problemursache erläutern.

    Habe die "Lösung" gefunden:

    http://www.tutorials.de/forum/c-c/208260-c-stl-vector-push_back-ist-sehr-langsam-schleife.html

    Mal wider das übliche Problem von C/C++. Kaum einer kennt die genauen
    Abläufe hinter den Kulissen und permanent treten "Bugs" auf.
    Z.B. was mir noch eine Menge Zeit gekostet hat:

    64 Bit Zahl ausgeben mit printf(%x,varname) geht nicht (nur 32 Bit)
    Bit Shifts gehen auch nicht sinnvoll ohne Recherche
    1 << 45 geht voll in die Hose (1L << 45 geht, aber woher wissen?)

    Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.



  • Kopfzerbrechen schrieb:

    Danke für die Anregungen, wie schon gesagt, der gezeigte Code war vollkommen
    ausreichend um einen Lösungsansatz aufzuzeigen / Problemursache erläutern.

    LordJaxom sagte das auch eher wegen derer, die den Post lesen. Für dich ist es jedoch auch von Vorteil, wenn sich dank schöner Formatierung mehr Leute deinen Post anschauen.

    Kopfzerbrechen schrieb:

    Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.

    Wenn du damit fehlerfreier programmieren kannst, dann viel Spass damit. 😉



  • Kopfzerbrechen schrieb:

    64 Bit Zahl ausgeben mit printf(%x,varname) geht nicht (nur 32 Bit)

    Mal im Ernst, falsch benutzen kann man jede Bibliothek in jeder Sprache. "%x" ist für den Datentyp int, kein Wunder dass Du da keine 64 bit Zahl mit rausbekommst.



  • Kopfzerbrechen schrieb:

    Mal wider das übliche Problem von C/C++. Kaum einer kennt die genauen Abläufe hinter den Kulissen und permanent treten "Bugs" auf.
    ...
    Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.

    1. Kann keiner die bei dir verwendete Umsetzung der C++ Standardbibliothek kennen, da der Standard nur Rahmenbedingungen festlegt, nicht aber WIE die Implementierung zu erfolgen hat.
    2. Magst du vielleicht der Meinung sein das dein Codeschnipsel reicht, nur wenn man diesen nicht ausführen kann, wird man dir kaum sagen können was besser zu machen ist.
    3. Dein Code ist gelinde gesagt bescheiden zu lesen, die fehlenden Tags verschlimmern das noch. Und nein, mindestens ich werde jetzt deinen Code nicht analysieren.
    4. Bugs habe ich bislang in der C++ Implementierung nahezu 0 erlebt. In der Regel sitzt das Problem vor dem Rechner (da nehme ich auch mich nicht aus). Viel Spaß mit Assembler, spätestens für große Projekte - C++ programmiert man nunmal anders als Assembler.
    5. [Nachtrag] Wer sich nicht mit einer Sprache auseinander setzt brauch sich auch nicht zu wundern wenn ihm einige "Bugs" auffallen...

    cu André



  • So, und um jetzt den Irrglauben gegen langsame vectoren etwas auszumerzen, sei neben meinen Post in diesem Thread hier, auch noch folgendes Beispiel zu nehmen.

    Getestet unter MSVC 2008, unter Verwendung von push_back, und verglichen mit einmal einen initialisierten und einmal einen uninitialisierten Array:

    1. Fall: ca. 0,36 Sekunden (Uninitialisiertes Array)
    2. Fall: ca. 0,55 Sekunden (Initialisiertes Array)
    3. Fall: ca. 0,45 Sekunden (vector mit reserve und push_back)

    Also ich sehe da keinen Faktor 1:3, sondern wenn schon 1:1,25... Also träum weiter.

    #define _SECURE_SCL 0
    
    #include <vector>
    #include <boost/progress.hpp>
    
    int main()
    {
        for(int i=0; i<5; ++i)
        {
            boost::progress_timer t;
            {
                long* list = new long[100000000]; // Ohne Elementinitialisierung
    			for(int i=0; i<100000000; ++i)
    				list[i] = i;
                delete[] list;
            }
        }
        for(int i=0; i<5; ++i)
        {
            boost::progress_timer t;
            {
                long* list = new long[100000000](); // Mit Elementinitialisierung
    			for(int i=0; i<100000000; ++i)
    				list[i] = i;
                delete[] list;
            }
        }
        for(int i=0; i<5; ++i)
        {
            boost::progress_timer t;
            {
                std::vector<long> list;
    			list.reserve(100000000);
    			for(int i=0; i<100000000; ++i)
    				list.push_back(i);
            }
        }
        return 0;
    }
    

Log in to reply