Was ist theoretisch flotter?

DocShoe

volkard schrieb:

DocShoe schrieb:

Ähnlicher Thread, gleiches Thema...
Don´t optimize prematurely!

Der Spruch ist abgedroschen.

Aber immer noch wahr. Selbst dir dürfte aufgefallen sein, dass es hier um ein mikroskopisch kleinen Ausschnitt des Gesamtproblems geht, und ich behaupte immer noch, dass dieser Schnipsel wenig Relevanz für die Gesamtlaufzeit hat.

Bashar schrieb:

DocShoe: Dein Test dürfte völlig wertlos sein, weil du nicht weißt, wie der generierte Maschinencode aussieht und was da drin optimiert wurde.

Richtig. Zu meiner Schande muss ich gestehen, dass ich mich mit x86 Assembler nie auseinandergesetzt habe. Interessiert mich, ehrlich gesagt, auch nicht, weil ich mit dem Ergebnis meines Compilers leben muss, weil ich es manuell in ASM nicht selbst programmieren könnte.

volkard schrieb:

Hihi.
Und zwar ist die
for( unsigned int o = 0; o < 1e9; ++o )
dran schuld! Wer schreibt denn auch sowas?? Vermutlich hat DocShoe zu selten einfach mal aus Spaß optimiert.

1e9 ist bei meinem Compiler das gleiche wie 1000*1000*1000. Was kommt bei dir raus?

volkard schrieb:

Ich messe seine Schleife

UInt32 test2(){
   for( unsigned int o = 0; o < 1e9; ++o )
   {
      for( unsigned int i = 0; i < 64; ++i )
      {
         unsigned int row = i >> 3;
         unsigned int col = i % 8;
      }
   }
   return 28000000;
}

6542334167 cycles
und jetzt die reparierte Schleife

UInt32 test2(){
   for( unsigned int o = 0; o < 1000*1000*1000; ++o )
   {
      for( unsigned int i = 0; i < 64; ++i )
      {
         unsigned int row = i >> 3;
         unsigned int col = i % 8;
      }
   }
   return 28000000;
}

5 cycles

Welchen Compiler benutzt du? Ich habe deinen Test durch meinen Compiler laufen lassen (Codegear RAD Studio 2010), und komme auf fast identische Ergebnisse wie bei meiner ursprünglichen Messung. Die tatsächliche Laufzeit hängt also vom benutzen Compiler und dessen Optimierungsfähigkeiten ab. Ein weiterer Grund, das Laufzeitverhalten zu testen statt auf dem Papier zu überlegen, welcher Code besser oder schlechter ist. Zur Zeitmessung benutze ich die Win32 API Funktionen QueryPerformanceCounter und QueryPerformanceFrequency.

volkard schrieb:

Falsch. Erstens braucht man keinen Profiler, wenn man sowas mal wissen mag, ein einfaches Meßprogramm reicht.

Falsch. Mit deiner Messmethode kannst du lediglich die Laufzeit einer Funktion messen, bestenfalls die akkumulierte Laufzeit, aber nicht, welche Funktion wieviel CPU Zeit zur Lösung des Gesamtproblems benötigt. Das geht nur mit einem Profiler. Oder du bastelst dir irgendwas, was die Laufzeiten der einzelnen Funktionen aufsummiert, was dann eigentlich ein Profiler ist.
Ich gebe dir Recht, wenn du deine Aussage auf die Zeitmessung einer einzelnen Funktion beziehst, dafür braucht man keinen Profiler.
Man sollte eine lauffähige Version durch einen Profiler analysieren lassen und dann an den Engpässen arbeiten, statt sich im Vorfeld Gedanken über irgendwelche winzigen Optimierungen zu machen. Etwaige faux-pas wie call-by-value oder Benutzung von unnötigen temporaries schliesse ich einfach mal aus. Hoffentlich kommt jetzt niemand auf die Idee, den letzten Satz auf meine Messmethode anzuwenden

Ich finde es gut, sich jeden Schritt genau zu überlegen und zu schauen, dass man von Anfang an optimiert, wo es nur geht. So entwickelt man wirklich professionelle Software!
Im Nachhinein optimieren könnte Probleme geben, oft muss dann mehr umgeschrieben werden, als einem lieb ist.
Außerdem wird man dann vielleicht schnell faul &| übersieht Dinge.

Tomahawk

volkard schrieb:

DocShoe schrieb:

Ähnlicher Thread, gleiches Thema...
Don´t optimize prematurely!

Der Spruch ist abgedroschen.

DocShoe schrieb:

Ich habe mal einen Testlauf mit 1 Milliarde Iterationen gemacht:
Ergebnisse (Release Build auf nem 3.0 MHz Intel DualCore)
f1() : 1.29381E11 Cycles (43.1582 sec)
f2() : 1.29345E11 Cycles (43.1464 sec)

Keine Ahnung, wie Du das gemessen hast.

Ich hab mal
int file[64]={
	0,0,0,0,0,0,0,0,8,8,8,8,8,8,8,8,
	16,16,16,16,16,16,16,16,24,24,24,24,24,24,24,24,
	32,32,32,32,32,32,32,32,40,40,40,40,40,40,40,40,
	48,48,48,48,48,48,48,48,56,56,56,56,56,56,56,56,
};
inline int get_file(const int square) {
  return file[square%64];
//  return (square%64)&56;
}
UInt32 test2(){
	UInt32 sum=0;
	for(int i=0;i<1000000;++i)
		sum+=get_file(i);
	return sum;
}
gemessen.

Array-Version: 3014773 cycles
Bit-Version: 2014571 cycles

DocShoe schrieb:

Aus praktischer Sicht identisch, also nimm die einfacherere Lösung. Ohne Profiler zu optimieren ist Käse, du schraubst mit Sicherheit an der falschen Stelle!

Falsch. Erstens braucht man keinen Profiler, wenn man sowas mal wissen mag, ein einfaches Meßprogramm reicht. Außerdem muß man sowas erkunden dürfen, ohne immer die premature Ohrfeige zu bekommen.

Hallo!
Eine nervige Bitte habe ich noch, könntest du mir den kompletten Testaufbau geben, da ich leider nicht weiss, wie ich cycles messen kann!
Wäre echt super, danke!!!!

Tomahawk

DocShoe

Erkenner schrieb:

Ich finde es gut, sich jeden Schritt genau zu überlegen und zu schauen, dass man von Anfang an optimiert, wo es nur geht. So entwickelt man wirklich professionelle Software!
Im Nachhinein optimieren könnte Probleme geben, oft muss dann mehr umgeschrieben werden, als einem lieb ist.
Außerdem wird man dann vielleicht schnell faul &| übersieht Dinge.

Jein. Auf der einen Seite sollte man sich schon ein gutes Design überlegen und vernünftigen Code schreiben, aber nur bis zu einem gewissen Grad. An dem Punkt, wo man von seinem üblichen Programmierstil abweicht um etwas zu optimieren muss diese Abweichung gerechtfertigt sein. Zum Beispiel die Auswahl des richtigen Containers und des richtigen Algorithmus setze ich einfach voraus, ohne das jetzt Optimierung zu nennen.
Vielleicht reden wir hier auch alle ein wenig aneinander vorbei...

Tomahawk

QueryPerformanceCounter
QueryPerformanceFrequency

Wie setzte ich diese Funktionen ein, werde aus der MSDN Beschreibung nicht schlau...

[Bitte, wenn möglich, vollständigen Code eines Messbeispiels posten, thx]

Tomahawk

LARGE_INTEGER start_ticks, ende_ticks, frequenz; 

double tick_diff     = 0; 
start_ticks.QuadPart = 0; 
ende_ticks.QuadPart  = 0; 

QueryPerformanceCounter(&start_ticks); 
QueryPerformanceFrequency(&frequenz); 

// ... hier irgendwas machen ... 

QueryPerformanceCounter(&ende_ticks); 

// benötigte zeit berechnen 
tick_diff = ((double) ende_ticks.QuadPart - (double) start_ticks.QuadPart) / frequenz.QuadPart;

Habe ich gefunden, ok so?

DocShoe

#include <vcl.h>
#pragma hdrstop

#include <tchar.h>

#include <iostream>

#pragma argsused

unsigned int ROWS[] = {
	0, 0, 0, 0, 0, 0, 0, 0,
	1, 1, 1, 1, 1, 1, 1, 1,
	2, 2, 2, 2, 2, 2, 2, 2,
	3, 3, 3, 3, 3, 3, 3, 3,
	4, 4, 4, 4, 4, 4, 4, 4,
	5, 5, 5, 5, 5, 5, 5, 5,
	6, 6, 6, 6, 6, 6, 6, 6,
	7, 7, 7, 7, 7, 7, 7, 7
};

unsigned int COLS[] = {
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7,
	0, 1, 2, 3, 4, 5, 6, 7
};

using namespace std;

unsigned int f1()
{
	for( unsigned int o = 0; o < 1e9; ++o )
	{
		for( unsigned int i = 0; i < 64; ++i )
		{
			unsigned int row = i / 8;
			unsigned int col = i & 7;
		}
	}
	return 28000;
}

unsigned int f2()
{
	for( unsigned int o = 0; o < 1e9; ++o )
	{
		for( unsigned int i = 0; i < 64; ++i )
		{
			unsigned int row = ROWS[i];
			unsigned int col = COLS[i];
		}
	}
	return 28000;
}

void print_timings( const LARGE_INTEGER& start, const LARGE_INTEGER& stop )
{
	LARGE_INTEGER F;
	::QueryPerformanceFrequency( &F );

	double Cycles = static_cast<double>( stop.QuadPart - start.QuadPart );
	double Time   = Cycles / static_cast<double>( F.QuadPart );

	cout << Cycles << " clock cycles (" << Time << "s)" << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	LARGE_INTEGER S, T;
	cout << "Running f1()" << endl;
	::QueryPerformanceCounter( &S );
	f1();
	::QueryPerformanceCounter( &T );
	print_timings( S,T );

	cout << "Running f2()" << endl;
	::QueryPerformanceCounter( &S );
	f2();
	::QueryPerformanceCounter( &T );
	print_timings( S,T );

	return 0;
};

Du wirst den Code an deinen Compiler anpassen müssen, deiner wird die vcl.h nicht kennen, int main() als Einsprungspunkt haben und auch mit den #pragma wenig anfangen können.
Seltsamerweise liefert ein Test für f1() 43.1762sec und für f2() 64.6362sec. o.O

Tomahawk

@DocShoe

Danke für den Code!

Bashar

DocShoe schrieb:

Bashar schrieb:

DocShoe: Dein Test dürfte völlig wertlos sein, weil du nicht weißt, wie der generierte Maschinencode aussieht und was da drin optimiert wurde.

Richtig. Zu meiner Schande muss ich gestehen, dass ich mich mit x86 Assembler nie auseinandergesetzt habe. Interessiert mich, ehrlich gesagt, auch nicht, weil ich mit dem Ergebnis meines Compilers leben muss, weil ich es manuell in ASM nicht selbst programmieren könnte.

So meinte ich das nicht. Du musst nicht Assembler programmieren können, du musst es nichtmal lesen können (meine Assemblerkenntnisse sind auch vorsintflutlich). Aber was genau testet dein Test? Sind es wirklich die Anweisungen im Schleifenkörper?
Das ist hier zu bezweifeln, weil die Variablen col und row danach nicht mehr benutzt werden. Das kann ein Compiler sehr gut aufräumen.
Die Frage ist nur, warum er nicht die ganze Schleife wegwirft.

volkard schrieb:
Hihi.
Und zwar ist die
for( unsigned int o = 0; o < 1e9; ++o )
dran schuld! Wer schreibt denn auch sowas?? Vermutlich hat DocShoe zu selten einfach mal aus Spaß optimiert.
1e9 ist bei meinem Compiler das gleiche wie 1000*1000*1000. Was kommt bei dir raus?

1e9 ist zunächst mal ein floating-point-Literal. Das kann gut sein, dass sich ein Compiler bei der Optimierung nicht traut, floating-point-Geschichten vorher auszurechnen. Er macht also in jedem Schleifendurchlauf wieder den Vergleich mit 1e9 ... könnte ja sein, dass das irgendwelche Fehlerflags in der FPU setzt oder was weiß ich
Bei einem Integer-Vergleich mit 1000*1000*1000 (was er direkt zu 1000000000 falten kann) weiß er aber genau, was passiert.

DocShoe

Tomahawk schrieb:

@DocShoe

Danke für den Code!

Hehe, dafür doch nicht.

volkard

DocShoe schrieb:

Welchen Compiler benutzt du?

gcc 4.4.0 mingw

Zur Zeitmessung benutze ich die Win32 API Funktionen QueryPerformanceCounter und QueryPerformanceFrequency.

Ich benutze rdtsc und nehme das Minimum von mindestens 1000 Durchläufen. Damit sind normalerweise Cache-Effekte und die anderen Prozesse, Festplatte und so aus der Messung raus.

Man sollte eine lauffähige Version durch einen Profiler analysieren lassen und dann an den Engpässen arbeiten, statt sich im Vorfeld Gedanken über irgendwelche winzigen Optimierungen zu machen. Etwaige faux-pas wie call-by-value oder Benutzung von unnötigen temporaries schliesse ich einfach mal aus. Hoffentlich kommt jetzt niemand auf die Idee, den letzten Satz auf meine Messmethode anzuwenden

Man muß sich auch im Vorfeld Gedanken machen und die Performance muß im gesamten Entwicklungsprozess im Hinterkopf mitgetragen werden. Anderernfalls kommen diese typischen Anwendungen raus, die erst lahm entwickelt werden, später nachoptimiert und dabei dermaßen verfrickelt, daß kein Mensch mehr durchblickt.

volkard

Tomahawk schrieb:

Eine nervige Bitte habe ich noch, könntest du mir den kompletten Testaufbau geben, da ich leider nicht weiss, wie ich cycles messen kann!

Der komplette ist ein wenig groß. Kannste auch haben, aber da sind auch andere Sachen drin, ich benutze dort die Standardbibliothek außer für syscalls und new nicht mehr.
Aber ich versuche mal, das Relevate zusammenzukopieren.

typedef unsigned long long UInt64;
typedef unsigned int UInt32;

//GCC
UInt64 rdtsc() {
   UInt64 result;
   asm volatile(
   	"rdtsc":
   	"=A"(result)
   );
   return result;
}

//MS (geraten, nicht getestet)
UInt64 rdtsc() {
   __asm rdtsc;
}

//linux
#include <unistd.h>
#include <sys/resource.h>
inline void lockProcessToProcessor(){
	cpu_set_t mask;
	CPU_ZERO( &mask );
	CPU_SET( 1, &mask );
	sched_setaffinity( 0, sizeof(mask), &mask );
	sleep(1);
}

//windows
#include <windows.h>
inline void lockProcessToProcessor(){
	SetProcessAffinityMask(GetCurrentProcess(),1);
	Sleep(1);
}

template<typename F>
UInt64 measure(F f,UInt32 goodResult,UInt32 initCount=1000){
	os::lockProcessToProcessor();
	UInt64 minTime=UInt64(-1);
	int count=initCount;
	while(count--){
		UInt64 elapsed=-rdtsc();
		UInt32 result=f();
		elapsed+=rdtsc();
		if(result!=goodResult){
			cout<<"error: result="<<result<<" expected="<<goodResult<<'\n';
			return UInt64(-1);
		}
		if(elapsed<minTime){
			minTime=elapsed;
			count=initCount;
			cout<<minTime<<" cycles\n";
		}
	}
	return minTime;
}

int file[64]={
	0,0,0,0,0,0,0,0,8,8,8,8,8,8,8,8,
	16,16,16,16,16,16,16,16,24,24,24,24,24,24,24,24,
	32,32,32,32,32,32,32,32,40,40,40,40,40,40,40,40,
	48,48,48,48,48,48,48,48,56,56,56,56,56,56,56,56,
};

inline int get_file(const int square) {
//  return file[square%64];
  return (square%64)&56;
}

UInt32 test2(){
	UInt32 sum=0;
	for(int i=0;i<1000000;++i)
		sum+=get_file(i);
	return sum;
}

int main(){
	measure(&test2,28000000);

volkard

DocShoe schrieb:

Seltsamerweise liefert ein Test für f1() 43.1762sec und für f2() 64.6362sec. o.O

Noch berechnet Dein Test nichts und es ist unabschätzbar, was wegoptimiert wird. Außerdem berechet er nicht mit zwei unterschiedlichen Methoden dasselbe, weshalb ich auch mit dem Test unzufrieden bin.

DocShoe

@Bashar
Deswegen predige ich ja schon seit Threadstart, ein Performanceprofil über die gesamte Applikation zu erstellen. Einzelne Funktionen isoliert zu betrachten macht keinen Sinn, da man nicht sagen kann, wie hoch ihr Gesamtbeitrag ist.

@volkard
Vielleicht haben wir unterschiedliche Vorstellungen von dem Begriff "optimieren". Ich halte die Benutzung von Bitshift Operatoren für selbstverständlich, allerdings muss die Notwendigkeit von Lookup Tabellen, etc. erst einmal belegt werden. Software (eigentlich deren Quellcode) muss wartbar bleiben (übrigens auch ein Merkmal professioneller Software, nicht nur Geschwindigkeit), und wenn die Implementation deutlich komplexer als die Standardlösung wird muss es einen triftigen Grund dafür geben. Wo man die Messlatte ansetzt muss von Fall zu Fall entschieden werden, aber ein Performancezuwachs in der zweiten Nachkommastelle sind sicher keine Rechtfertigung. Und genau das versuche ich doch die ganze Zeit zu erklären: Man muss zunächst einmal sicherstellen, dass die Optimierungen, die man vornimmt, tatsächlich messbare Ergebnisse vorweist.

Ich glaube, ich habe meine Punkte deutlich genug gemacht, bin jetzt raus aus diesem Thread.

volkard

DocShoe schrieb:

wenn die Implementation deutlich komplexer als die Standardlösung wird muss es einen triftigen Grund dafür geben.

DocShoe schrieb:

Man muss zunächst einmal sicherstellen, dass die Optimierungen, die man vornimmt, tatsächlich messbare Ergebnisse vorweist.

In einem privat erstellen Schachprogramm darf man sehr vieles und muß nur sehr wenig, fürchte ich. Außerdem wird das Schachprogramm sehr viel seiner Spielstärke aus der rohen Rechenleistung ziehen und es wird immer immer weiter auf Performance optimiert werden, da ist es keine völlig absurde Idee, bereits frühzeitig ein wenig mehr in die Details zu gehen als bei einem XML-Parser.

Ich halte es jetzt so, daß ich nach Möglichkeit gleich mehrere Alternativen im Code anbiete und nicht überlege, welche die schnellste ist. Ich kann ja am Ende Code-Schalter umlegen und die Alternativen wechseln. Geht natürlich nur für kleine Sachen wie get_file(), für die austauschbare Implementierungen möglich sind.

Bashar

DocShoe schrieb:

@Bashar
Deswegen predige ich ja schon seit Threadstart, ein Performanceprofil über die gesamte Applikation zu erstellen. Einzelne Funktionen isoliert zu betrachten macht keinen Sinn, da man nicht sagen kann, wie hoch ihr Gesamtbeitrag ist.

Das ist ja alles gut und richtig, hat aber überhaupt nichts mit dem zu tun, was ich geschrieben habe. Aber da du eh raus bist, brauch ich dazu wohl nichts mehr zu sagen.

volkard

DocShoe schrieb:

1e9 ist bei meinem Compiler das gleiche wie 1000*1000*1000. Was kommt bei dir raus?

int main(){
	cout<<sizeof(1000*1000*1000)<<'\n';
	cout<<sizeof(1e9)<<'\n';
	return 0;
}

Ausgabe:
4
8

Und

#include <iostream>
using namespace std;

int main(){
	for(int i=0;i<1e9;++i)
		;
	return 0;
}

Laufzeit: 2s

#include <iostream>
using namespace std;

int main(){
	for(int i=0;i<1e10;++i)
		;
	return 0;
}

Laufzeit... ähm, er läuft noch. Länger als 20s. Vieeel länger.

Bashar

Volkard, was wolltest du denn mit dem letzten Beispiel aussagen?

unskilled

Bashar schrieb:

Volkard, was wolltest du denn mit dem letzten Beispiel aussagen?

das du wenn du ints einsetzt ne laufzeit von vll 4 cycles hast, weil der compiler sich dann getraut, die schleife (fast?) vollkommen zu optimieren... imho muss er nur noch den wert von ecx setzen, falls er das für nötig hält - hier wird er aber vrmtl drauf verzichten^^

bb

volkard

Bashar schrieb:

Volkard, was wolltest du denn mit dem letzten Beispiel aussagen?

naja, die Laufzeit gehört hier ausnahmsweise mal zum beobachtbaren Verhalten, da ich keine Cray habe.