Bitweises Und + Vergleich in Assembler

[DieDackel]

Hallo Leute,

ich habe folgendes Problem:
Zurzeit programmiere ich eine KI in C für ein Vier-Gewinnt Spiel. Um einen perfekten Gegner zu bekommen, der auch in akzeptabler Zeit einen Zug berechnet, ist schon einiges an Aufwand nötig. Mittlerweile hat mein Quelltext schon mehr als 5000 Zeilen. Um noch ein bisschen Zeit rauszukitzeln bin ich am überlegen, besonders zeitkritische Teile in Assembler zu programmieren. Knapp 2000 Zeilen des Programms sehen folgendermaßen aus:

[cpp]
switch(Height[3])
	{
		case 0:
			if((Feld1 & 0x4200000000i64) == 0x4200000000i64 && Height[2]<1) return 3;
			if((Feld1 & 0x210000000i64) == 0x210000000i64 && Height[0]<3) return 3;
			if((Feld1 & 0x4010000000i64) == 0x4010000000i64 && Height[1]<2) return 3;
			if((Feld1 & 0x10200i64) == 0x10200i64 && Height[6]<3) return 3;
			if((Feld1 & 0x204i64) == 0x204i64 && Height[4]<1) return 3;
			if((Feld1 & 0x10004i64) == 0x10004i64 && Height[5]<2) return 3;
			break;
		case 1:
			if((Feld1 & 0x10400000000i64) == 0x10400000000i64 && Height[2]<1) return 3;
			if((Feld1 & 0x410000000i64) == 0x410000000i64 && Height[0]<1) return 3;
                          .               .
                          .               .
                          .               .
                          .               .
                          .               .
[/cpp]

Die Variable Feld1 besteht aus 64 Bit. Das Array Height besteht aus 7 Elementen, die jeweils die Werte von 0-6 annehmen können.

einen bestimmten Wert unterschreitet. Ist der Gesamtausdruck der If-Abfrage TRUE, dann wird die Funktion sofort beendet und eine Konstante zurückgegeben.

Jetzt meine Frage:
Lohnt es sich überhaupt, das alles in Assembler zu schreiben(Kann man genug Laufzeit einsparen? Arbeitszeit ist mir egal). Und wenn ja, könnte jemand exemplarisch etwas Assembler-Code posten, den ich dann auf alle Zeilen anwenden kann.
Für jede noch so kleine Idee bin ich dankbar, denn meine Kenntnisse in Assembler sind doch sehr beschränkt.

[rapso]

benchmark es mal mit sowas

template<int64_t Mask,int64_t Value>
bool compare(int64_t Field,int64_t Height)
{
  const int64_t SignBit = sizeof(int64_t)*8-1;
  const int64_t M=((Field&Mask)-Mask);
  const int64_t C=((static_cast<int64_t>(Height)-Value)>>SignBit)+1;
  return (M|C)==0;
}

//im switch
if(compare<0x4200000000i64,1>(Feld1,Height[2],1) return 3;

das ist ungetestet, ich weiss nichtmal ob es compiliert ;), aber es koennte der cpu entgegen kommen.

btw. solche magic numbers wie "0x4200000000i64" koennte man mit templates gut generieren, das koennte das fehleranfaellige erstellen von ihnen ersparen. (das ist nichts dramatisches, nur ein kleiner hinweis um sich das leben einfacher zu machen )

[Nobuo T]

Das bringt sehr Wahrscheinlich bestenfalls gar nichts, wenn du da noch versuchst, mit Assembler rum zu werkeln. Da ist es sinnvoller, das alles in C evtl. sinnvoller zu optimieren.
Sieht ja fast so aus, als wuerdest du zu so ziemlich jedem moeglichen Konstellation im Spielfeld eine vorprogrammierte Antwort liefern. Ob das so optimal ist... Bestimmt wuerde es auch sinn machen, mit Arrays zu arbeiten, statt tausenden von ifs.

Edit:
@rapso: weiss nicht... Ich bin da irgendwie skeptisch...

[rapso]

ja ich benutze auch arrays, ich wollte nur nicht sein komplettes system umstellen.

www.rapso.de/ranz/4Win.exe

das lustige ist, wenn man es richtig anstellt, sodass in einigen zuegen die KI auf jedenfall verliert, wird sie ganz aphatisch und zieht nur noch unsinn.
manchmal, wenn kein sieg in reichweite ist, zieht sie auch nur unsinn. ich glaube die suchtiefe hatte ich auf 7 eingestellt.

mit arrays kann man ganz simple z.b.

Value=Field[0]+Field[1]+Field[2]+Field[3];
if(abs(Value)==4)
...

und fuer spieler setz ich 1, gegenspieler -1.

wenn man es noch etwas schneller will, kann man mit SS4 unalligned reads nutzen um den vector einzulesen und dann mittels dotproduct die 4 floats accumulieren.
das geht extrem fix seit dem penryn model.

[DieDackel]

Schonmal vielen Dank für die Antworten...

@rapso: Ich werd deinen Vorschlag mal bei Gelegenheit testen, obwohl ich da auch ein wenig skeptisch bin, weil die CPU wahrscheinlich mehr Operationen machen muss um Deinen Teil abzuarbeiten, als bei einer normalen If-Abfrage.
Dein Vier-GewinntProgramm funktioniert bei mir leider nicht. Es kommt immer die Fehlermeldung, dass die Anwendungskonfiguration nicht korrekt ist.

@Nobuo T:
Meine ersten Versionen von Vier Gewinnt habe ich mit Arrays realisiert. Aber wenn man mit Arrays arbeitet kommt man in der Regel nicht um den Gebrauch von Schleifen herum. Und Schleifen fressen Laufzeit. Zusätzlich ist der Code in Schleifen sehr Allgemein formuliert, sodass oft unnötige Berechnungen ausgeführt werden. Wenn man mit Bitboards arbeitet, dann kann man die sehr schnellen Bit-Operatoren verwenden(Bitwise-AND, OR, Verschiebe-Operatoren), hat aber den Nachteil, dass man einen längeren, komplizierteren und schwerer zu wartenden Code hat. Dies muss man aber bei Laufzeit-Optimierten Programmen in Kauf nehmen.
Naja, ich hab mir auch schon gedacht, dass mit Assembler nicht viel bis Nichts rauszuholen ist.

Aber vllt. hat ja noch ein heller Kopf eine Idee, wie man das ganz geschickt in Assembler oder auch in C ausdrücken kann.

[rapso]

DieDackel schrieb:

Schonmal vielen Dank für die Antworten...

@rapso: Ich werd deinen Vorschlag mal bei Gelegenheit testen, obwohl ich da auch ein wenig skeptisch bin, weil die CPU wahrscheinlich mehr Operationen machen muss um Deinen Teil abzuarbeiten, als bei einer normalen If-Abfrage.

dafuer sind sie branchfree, und darauf kommt es oft an. ein branchmiss duerfte oft weit aus mehr kosten als die instruktionen dort haben.... kommt aber bei x86 cpus auch drauf an was die daraus machen.

[abc.w]

DieDackel schrieb:

Für jede noch so kleine Idee bin ich dankbar, denn meine Kenntnisse in Assembler sind doch sehr beschränkt.

Ich habe noch eine kleine Idee, die aber nur unter GCC funktionieren würde und da dein Programm sowieso schon so kryptisch ist.. warum denn nicht mit "goto" arbeiten und zwar mit folgender Erweiterung von GCC (weiss nicht, vielleicht unterstützen diese Erweiterung auch andere Compiler), nämlich mit Zeigern auf Sprungmarken. Im Prinzip ist das folgendes:

void *pMarke = NULL;
pMarke = &&SprungMarke;
goto *pMarke;
...
SprungMarke:
...

Und diese Idee kann man so weit ausbauen, dass man ein Array von Zeigern auf Sprungmarken hat, hier ein Beispiel mit einer Variable aus deinem Code:

void *pMarke[] = { &&SprungMarkeEins, &&SprungMarkeZwei, &&SprungMarkeDrei };
...
goto *pMarke[Height[3]];
SprungMarkeEins:
...
SprungMarkeZwei:
...
SprungMarkeDrei:
...

Das soll laut GCC-Doku angeblich recht schnell sein und außerdem ist "goto" ein absoluter Sprung (kein bedingter Sprung). Da du anscheinend Zeit hast, kannst ja mal ausprobieren, und uns berichten, ob was gebracht hat. Also, man kann es beliebig kompliziert machen, bestimmte Codeabschnitte vollständig, und wenn man geschickt ist, auch bestimmte if's einsparen und durch ein "goto" ersetzen.

[DieDackel]

Ahhh, das mit den Sprungmarken hört sich doch ganz interessant an. Das muss ich mal morgen ausprobieren, bin mal gespannt ob das schneller ist. Mal sehen, ob das auch mit dem C++-Builder so funktioniert. Danke für den Tipp!!!

[rapso]

genau das sollte ein compiler aus einer switch anweisung machen
visual studio und gcc machen das auch.

[DieDackel]

Ja stimmt, da hast du Recht rapso . Ich hab das vorhin mal ausprobiert und das ist tatsächlich genauso schnell wie die switch-Anweisung. Schade, wär mal ganz interessant gewesen.
Aber mal ne andere Frage:
if/else if - Konstruktionen müssten ja bis zu einer gewissen Anzahl schneller sein als switch-Anweisungen, weil bei der switch-Anweisung ja erstmal die Sprungmarken berechnet werden müssen. Weiß da jemand etwas???

Aber ich glaube wir weichen ein wenig vom Thema ab, wir sind ja im Assembler Forum...

[rapso]

DieDackel schrieb:

if/else if - Konstruktionen müssten ja bis zu einer gewissen Anzahl schneller sein als switch-Anweisungen, weil bei der switch-Anweisung ja erstmal die Sprungmarken berechnet werden müssen. Weiß da jemand etwas???

die kosten bei jumptables enstanden dadurch dass sie immer wie ein jump mit falsche jumpprediction gehandelt wurden. ab conroe sollte das aber nicht mehr der fall sein. ich denke, dass somit, sofern die daten fuer den sprung bekannt sind, dass das schnellste sein wird, ich glaube allerdings, dass es trotzdem kein prefetching fuer dan codecache gibt.

ansonsten sind normale if abfragen theoretisch schneller, sofern der wert weit im voraus bekannt ist oder die jumpprediction richtig laeuft.
aber darum kuemmern sich compiler auch.

Aber ich glaube wir weichen ein wenig vom Thema ab, wir sind ja im Assembler Forum...

wo wir biem thema sind, haste zeit gefunden meinen code zu benchmarken?

[DieDackel]

Ne, hab ich noch nicht gemacht. Aber wo du es grad erwähnst...
Ich glaub das probier ich jetzt mal grad aus...

[DieDackel]

template<int64_t Mask,int64_t Value>
bool compare(int64_t Field,int64_t Height)
{
  const int64_t SignBit = sizeof(int64_t)*8-1;
  const int64_t M=((Field&Mask)-Mask);
  const int64_t C=((static_cast<int64_t>(Height)-Value)>>SignBit)+1;
  return (M|C)==0;
}

//im switch
if(compare<0x4200000000i64,1>(Feld1,Height[2],1) return 3;

So, ich hab das mal getetest. Dieser Code ist ungefähr 3x langsamer als die normalen if-Abfragen. Naja, einen Versuch war es wert.

[rapso]

DieDackel schrieb:

So, ich hab das mal getetest. Dieser Code ist ungefähr 3x langsamer als die normalen if-Abfragen. Naja, einen Versuch war es wert.

wow, krass
hier mein kurzer test

DU32 Test0(DU32 Feld1,DU32 Height)
{
	if((Feld1 & 0x420000) == 0x420000 && Height<1) return 3; 
	if((Feld1 & 0x210000) == 0x210000 && Height<3) return 3; 
	if((Feld1 & 0x401000) == 0x401000 && Height<2) return 3; 
	if((Feld1 & 0x10200) == 0x10200 && Height<3) return 3; 
	if((Feld1 & 0x204) == 0x204 && Height<1) return 3; 
	if((Feld1 & 0x10004) == 0x10004 && Height<2) return 3; 
	return 1;
}

template<DU32 Mask,DU32 Value> 
bool compare(DU32 Field,DU32 Height) 
{ 
  const DU32 SignBit = sizeof(DU32)*8-1; 
  const DU32 M=((Field&Mask)-Mask); 
  const DU32 C=((static_cast<DU32>(Height)-Value)>>SignBit)+1; 
  return (M|C)==0; 
} 

DU32 Test1(DU32 Feld1,DU32 Height)
{
	if(compare<0x420000,1>(Feld1,Height)) return 3; 
	if(compare<0x210000,3>(Feld1,Height)) return 3; 
	if(compare<0x401000,2>(Feld1,Height)) return 3; 
	if(compare<0x10200,3>(Feld1,Height)) return 3; 
	if(compare<0x204,1>(Feld1,Height)) return 3; 
	if(compare<0x10004,2>(Feld1,Height)) return 3; 
	return 1;
}

bool Test()
{
	DU32 C0=0,C1=0;
	const DU32 Loops	=	1000000000;
	DU32 T0=NDionysos3::NDCore::CDTimer::TickMs();
	for(DU32 a=0;a<Loops;a++)
		C0+=Test0(C0,a);
	DU32 T1=NDionysos3::NDCore::CDTimer::TickMs();
	for(DU32 a=0;a<Loops;a++)
		C1+=Test1(C1,a);
	DU32 T2=NDionysos3::NDCore::CDTimer::TickMs();
	printf("%d %d  ",T1-T0,T2-T1);
	return C0==C1;
}

resultat

8548 8300 true

deine resultate sind fuer mich leider nicht nachvollziehbar, aber ich hab auch keine realen testdaten bzw testumgebung.

welches OS (wieviel 32 oder 64bit?) und welche cpu hast du?

ich hab das mal bewust leicht abgeaendert fuer 32bit, war nur ein kurzer hack in etwas bestehendes als ich das hier gerade von dir las ;).

[hellihjb]

DU32 Test0(DU32 Feld1,DU32 Height)
{
    if((Feld1 & 0x420000) == 0x420000 && Height<1) return 3;
    if((Feld1 & 0x210000) == 0x210000 && Height<3) return 3;
    if((Feld1 & 0x401000) == 0x401000 && Height<2) return 3;
    if((Feld1 & 0x10200) == 0x10200 && Height<3) return 3;
    if((Feld1 & 0x204) == 0x204 && Height<1) return 3;
    if((Feld1 & 0x10004) == 0x10004 && Height<2) return 3;
    return 1;
}

Kann man da nicht was in groesserem Radius optimieren?
Wie haeufig aendern sich denn Feld1 und Height ?

[DieDackel]

@rapso:
Also ich hab einen AMD Turion (DualCore, 1,6GHz) und Windows XP.
Also mich wundert das jetzt, dass unsere Ergebnisse so deutlich von einander abweichen.
Ich kann mir auch nicht vorstellen, dass das an deiner Änderung zu 32 Bit liegt. Ich werd meinen Test nochmal dürchführen, vllt. hab ich mich vertan.

@hellihjb:
Also die Variablen Feld1(64 Bit) und Height[x](7 Elemente, short) sind praktisch bei jedem Funktionsaufruf unterschiedlich.

[DieDackel]

Achso, der Turion ist ein Turion 64...

[DieDackel]

rapso schrieb:

DieDackel schrieb:

So, ich hab das mal getetest. Dieser Code ist ungefähr 3x langsamer als die normalen if-Abfragen. Naja, einen Versuch war es wert.

resultat

8548 8300 true

deine resultate sind fuer mich leider nicht nachvollziehbar, aber ich hab auch keine realen testdaten bzw testumgebung.

welches OS (wieviel 32 oder 64bit?) und welche cpu hast du?

ich hab das mal bewust leicht abgeaendert fuer 32bit, war nur ein kurzer hack in etwas bestehendes als ich das hier gerade von dir las ;).

Naja, ich hab das grad nochmal mit deinem Code(leicht abgeändert) probiert. Da krieg ich immer noch das gleiche Ergebnis(Template ca. 3x langsamer, bei 32 Bit- wie auch bei 64Bit Variablen).

__int32 Test0(__int32 Feld1,__int32 Height)
{
	if((Feld1 & 0x420000) == 0x420000 && Height<1) return 3;
	if((Feld1 & 0x210000) == 0x210000 && Height<3) return 3;
	if((Feld1 & 0x401000) == 0x401000 && Height<2) return 3;
	if((Feld1 & 0x10200) == 0x10200 && Height<3) return 3;
	if((Feld1 & 0x204) == 0x204 && Height<1) return 3;
	if((Feld1 & 0x10004) == 0x10004 && Height<2) return 3;
	return 1;
}

template<__int32 Mask,__int32 Value>
bool compare(__int32 Field,__int32 Height)
{
  const __int32 SignBit = sizeof(__int32)*8-1;
  const __int32 M=((Field&Mask)-Mask);
  const __int32 C=((static_cast<__int32>(Height)-Value)>>SignBit)+1;
  return (M|C)==0;
}

__int32 Test1(__int32 Feld1,__int32 Height)
{
	if(compare<0x420000,1>(Feld1,Height)) return 3;
    if(compare<0x210000,3>(Feld1,Height)) return 3;
	if(compare<0x401000,2>(Feld1,Height)) return 3;
    if(compare<0x10200,3>(Feld1,Height)) return 3;
	if(compare<0x204,1>(Feld1,Height)) return 3;
    if(compare<0x10004,2>(Feld1,Height)) return 3;
	return 1;
}

bool Test()
{
    __int32 C0=0,C1=0;
	const __int32 Loops    =    1000000000;
	LONGLONG g_Frequency, g_CurentCount, g_LastCount;
    //Frequenz holen
	if (!QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency))
		std::cout << "Performance Counter nicht vorhanden" << std::endl;

	QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);
	for(__int32 a=0;a<Loops;a++)
		C0+=Test0(C0,a);
	QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);
	double dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency));
	std::cout << "Zeit: " << dTimeDiff << std::endl;

	QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);
	for(__int32 a=0;a<Loops;a++)
		C1+=Test1(C1,a);
	QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);
	dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency));
	std::cout << "Zeit: " << dTimeDiff << std::endl;

	return C0==C1;
}

Ergebnis:
20,747
64,6001

[rapso]

benutzt du vielleicht gcc?
3mal langsammer ist echt weird

64bit bei einem 32bit os zu verwenden resultiert in 32bit code der 64bit 'emuliert', weil das OS leider nur 32bit register sichert und selbst wenn also deine applikation 64bit nutzen sollte, wuerde es schiefgehen.

esseiden windows macht etwas was mir entgeht. (Nobuo T , seh ich was falsch??)

btw. nur um mal so allgemeine dinge auszuschliessen.
-du baust im release?
-welche optimierungen hast du an?

[DieDackel]

Ich hab das mit dem Borland C++ Builder 5 compiliert in der Release-Version. Code-Optimierung ist auf Geschwindigkeit gestellt.
Anweisungsset: 80386

Also ich hab ein 64Bit Xp-OS