Was ist theoretisch flotter?

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.

Bashar

unskilled, das war doch gar nicht als Falle gedacht, in die du tappen sollst.

DeepCopy

Nur aus Neugier mal getestet auf einem AMD 8450 3-Kern Prozessor, WindowsXP Sp3, Compiler VS2008 (Prof. Ed.)

#include <windows.h>
#include <iostream>
#include <iomanip>

ULONG32 test1();
ULONG32 test2();
double   getClockTime(const LARGE_INTEGER& Start,const LARGE_INTEGER& End);
LONGLONG getClockCycle(const LARGE_INTEGER& Start,const LARGE_INTEGER& End);

int main( void )
{
   LARGE_INTEGER liFrequence, liStart1, liEnd1, liStart2, liEnd2
                            , liStart1i, liEnd1i, liStart2i, liEnd2i;

   SetProcessAffinityMask(GetCurrentProcess(),1); 

   QueryPerformanceFrequency(&liFrequence);
   printf( "PerformanceFrequency: %i\n", liFrequence.QuadPart);

   printf( "Start Test1\n");
   QueryPerformanceCounter(&liStart1);
   test1();	
   QueryPerformanceCounter(&liEnd1);

   printf( "Start Test1 inline\n");
   QueryPerformanceCounter(&liStart1i);
   for( unsigned int o = 0; o < 1e7; ++o )
   {
      for( unsigned int i = 0; i < 64; ++i )
      {
         unsigned int row = i >> 3;
         unsigned int col = i % 8;
      }
   }
   QueryPerformanceCounter(&liEnd1i);

   printf( "Start Test2\n");
   QueryPerformanceCounter(&liStart2);
   test2();	
   QueryPerformanceCounter(&liEnd2);

   printf( "Start Test2 inline\n");
   QueryPerformanceCounter(&liStart2i);
   for( unsigned int o = 0; o < 1000*1000*10; ++o )
   {
      for( unsigned int i = 0; i < 64; ++i )
      {
         unsigned int row = i >> 3;
         unsigned int col = i % 8;
      }
   }
   QueryPerformanceCounter(&liEnd2i);

   const int cPrec = 12;
   const int cWidth = 9;

   std::cout << std::setfill(' ');
   std::cout <<  "test1()        : " << std::setw(cWidth) 
             << getClockCycle(liStart1, liEnd1) << " cycles [" 
             << std::setprecision(cPrec) << std::setw(3) 
             << getClockTime(liStart1, liEnd1) << " sec]" << std::endl;

   std::cout <<  "test1() inline : " << std::setw(cWidth)
             << getClockCycle(liStart1i, liEnd1i) << " cycles [" 
             << std::setprecision(cPrec) << std::setw(3) 
             << getClockTime(liStart1i, liEnd1i) << " sec]"  << std::endl;

   std::cout <<  "test2()        : " << std::setw(cWidth)
             << getClockCycle(liStart2, liEnd2) << " cycles [" 
             << std::setprecision(cPrec) << std::setw(3) 
             << getClockTime(liStart2, liEnd2) << " sec]" << std::endl;

   std::cout <<  "test2() inline : " << std::setw(cWidth)
             << getClockCycle(liStart2i, liEnd2i) << " cycles [" 
             << std::setprecision(cPrec) << std::setw(3) 
             << getClockTime(liStart2i, liEnd2i) << " sec]" << std::endl;
   getchar();
}

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

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

double getClockTime(const LARGE_INTEGER& Start,const LARGE_INTEGER& End)
{
	LARGE_INTEGER Freq;
	QueryPerformanceFrequency(&Freq);
	double Tick = static_cast<double>(End.QuadPart) - static_cast<double>(Start.QuadPart);
	return (Tick / static_cast<double>(Freq.QuadPart));
}

LONGLONG getClockCycle(const LARGE_INTEGER& Start,const LARGE_INTEGER& End)
{
	return End.QuadPart - Start.QuadPart;
}

RELASE Build 1e7
===========
PerformanceFrequency: 3579545
Start Test1
Start Test1 inline
Start Test2
Start Test2 inline
test1()        :        15 cycles [4.1904767226e-006  sec]
test1() inline :    167615 cycles [0.0468257837239    sec]
test2()        :         9 cycles [2.51428603356e-006 sec]
test2() inline :         8 cycles [2.23492091872e-006 sec]

DEBUG Build 1e7
===========
PerformanceFrequency: 3579545
Start Test1
Start Test1 inline
Start Test2
Start Test2 inline
test1()        :  35974720 cycles [10.0500817841 sec]
test1() inline :  36492236 cycles [10.1946577009 sec]
test2()        :  34339467 cycles [9.593249142   sec]
test2() inline :  35321222 cycles [9.86751724032 sec]

Fazit: Soll sich jeder selber machen. :ß

G-DC!

EDIT: Zeilenumbruch gekürzt.

Tomahawk schrieb:

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

Was soll da der Zusammenhang sein? Je nachdem was in den Arrays steht kommt doch was ganz anderes raus. Und wieso überhaupt diese bitoperationen um irgendwelche file und rank dinger aus square zu bekommen? Zusammenhang?

hustbaer

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.

Dass du so denkst, liegt vermutlich einfach daran, dass du überhaupt keine Ahnung von irgendwas hast.
Also Maul halten.

hustbaer schrieb:

Also Maul halten.

Sag mal Husti, nimmst Du Drogen oder bist Du von Haus aus so Dumm und Aggressiv?
Ich glaube Du kannst Dich selber nicht leiden!
Suche Dir mal einen anderen Spielplatz Du Fatzke.

Was erwartet ihr? Leute die beruflich Software schreiben und sie optimieren stellen solche Fragen doch nicht in Foren. Diese "Was ist schneller"-Fragen hier kommen zu 99.9% von Anfängern die wirklich professionelle Engines, MMPORGs usw. schreiben.