Was ist theoretisch flotter?

Tomahawk

Bei mir sind viele Informationen in 1-dimensionalen Arrays gespeichert. Aber diese Informationen lassen sich oft auch mit einfachen Bitoperationen abdecken (siehe Beispiele weiter unten).

Kann es leider momentan nicht testen. Daher meine Frage:

Was ist theoretisch schneller?

int file[64];
int rank[64];

inline int get_file(const int square) {
  return file[square];
}

inline int get_rank(const int square) {
  return rank[square];
}

oder

inline int get_file(const int square) {
  return square & 56;
}

inline int get_rank(const int square) {
  return square >> 3;
}

volkard

& und >> sind schon klasse.
Deswegen benutzt Du doch die ganze Zeit bitboards.

DocShoe

Ähnlicher Thread, gleiches Thema...

Don´t optimize prematurely!

Ich habe mal einen Testlauf mit 1 Milliarde Iterationen gemacht:

unsigned int ROWS[] = { /* Zeilenindizes */ };
unsigned int COLS[] = { /* Spaltenindizies */ };

void f1()
{
   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;
      }
   }
}

void 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];
      }
   }
}

Ergebnisse (Release Build auf nem 3.0 MHz Intel DualCore)
f1() : 1.29381E11 Cycles (43.1582 sec)
f2() : 1.29345E11 Cycles (43.1464 sec)

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!

Tomahawk

DocShoe schrieb:

Ähnlicher Thread, gleiches Thema...

Don´t optimize prematurely!

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!

Hallo DocShoe!

Nein, ich optimiere nicht an der falschen Stelle. Ich baue eine neue Engine von Grund auf und möchte, sofern möglich, von Anfang an einen guten Weg gehen und nicht nachher wieder alles über den Haufen werfen. Am besten ich kaplse die ganzen Zugriffe auf Tabellen in kleine Inline-Funktionen, um dann später bei Bedarf den Zugriff auf die Tabelle auf einen Schlag durch eine logische Operation zu ersetzen. Dann erspare ich mir die Arbeit an duzenden Stellen im Code den tabellezugriff durch eine Inlinefunktion zu ersetzen, um die Bitoperation zu implementieren.

So, jetzt muss ich mal offline gehen, da ich mir einige Trojaner gefangen haben und die Platte gesäubert werden muss...

Bashar

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. Die Variablen col und row sind z.B. völlig sinnlos, jeder normale Compiler würde sie wegschmeißen.

volkard

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.

volkard

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.

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.

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

*ROFL*

Bashar

Made my day!

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