for-Optimierung

dot

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...

cooky451

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.

Christoph

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.

cooky451

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.)

krümelkacker

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 ...

knivil

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.

hustbaer

@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.

krümelkacker

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?

knivil

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?

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

Wurstinator

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

Mechanics

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.

Wurstinator schrieb:

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

Bei Funktionen in einer anderen Übersetzungeinheit nicht. Der GCC könnte es wahrscheinlich, wenn du die aufzurufende Funktion als "pur" deklarierst, aber das ist dann nicht mehr portabel. Eine andere Möglichkeit wäre Link-Time-Optimization.

hustbaer

Die ~i Variante war bloss als Beispiel für eine komplett bescheuerte Schreibweise gedacht. Wenn es wichtig ist sagt es, vielleicht fällt mit ja noch was bekloppteres ein.

Und ja, da muss dann natürlich foo() - 1 hin.

cooky451

Mechanics schrieb:

Nein, siehe Antwort von knivil. Ich bin sogar ziemlich skeptisch, ob er das bei so vielen Funktionen tatsächlich erkennen kann.

Und ich bin mir ziemlich sicher, dass VS, GCC und der Intel Compiler das bei allen Funktionen packen die geinlined werden.

Mechanics schrieb:

obskuren Tricks

Hättest du die letzten 4 Seiten gelesen, sollte dir klar sein, dass ich das eben nicht als obskuren Trick ansehe. std::tuple, std::function und std::make_shared sind obskure Tricks, aber doch nicht "i-- != 0".

hustbaer

Liebes Keks,
DU empfindest es vielleicht nicht als obskure Tricks.
Andere schon.
Ist eben alles Ansichtssache.

Und bei Kritik im Sinne von "das versteht ja keiner" einfach immer sagen "pf, ich versteh das super" ist irgendwie nicht sinnvoll.

hustbaer

cooky451 schrieb:

Mechanics schrieb:

Nein, siehe Antwort von knivil. Ich bin sogar ziemlich skeptisch, ob er das bei so vielen Funktionen tatsächlich erkennen kann.

Und ich bin mir ziemlich sicher, dass VS, GCC und der Intel Compiler das bei allen Funktionen packen die geinlined werden.

Mhm, ja, täusch dich mal nicht.

krümelkacker

knivil schrieb:

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.

Jo, stimmt. Da habe ich mich echt vertan. Ich finde ~i irgendwie weniger lesbar als das i-->0 in anderen Schleifen.

knivil schrieb:

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?

Ist das dein Ernst? Tja, so kann's gehen. for(;;) ist wohl doch zu mächtig und wenig lesbar, wenn ich mir diese Tricks i-->0 bzw ~i zum Umgehen des Unterlaufproblems anschaue ...

Kann mir vorstellen, dass for-range bald so oder so ähnlich genutzt wird:

for (auto i : reversed(range(0,foo()))) {

}

oder in Boost.Range Pipe-Syntax:

for (auto i : range(0,foo()) | reverse) {

}

hustbaer

Das schreit nach einer Spracherweiterung...

for (auto i ~: dings)

Mechanics

cooky451 schrieb:

Hättest du die letzten 4 Seiten gelesen, sollte dir klar sein, dass ich das eben nicht als obskuren Trick ansehe.

Ich hab alles gelesen und ich weiß, dass du das nicht als obskuren Trick ansiehst. So obskur find ich das jetzt auch nicht mal, die Aussage war nicht ausschließlich darauf bezogen. Aber es ist eben obskur genug. Ich kann mich nur wiederholen, je einfacher und dümmer der Code ist, desto besser ist es meist. Alles was nicht absolut straight forward ist, ist nur eine zusätzliche Stör- und Fehlerquelle.