3. for-Optimierung

for-Optimierung

  • M

    cooky451 schrieb:

    Langsam wird's lustig. 😃 Aber dafür verstehe ich etwas mehr was pumuckl meint.

    Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

    #include <vector>
#include <iostream>
using namespace std;

int main()
{
        vector<int> foo(2, 0);
        for(auto i = foo.size(); i >= 0; --i)
        {
                cout << i << endl;
                if(i > 1000) break;
        }
}

    Ausgabe:

    2
1
0
4294967295
    0
  • C

    Michael E. schrieb:

    Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

    Wenn du noch ein bisschen überlegst und dir den Code anguckst den ich gepostet habe, wirst du verstehen warum das lustig ist. 😉
    Tipp: Die von dir geschriebene Schleife ist zu meiner grundverschieden.

    @otze
    Also ich weis nicht. Mir sind die ganzen Varianten alle gleich geläufig, und offen gesagt ist mir völlig egal was davon man benutzt, ich kann das alles gleich gut lesen. Und per default die langsamere Variante zu benutzen leuchtet mir einfach nicht ein.

    0
  • P

    cooky451 schrieb:

    Und selbst wenn man völlig verwirrt ist und aus dem Konzept kommt verliert man so höchstens 3 mal eine Minute, das ist es definitiv wert.

    Ist es das? Zwei parallele Konventionen, für Schleifen, die nur dann semantisch gleichwertig sind, wenn die Reihenfolge keine Rolle spielt. Und als Ergebnis kriegen wir eine schnellere Ausführung des Schleifenkopfes (wie viel schneller eigentlich?), dessen Performanceimpakt vielleicht in einem von hundert Fällen wirklich was ausmacht (wenn überhaupt). Richtig auszahlen wird sich sowas vermutlich nur, wenn man Schleifen über riesige Bereiche hat (Numerik, Bildverarbeitung, ...?), deren Schleifenrümpfe nur sehr wenig Zeit benötigen (sonst fällt der Schleifenkopf prozentual nicht ins Gewicht und man sollte eher an der Anzahl der Iterationen schrauben). Vielleicht abgesehen von besagten speziellen Bereichen, wo solche Schleifen häufig vorkomemn, sehe ich da keinerlei Gewinn. Oder anders gesagt: Dem Ottonormalentwickler kommt nur höchst selten ein Fall unter, wo das Konstrukt eine messbare Optimierung darstellt. Das als allgemeinen Standard zu propagieren, der keines Kommentars bedarf, ist absurd. Wenn du in einem Projekt arbeitest, in dem ein großer Teil der Schleifen davon profitieren, dann machs im Projekt zum Standard. Ich bin zufälligerweise mit der Performanceoptimierung in einem Projekt vertraut, in dem viele Schleifen vorkommen, bei denen Reihenfolge keine Rolle spielt (aktuarieller Rechenkern für Lebensversicherungssoftware). Auch solche Schleifenoptimierungen sind dort schon erwägt worden, weil Performance hier wirklich eine Rolle spielt. Es bringt nur kein Ergebnis, das die Aufwände für eine entsprechende Umstellung rechtfertigen würde.

    0
  • ?

    cooky451 schrieb:

    Am besten ein paar mal hintereinander laufen lassen, damit der RAM vorbereitet ist. n zwischen 512 und 1024 sollte gute Ergebnisse bringen.

    .. und wie sind die Ergebnisse?

    Mein Benschmark liefert folgendes:

    klassisch
5000000 0s
dekrementierend
5000000 0.0179735s
abgefahren
5000000 0.0135209s

    interessanterweise ist selbst die Variante mit counting_iterator (s.u.) und Algorithmus geringfügig schneller als die dekrementierende Variante

    und hier ist der Code dazu

    int foo() { return 1000*(2000 + 8000); }

int main()
{
    using namespace std;
    Watch uhr;
    {
        cout << "klassisch" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        int bla = foo();
        for( int i=0; i<bla; ++i )
            counter += i % 2? +i: -i;
        cout << counter << " " << uhr << endl;
    }
    {
        cout << "dekrementierend" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        for( int i=foo(); i-- != 0; )
            counter += i % 2? +i: -i;
        cout << counter << " " << uhr << endl;
    }
    {
        cout << "abgefahren" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        for_each( boost::counting_iterator< int >(0), boost::counting_iterator< int >(foo()), [&counter]( int i ) { counter += i % 2? +i: -i; } );
        cout << counter << " " << uhr << endl;
    }
}
    0
  • M

    cooky451 schrieb:

    Michael E. schrieb:

    Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

    Wenn du noch ein bisschen überlegst und dir den Code anguckst den ich gepostet habe, wirst du verstehen warum das lustig ist. 😉
    Tipp: Die von dir geschriebene Schleife ist zu meiner grundverschieden.

    Sorry, mein Fehler. Bin noch nicht wach. Ich dürfte aber meinen Punkt rübergebracht haben, dass ich deine Variante nicht so leserlich finde 😉

    0
  • C

    Michael E. schrieb:

    Ich dürfte aber meinen Punkt rübergebracht haben, dass ich deine Variante nicht so leserlich finde 😉

    Ja, irgendwie war das die bestmögliche Argumentation. 😃

    0
  • C

    pumuckl schrieb:

    Ist es das? Zwei parallele Konventionen, für Schleifen, die nur dann semantisch gleichwertig sind, wenn die Reihenfolge keine Rolle spielt.

    Also das Zeug <algorithm> sollte man auch lieber nicht nutzen, wenn es eine relativ einfache Schleife als Alternative gibt? Sorry, aber solange Konventionen so simpel sind, sehe ich da kein Problem.

    pumuckl schrieb:

    Das als allgemeinen Standard zu propagieren, der keines Kommentars bedarf, ist absurd.

    Also ich weiß nicht. Ich finde jeden etwas ausgefeilteren iostream/Template Trick etwa 100 mal schwieriger zu verstehen. Ganz zu schweigen von Algorithmen selbst. Schleifenköpfe bei so etwas zu durchblicken macht bei mir nicht mal ein Promille der Zeit aus, die ich brauche um fremden Code zu verstehen. (Wenn er nicht gerade nur aus dieser einen Schleife besteht. ;))

    pumuckl schrieb:

    (wie viel schneller eigentlich?)

    Werner_logoff schrieb:

    .. und wie sind die Ergebnisse?

    Die Schleife vorwärts dauert bei mir ~1.05 Sekunden, die andere ~0.65.

    An deinem Beispiel arbeite ich gerade Werner, der macht da bei mir lustige Sachen mit mmx Registern, ich blicke da noch nicht so wirklich durch. Mal sehen. Aber die Beispiele laufen gleich schnell bei mir. (boost kann ich gerade nicht testen.) Ich hatte eben sogar eine Variante, bei der klassisch schneller war. Bin ja mal gespannt. 🙂

    0
  • P

    cooky451 schrieb:

    Also das Zeug <algorithm> sollte man auch lieber nicht nutzen, wenn es eine relativ einfache Schleife als Alternative gibt?

    Klares jein. Die Dinge aus <algorithm> sind Abstraktionen, die quasi die Schleife in eine eigene Funktion auslagern. Häufig wird aus der Schleife ein Einzeiler, was wiederum bessere Lesbarkeit hervorbringt (vorausgesetzt, der Leser weiß, was der Algorithmus macht). Selbst bei Dingen wie z.B. std::transform mit einem Mehrzeiler-Lambda wird das "transformiere alles von A nach B" und "so transformierst du ein Element" voneinander getrennt, => besser lesbar. Wenn eine Funktion aus <algorithm> allerdings genauso durch eine sehr einfache Einzeler-for-Schleife (bitte mit üblichem Kopf! :p) ausgedrückt werden kann, ist die Schleife genauso gut. Wenn man sich für den Algorithmus erst irgendwelche Iteratoren auf komplizierte Weise aus den Rippen leiern muss, kann eine Schleife sogar lesbarer sein - ich denke da z.B. an die Situation, wo man ein Array und Indizes hat. Beispiel:

    unsigned a, b; 
int arr[N];

//schleife:
for (auto i = a; i < b; ++i)
{
  arr = 2*i;
}

//algo:
std::generate(arr+a, arr+b, [a](){static auto i = a; return 2*i++;}); //WTF?

    Vielleicht gibts elegantere Algorithmen dafür, mir fällt grade keiner ein. Sehr zweielhaft finde ich auch solche Dinge wie

    copy(begin(x), end(x), ostream_iterator<Foo>(cout, " (meh) ");

    imo sind manche Benutzungen von Algorithmen zwar "fancy", wobei der Entwickler zeigen kann "schau mal, ich kenne die Standarbiblitohek, ich kanns als Einzeiler!!", aber oft grenzt sowas auch an Obfuscation.

    Also ich weiß nicht. Ich finde jeden etwas ausgefeilteren iostream/Template Trick etwa 100 mal schwieriger zu verstehen. Ganz zu schweigen von Algorithmen selbst.

    Auch solche iostream/Template-Tricks sollten nur angewandt werden, wenn sie wirklich was bringen, und dann sollte auch kurz kommentiert werden, was sie bringen.

    Schleifenköpfe bei so etwas zu durchblicken macht bei mir nicht mal ein Promille der Zeit aus, die ich brauche um fremden Code zu verstehen.

    Schleifenköpfe sollten garnicht erst durchblickt werden müssen, man sollte dafür [i]garkeine* Zeit aufwenden müssen. Über einen Schleifenkopf sollte man drüberhuschen können wie über ein int a = 10; - das ist eben bei den "normalen" Köpfen gegeben. Der dekrementierende Kopf geht eben in die Richtung "fancy tricks" - und auch wenn der Trick noch so schnell zu durchschauen ist, stört er erstmal beim flüssigen Drüberlesen. Natürlich kann man sich das angewöhnen. Aber es ist ja nicht so, dass man im Projekt nur eine Handvoll Entwickler hat, die sich das schnell angewöhnen und danach kommt nie jemand neues dazu. Es gibt immer jemanden der sowas zum ersten mal sieht, und deshalb kostet sowas durchgehend Zeit, bei weitgehend beschränktem Nutzen.

    Ich will sowas nicht verbieten. Ich will nur wie andere auch schon geschrieben haben, dass man es mit Bedacht einsetzt (d.h. wenn man es braucht), dass man es nicht präventiv auf Kosten der Lesbarkeit einsetzt (premature optimization), und dass man mit einem kleinen sinnvollen Kommentar den Leuten wieder auf die Beine hilft, die das Konstrukt nicht kennen und deshalb ins Straucheln kommen. Das reduziert einfach die Zeit, die man braucht, um mit dem Konstrukt warm zu werden 🙂

    /* ggf. performantere Alternative zu for(unsigned i = 0; i < foo(); ++i) */
for(auto i = foo(); i-- !=0;)
{ 
  /* ... */
}
    0

  • Was man bei der dekrementierenden Variante auch noch unbedingt berücksichtigen sollte: Jede CPU wird schlau genug sein, beim Vorwärtsiterieren zu checken, welche Dinge als nächstes in den Cache müssen. Beim Rückwärtsiterieren wär ich mir da nicht mehr so sicher, auch wenn es auf einem Desktop Core i7 keinen Unterschied macht...

    0
  • C

    dot schrieb:

    Beim Rückwärtsiterieren wär ich mir da nicht mehr so sicher, auch wenn es auf einem Desktop Core i7 keinen Unterschied macht...

    Hm, wenn ich in Optimization Guides lese, dass viele CPUs schon simple Muster erkennen können (z.B. immer wechselnde Branches und Ähnliches), bin ich mir bei dem Zeug ziemlich sicher, zumindest bei allem was jünger als 10 Jahre ist. 😉

    Zu Werners Test kann ich nur sagen: Ist ein interessanter Fall, aber der Compiler scheint da einige Optimierungen durchzuführen, die er bei der dekrementierenden Variante nicht schafft. Aber oft habe ich sowas noch nicht gesehen. Etwas abgeändert sieht es auch wieder ganz anders aus:

    unsigned foo() { return 2684354565UL; }

int main()
{
  using namespace std;
	unsigned n;
	std::cin >> n;
  {
    cout << "klassisch" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    unsigned bla = foo();
    for( unsigned i = 0; i < bla; ++i )
        counter += i * n;
				//counter += i % 2 ? + i : i * 2;

		cout << counter << " " << duration_cast<float>(w.elapsed()) << endl;
  }
  {
    cout << "dekrementierend" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    for( unsigned i = foo(); i-- != 0; )
        counter += i * n;
				//counter += i % 2 ? + i : i * 2;

		cout << counter << " " << duration_cast<float>(w.elapsed()) << endl;
  }
}

    2.14 vs 1.66 Sekunden.

    @pumuckl
    Wie gesagt, ich finde die Varianten sind alle gleich schnell zu lesen, bzw. die dekrementierende sogar besser (insbesondere ist sie leichter zu schreiben). Aber so langsam wiederholen wir uns, ich denke die Argumente liegen auf dem Tisch. 😉

    0
  • C

    cooky451 schrieb:

    unsigned foo() { return 2684354565UL; }

int main()
{
  using namespace std;
	unsigned n;
	std::cin >> n;
  {
    cout << "klassisch" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    unsigned bla = foo();
    for( unsigned i = 0; i < bla; ++i )
        counter += i * n;
				//counter += i % 2 ? + i : i * 2;

		cout << counter << " " << duration_cast<float>(w.elapsed()) << endl;
  }
  {
    cout << "dekrementierend" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    for( unsigned i = foo(); i-- != 0; )
        counter += i * n;
				//counter += i % 2 ? + i : i * 2;

		cout << counter << " " << duration_cast<float>(w.elapsed()) << endl;
  }
}

    2.14 vs 1.66 Sekunden.

    Ausgabe auf einem (runtergetakteten) Core2Quad:

    11
klassisch
4026531950 2.59617
dekrementierend
4026531950 2.68544

    Die "11" habe ich eingetippt.

    Ich habe diesen Test 3 Mal laufen lassen mit verschiedenen Eingaben für "n". In jedem Durchlauf war die Dekrementier-Variante langsamer als die Inkrementier-Variante.

    Hätte mich auch gewundert, wenn das Dekrementieren auf heutigen CPUs noch in irgendeiner Weise schneller wäre.

    0
  • C

    Christoph schrieb:

    Hätte mich auch gewundert, wenn das Dekrementieren auf heutigen CPUs noch in irgendeiner Weise schneller wäre.

    Aber dass Inkrementieren schneller ist wundert dich nicht? 🤡
    Ne ernsthaft, das ist nicht der Vorteil. Der Unterschied sieht (ohne Optimierungen mit dem Schleifenkörper) in etwa so aus:

    unsigned foo()
{
	__asm
	{
		sub eax, eax
		sub esi, esi
loop1:
		add eax, esi
		inc esi
		cmp esi, 1234567890
		js loop1
	}
}

unsigned bar()
{
	__asm
	{
		sub eax, eax
		mov esi, 1234567890
loop1:
		dec esi
		add eax, esi
		test esi, esi
		jnz loop1
	}
}

    Und das dürfte nicht sonderlich CPU abhängig sein. 😉
    Da du gleiche Laufzeiten bekommst, habe ich es mal mit GCC 4.6 probiert (-O3 -march=native). Da bekomme ich auch beide male ~2.4 Sekunden. Leider kann ich mir den ASM Code so leicht nicht angucken, aber irgendwas scheint VS hier bedeutend besser zu machen. (Mein ursprünglicher Benchmark mit dem vector "funktioniert" mit beiden Compilern.)

    0
  • K

    cooky451 schrieb:

    [...] Leider kann ich mir den ASM Code so leicht nicht angucken [...]

    Probier es mal mit objdump -Cd

    cooky451 schrieb:

    cout << "klassisch" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    unsigned bla = foo();
    for( unsigned i = 0; i < bla; ++i )
        counter += i * n;

    ...
    << endl;

    cout << "dekrementierend" << endl;
    stopwatch<> w;

    unsigned counter = 0;
    for( unsigned i = foo(); i-- != 0; )
        counter += i * n;

    Also, nur in der Hoffnung, dass der Test der Laufvariablen gegen 0 schneller funzt als gegen einer zur Laufzeit abhängigen Konstante, schreibe ich keine Rückwärts-Loops. Aber ich finde, solche Loops sind durchaus nachvollziehbar. Habe erst letzten Samstag

    for (b=blocks; b-->0; ) { 
    ...
 }

    geschrieben, weil ich rückwärts durch ein Array laufen musste. Ich find' das voll okay so ...

    0
  • K

    1.) Compiler sind auch nur Menschen, d.h. prasentiert man ihnen bekannte Muster, dann koennen sie besser optimieren.
    2.) Ich lese von links nach rechts, beginne bei 0 mit dem Zaehlen, ... ohne Grund iteriere ich nicht rueckwaerts durch ein Array. Und wenn solche Schritte optimiert werden muessen, dann reife ich zu Intrinsics.

    Aber hey, Hauptsache wir reden ueber so einen Firlefanz. Um die Ausgangsfrage ""macht ein Compiler mit Release-Optionen .." zu beantworten: Kommt drauf an, was in der for-Schleife steht.

    0

  • @cooky451
    Ich programmiere seit ca. 20 Jahren, davon ca. 13 Jahre beruflich in C++: kein Mensch schreibt rückwärts Schleifen oder mag rückwärts Schleifen lesen wenn es dafür keinen guten Grund gibt.
    Und dass ein Test gegen 0 um den einen oder anderen halben Zyklus schneller ist als ein Test gegen einen Wert != 0 ist in 99% der Fälle kein guter Grund.

    Gewöhn' dir an einfachen, "dummen" Code zu schreiben. "Dummer" Code ist einfach viel angenehmer zu lesen und zu warten.

    Davon abgesehen...
    Wir hatte hier erst vor ein paar Monaten ne Diskussion ob CPUs rückwärts-Streams beim Prefetching checken. Ergebnis: die meisten rückwärts-Schleifen waren ein wenig langsamer als die vorwärts-Schleifen. Nicht viel, aber messbar.
    So viel zum Thema schneller.

    Und was du findest was einfacher zu lesen ist, ist wohl vollkommen irrelevant, wenn du primär die Variante verwendest von der so ziemlich alle hier meinen dass sie schlechter zu lesen ist.

    Man kann es z.B. auch so schreiben:

    for (size_t i = foo(); ~i; i--)
    ...

    Wenn ich das immer so schreibe, dann wird es für mich auch super-easy zu lesen sein.
    Wenn ich es dann allerdings wem anderen zeigen würde, würde mir der zu Recht nen Vogel zeigen.

    0
  • K

    hustbaer schrieb:

    Man kann es z.B. auch so schreiben:

    for (size_t i = foo(); ~i; i--)
    ...

    Die macht übrigens was anderes, die Schleife. Sie läuft
    von einschließlich foo() bis ausschließlich 0.
    Wie würdest du denn eine Schleife bauen, die
    von ausschließlich foo() bis einschließlich 0
    läuft?

    Hätte gedacht, dass

    for (size_t i = foo(); i-->0; )
    ...

    auch so ein "Standardmuster" ist.
    --> ist doch der "runs down to"-Operator. 😉

    Wie soll man das denn bitte "in doof" aufschreiben, dass keiner drüber stolpert?

    0
  • K

    krümelkacker schrieb:

    for (size_t i = foo(); ~i; i--)
    ...

    Sie läuft von einschließlich foo() bis ausschließlich 0.

    Bei mir lauft sie sogar bis einschliesslich 0.

    Wie würdest du denn eine Schleife bauen, die
    von ausschließlich foo() bis einschließlich 0
    läuft?

    for (size_t i = foo()-1; ~i; i--)

    So?

    0
  • ?

    knivil schrieb:

    for (size_t i = foo()-1; ~i; i--)

    So?

    aber dann verliert man den Bonus durch den Vergleich gegen 0.

    Dann doch lieber den Fall explizit unrollen:

    for(size_t i= size()-1; i!=0; --i)
   arr[i] = x;
arr[0] = x;

    Das einzige, was dann noch schief gehen kann, ist beim Fall size() == 0

    0
  • W

    Der Compiler ist also schlau genug, zu erkennen, ob sich während der Schleife etwas am Funktionswert ändert und optimiert gegebenenfalls.
    Ok, danke 🙂

    0
  • M

    Wurstinator schrieb:

    Der Compiler ist also schlau genug, zu erkennen, ob sich während der Schleife etwas am Funktionswert ändert und optimiert gegebenenfalls.

    Nein, siehe Antwort von knivil. Ich bin sogar ziemlich skeptisch, ob er das bei so vielen Funktionen tatsächlich erkennen kann. Trotzdem würde ich den Endwert nur selten rausziehen, außer ich weiß von vornherein, dass der Compiler das nicht erkennen kann und es was ausmacht (z.B. COM Aufrufe).

    @Cooky: typische Einstellung von einem Schüler 😉 Ich habe damals auch so gedacht. Aber robuster, allgemein gut lesbarer Code ist sehr viel wichtiger als irgendwelche obskuren Tricks oder potentielle minimale Optimierungen. Ich habe so eine Schleife wie bei dir noch nie im Real Life Code gesehen, und überhaupt hab ich noch nie eine Schleife gesehen, die rückwärts iteriert, außer es ist explizit so gewollt, und ich will sowas auch nicht sehen 😉
    Auch mit irgendwelchem Templatecode würden sich zumindest bei uns in der Arbeit gleich mal paar nicht ganz unwichtige Leute beschweren. Wenn das interner Code ist, den niemand direkt benutzt und der gekapselt ist, ok. Aber wenn das zum "normalen" "Hauptcode" gehört, wo jeder dran arbeitet und das jeder irgendwo verstehen muss, oder auch mal schnell ändern/fixen, wenn der jenige im Urlaub ist, oder man das Projekt übernommen hat oder was auch immer, keine Chance. Niemand will da Template Code sehen und sich schon gar nicht in sowas reindenken. Ausnahmen sind interne Bibliotheken, wo das wirklich Sinn macht. Aber je "dümmer" und einfacher der normale Code ist, desto besser.

    0
Anmelden zum Antworten