Geschwindigkeitsfrage

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.

dot

volkard schrieb:

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

Afaik gibts seit der Core-Architektur wieder eine sehr viel seichtere Pipeline, was einen Stall in der Tat billiger macht.