Geschwindigkeitsfrage

knivil

volkard schrieb:

knivil schrieb:

Nein.

Ach kommt, jetzt wirds's kindisch. Wie haben oft genug bei diversen Implementierungen des Siebes des Eratosthenes hier im Forum gesehen, daß es ein paar Prozent Geschwindigkeitsbonus ergibt.

Ich kann mich an das nicht erinnern. Es ist auch etwas seltsam, dass 'aus dem Speicher/Cache holen, pruefen (mit jump, 50%) und Wert setzen' schneller sein soll als 'Wert setzen'.

SeppJ

knivil schrieb:

Ich kann mich an das nicht erinnern. Es ist auch etwas seltsam, dass 'aus dem Speicher/Cache holen, pruefen (mit jump, 50%) und Wert setzen' schneller sein soll als 'Wert setzen'.

Aber zumindest jetzt hast du einen Präzedenzfall. Der GCC liefert übrigens ein vergleichbares Ergebnis, was aber auch kein Wunder ist, da das vor allem an der Maschine selbst liegen sollte. Wenn jemand etwas moderneres oder weniger moderneres als den (für einen i7) schon etwas angestaubten i7 920 an dem ich gerade sitze hat: Immer her damit.

hustbaer

Hier werden riesen Mengen Speicher getestet/geschrieben, klar kann das dann was ausmachen.
Wenn er eine Cache-Line nur "shared" braucht, dann ist das billiger, als wenn er sie "exclusive" braucht.

Im Beispiel des OP ist "isValid" dagegen eine einfache einzelne Variable, statt eine von Millionen.
D.h. es wird - meine Einschätzung - nix bringen, sondern im Gegenteil sogar schaden.

cooky451

Das hat mich so gewundert, dass ich es mal getestet habe:

struct A
{
  bool i;
  void trueify()
  {
    if (!i)
    i = true;
  }
  void foo()
  {
    unsigned j;
    std::cin >> j; // 50000 ist ein guter Wert
    j *= j;
    auto t = std::clock();
    while (j--)
    {
      i = j % 2;
      trueify();
    }
    double elapsed = (std::clock() - t) / static_cast<double>(CLOCKS_PER_SEC);
    std::cout << i << "  Time: " << elapsed;
  }
};

Bei mir ist die Variante ohne if 3-4 mal schneller. Was mache ich falsch? (MSVC 10)

Mit if:

while (j--)
003816A6  mov         eax,dword ptr [esp+38h]  
003816AA  test        eax,eax  
003816AC  je          A::foo+41h (3816C1h)  
003816AE  mov         edi,edi  
003816B0  dec         eax  
    {
      i = j % 2;
003816B1  mov         cl,al  
003816B3  and         cl,1  
003816B6  mov         byte ptr [esi],cl  
      trueify();
003816B8  jne         A::foo+3Dh (3816BDh)  
003816BA  mov         byte ptr [esi],1  
    while (j--)
003816BD  test        eax,eax  
003816BF  jne         A::foo+30h (3816B0h)  
003816C1  dec         eax  
003816C2  mov         dword ptr [esp+38h],eax  
    }

Ohne if:

while (j--)
001B16A6  mov         eax,dword ptr [esp+38h]  
001B16AA  test        eax,eax  
001B16AC  je          A::foo+37h (1B16B7h)  
001B16AE  mov         cl,byte ptr [esi]  
001B16B0  dec         eax  
    {
      i = j % 2;
      trueify();
001B16B1  mov         cl,1  
001B16B3  jne         A::foo+30h (1B16B0h)  
001B16B5  mov         byte ptr [esi],cl  
    while (j--)
001B16B7  dec         eax  
001B16B8  mov         dword ptr [esp+38h],eax  
    }

SeppJ

Irgendwie kann's mit der Optimierfähigkeit (oder eher den Einstellungen die du gewählt hast?) deines Compilers nicht weit her sein, GCC kann das vollständig wegoptimieren:

call	clock
	movl	$-1, 8(%rsp)
	movq	%rax, %rbp
	call	clock

cooky451

SeppJ schrieb:

Irgendwie kann's mit der Optimierfähigkeit

Na ja, ich habe halt die Ausgabe genommen, die am einfachsten war - und es hat gleich geklappt. Ich habe jedenfalls alle Optimierungen an und alle auf Geschwindigkeit gestellt.
Sollte für die eigentliche Zeitmessung ja auch egal sein, nur doof dass das jetzt nur Leute mit dem hier schlechteren MSVC testen können.

SeppJ

cooky451 schrieb:

SeppJ schrieb:

Irgendwie kann's mit der Optimierfähigkeit

Na ja, ich habe halt die Ausgabe genommen, die am einfachsten war - und es hat gleich geklappt. Ich habe jedenfalls alle Optimierungen an und alle auf Geschwindigkeit gestellt.
Sollte für die eigentliche Zeitmessung ja auch egal sein, nur doof dass das jetzt nur Leute mit dem hier schlechteren MSVC testen können.

Es bleibt jedenfalls festzustellen, dass der Unterschied zwischen den beiden Assemblerausgaben mehr ist als nur das if(!i) . Und das wird das Ergebnis kaputt machen. Wir müssen also feststellen: Das Ergebnis passt erst, wenn der Compiler es nicht wieder kaputt macht. Irgendwie scheint dem MSVC das if die Optimierung kaputt zu machen. Beim GCC übrigens auch, die totale Wegoptimierung schafft er erst beim Fall ohne if.

edit: Ein bisschen viel "kaputt". Das kommt davon, wenn man einzelne Sätze mit ein paar Minuten Pause dazwischen schreibt. Aber ich gehe jetzt nicht nochmal mit dem Thesaurus drüber, mein ehemaliger Deutschlehrer liest hier bestimmt nicht mit :p .

SeppJ schrieb:

Intel-Compiler, O3, SSE4.2, laufen gelassen auf i7 mit virtuellen Kernen deaktiviert, je 6 Läufe. Bestzeit ohne Prüfung: 18.57 s. Bestzeit mit Prüfung 18.02 s.

GCC-4.6.2, -O2, march=corei7-avx, i7 mit HT (wollte jetzt nicht extra neu booten). Durchschnitt ohne Prüfung: 16,46, mit Prüfung: 15,25. Ein Plus von ca. 8%! O3 wurde nicht mehr schneller.

SeppJ

minime schrieb:

i7 mit HT (wollte jetzt nicht extra neu booten)

Du kannst Kerne im Betrieb ausschalten (Bei GCC nehm ich einfach mal an, dass du Linux benutzt). Dazu musst du in die /sys/devices/system/cpu/cpuX/online entweder 0 oder 1 schreiben. Beim i7 kannst du so die Kerne 4, 5, 6, und 7 ausschalten und hast (zumindest effektiv) kein HT mehr .
Ein kurzes Skript zum Ausschalten:

#!/bin/bash
echo 0 | sudo tee /sys/devices/system/cpu/cpu7/online
echo 0 | sudo tee /sys/devices/system/cpu/cpu6/online
echo 0 | sudo tee /sys/devices/system/cpu/cpu5/online
echo 0 | sudo tee /sys/devices/system/cpu/cpu4/online

Und wieder an:

#!/bin/bash
echo 1 | sudo tee /sys/devices/system/cpu/cpu7/online
echo 1 | sudo tee /sys/devices/system/cpu/cpu6/online
echo 1 | sudo tee /sys/devices/system/cpu/cpu5/online
echo 1 | sudo tee /sys/devices/system/cpu/cpu4/online

Du brauchst auch keine Angst haben, dass du dadurch irgendwelche Programme abschuießt, so doof ist der Scheduler nicht .

volkard

minime schrieb:

Ein Plus von ca. 8%! O3 wurde nicht mehr schneller.

Wobei ich den Code mit if häßlicher finde. Ich würde ihn beim Primzahlensieb schreiben, weil er da nicht stört und doch meßbar was bringt. Bei so einem Invalidate() dürften es so wenige Aufrufe sein im Vergleich zum Rest des Programms; sagen wir mal einmal Invalidate 1000-mal seltener (und das wäre noch enorm oft!), dann hätten wir wohl auch nur ca 8%/1000 nur noch als Gewinn, also quasi nichts.
Daß es enorm wenig bringen wird, hat der Threadersteller ja schon eingeräumt. Er wollte nur wissen, ob es überhaupt was bringt. Und da ist die richtige Antwort ein klares vielleicht. Aber:

Ich gehe auch mit hustbaer d'accord, daß es bei selteten Aufrufen vielleicht sogar langsamer wird. Dann aber halt auch mit ca 8%/1000(=quasi nichts). Defensive Programmierung (in Bezug auf die Performance) wäre also derzeit, Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen. Schaden kanns ja nicht, aber falls jemand Invalidate gar oft aufruft (für eine Prograss-Bar in einer zweitinnersten Schleife, wobei die innerste Schleife kaum abzuschätzende Laufzeiten hat), bringt es was.

Und wenn die Prozessorbauer nachgerüstet haben und dieses if in die Hardware reinlöten oder die Compilerbauer die Optimierung einbauen, kann es wieder weg.

Wobei ich bei kommerzieller Software sowas eher nicht einbaue, sondern davon ausgehe, daß die nächste Compilerversion es schon richten wird. Bei MS die übernächste, auch egal. Für Auftraggeber schreibe ich defensiv (in Bezug auf die eventuellen Schlafnasen, die meinen Code mal warten dürfen).

SeppJ

volkard schrieb:

Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen.

Weil der nächste logische Schritt dann ein vector<bool> gewesen wäre und dann eine Referenz auf ein vector<bool>-Element da gestanden hätte.

volkard

SeppJ schrieb:

volkard schrieb:

Seppjs Funktion inline void trueify(int &number) (warum nicht bool?) zu haben und gelegentlich zu benutzen.

Weil der nächste logische Schritt dann ein vector<bool> gewesen wäre und dann eine Referenz auf ein vector<bool>-Element da gestanden hätte.

Autsch! Ja. vector<bool> wäre hier schmerzhaft.

GorbGorb

Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.

Hier noch der code:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>

const unsigned int array_size = 100000000;

int main()
{
	std::vector< unsigned int > a( array_size );
	std::vector< unsigned int > b( array_size );

	auto it_a = a.begin();
	auto it_b = b.begin();
	while( it_a != a.end() )
	{
		unsigned int value = std::rand() % 2;
		*it_a = value;
		*it_b = value;
		//*it_a = 1;
		//*it_b = 1;
		++it_a;
		++it_b;
	}

	unsigned int t;

	t = std::clock();
	it_a = a.begin();
	while( it_a != a.end() )
	{
		if( (*it_a) )
			*it_a = false;
		++it_a;
	}
	std::cout<< std::clock() - t << std::endl;

	t = std::clock();
	it_b = b.begin();
	while( it_b != b.end() )
	{
		*it_b = false;
		++it_b;
	}
	std::cout << std::clock() - t << std::endl;

	std::cin.get();
}

volkard

GorbGorb schrieb:

Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.

Ah, also ist if erst schneller, wenn die Verzweigungsvorhersage oft genug trifft. Im Anwendungsfall, wenn man oft Invalidate() aufruft, obwohl das Objakt schon invalid war. Oder Invalidate() immer nur, wenn es nicht invalid war.

Bei den Primzahlen: Die Zahlen sind eh vermutlich zusammengesetzt. Meistens werden nur zusammengesetzte Zahlen nochmal überbestätigt.

SeppJ

volkard schrieb:

GorbGorb schrieb:

Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.

Ah, also ist if erst schneller, wenn die Verzweigungsvorhersage oft genug trifft.

Nicht voreilig sein! Der Code von GorbGorb macht zwei ganz verschiedene Dinge. Wenn ich den Assembleroutput recht interpretiere wird das nämlich im zweiten Fall zu einer Art memset optimiert.

Womit auch die Frage von GorbGorb beantwortet wäre: Wir setzen das vorher auf 0, weil unser Algortihmus etwas sinnvolles tut. Bei diesen ganzen Trivialbeispielen rennt man sonst viel zu schnell in die Falle, dass der Compiler zu clever ist, wie dein Code eindrucksvoll zeigt.

GorbGorb

Mit welchem compiler hast du das denn getestet (ich kann kein assembler, wollt ich irgendwann mal lernen, aber irgendwie...)?
Wenn ich am Anfang alles auf 1 oder 0 gesetzt hatte, hat die if-Version etwa 10% länger gebraucht (memset?), bei zufälligen Werten waren es ungefähr 600%.

volkard

SeppJ schrieb:

volkard schrieb:

GorbGorb schrieb:

Ist das Absicht, dass ihr euren bools immer den gleichen Wert gegeben habt? Wenn ich am Anfang den bools zufällige Werte zuweise, braucht bei mir die Version mit if 6x länger.
Auch wenn ich zu Beginn allen bools den gleichen Wert zuweise ist bei mir übrigens die if - Version schlechter. Ich vermute mal bei meinem Core i5 M520 ist das if einfach teurer als Speicherzugriff.

Ah, also ist if erst schneller, wenn die Verzweigungsvorhersage oft genug trifft.

Nicht voreilig sein! Der Code von GorbGorb macht zwei ganz verschiedene Dinge. Wenn ich den Assembleroutput recht interpretiere wird das nämlich im zweiten Fall zu einer Art memset optimiert.

Womit auch die Frage von GorbGorb beantwortet wäre: Wir setzen das vorher auf 0, weil unser Algortihmus etwas sinnvolles tut. Bei diesen ganzen Trivialbeispielen rennt man sonst viel zu schnell in die Falle, dass der Compiler zu clever ist, wie dein Code eindrucksvoll zeigt.

Danke.
Ich hatte mir bisher eingebildet: Ja, damals auf dem Pentium oder so kostete ein Sprung mit gelungener Vorhersage einen Takt und ein falscher Sprung dreizehn Straftakte dazu. Und ich hatte den Eindruck, daß die Prozessorbauer inzwischen dagegen was gelötet haben. Daß beide Richtungen parallel einigermaßen weit verfolgt werden und die Doof-Richtung dann halt verworfen wird. Wäre teuer, würde wieder Millionen von Transitoren kosten. Aber ich hatte den Eindruck, daß falsche Vorhersagen nicht mehr ganz so teuer sind.

Vielleicht ist mein Eindruck noch korrekt. Weiß da jemand moderne Daten?

SeppJ

GorbGorb schrieb:

Mit welchem compiler hast du das denn getestet (ich kann kein assembler, wollt ich irgendwann mal lernen, aber irgendwie...)?
Wenn ich am Anfang alles auf 1 oder 0 gesetzt hatte, hat die if-Version etwa 10% länger gebraucht (memset?), bei zufälligen Werten waren es ungefähr 600%.

GCC 4.4 mit O3 und SSE4.2. Ich habe jetzt aber nicht alle Möglichkeiten durchgespielt.
Vielleicht kann bei den Fällen ohne Zufall vom Compiler beim Code mit der if-Abfrage ebenfalls bewiesen werden, dass die Aktion äquivalent zu einem memset ist.

Man kann jedenfalls auch mal festhalten, dass das if eine ziemliche Optimierungssperre ist, wie man auch an cooky451s Code gesehen hat (wo der GCC einen Fall komplett wegoptimiert hat und der MSVC beim Fal mit if schlechter optimiert hat. Man sollte also schon Code vorliegen haben, den ein guter Programmierer ansonsten nicht mehr optimieren kann (GorbGorbs Code ist dafür ein gutes Beispiel, da es einfach ein umständliches memset ist, was der COmpiler einmal erkennen kann, einmal nicht), bevor man diese Mikrooptimierung versucht.

hustbaer

@volkard
Genaue Daten weiss ich keine.
Aber der Prescott war IIRC am schlimmsten, und mit Core2 wurde es viel viel besser.
Ob es bei den "is" nochmal verbesser wurde weiss ich nicht.

Die Frage hätte man schon von Anfang an klar beantworten können.