Bitweises Und + Vergleich in Assembler

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.

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.

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?

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

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 ?

@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.

Achso, der Turion ist ein Turion 64...

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?

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

Nobuo T

Kommt wohl auf die Optimierung und verwendete Befehlssätze an, was der Compiler aus 64Bit-Ints macht. Ich traue denen da grundsaetzlich vieles (vor allem Unfug) zu.
Aber wenn du fuer i386 compilierst, kommt auch nur 32Bit i386 raus (dh. 1 64Bit aufgeteilt auf 2x32 ... sollte zumindest), unabhaengig von Windows, 64Bit, Intel oder worauf auch immer das nachher laeuft.

Hm, ich hab noch ne andere Optimierungsmöglichkeit für diese Funktion. Die Funktion ist ja aus 7 switch-Anweisungen aufgebaut, die alle so wie die folgende aussehen (wobei diese die wenigsten If-Abfragen beinhaltet):

switch(Height[0])
	{
		case 0:
			if((Feld1 & 0x408000000i64) == 0x408000000i64 && Height[3]<3) return 0;
			if((Feld1 & 0x8100000i64) == 0x8100000i64 && Height[1]<1) return 0;
			if((Feld1 & 0x400100000i64) == 0x400100000i64 && Height[2]<2) return 0;
			break;
		case 1:
			if((Feld1 & 0x410000000i64) == 0x410000000i64 && Height[3]<1) return 0;
			if((Feld1 & 0x10400000i64) == 0x10400000i64 && Height[1]<1) return 0;
			if((Feld1 & 0x400400000i64) == 0x400400000i64 && Height[2]<1) return 0;
			if((Feld1 & 0x204000000i64) == 0x204000000i64 && Height[3]<4) return 0;
			if((Feld1 & 0x4080000i64) == 0x4080000i64 && Height[1]<2) return 0;
			if((Feld1 & 0x200080000i64) == 0x200080000i64 && Height[2]<3) return 0;
			break;
		case 2:
			if((Feld1 & 0x208000000i64) == 0x208000000i64 && Height[3]<2) return 0;
			if((Feld1 & 0x8200000i64) == 0x8200000i64 && Height[1]<2) return 0;
			if((Feld1 & 0x200200000i64) == 0x200200000i64 && Height[2]<2) return 0;
			if((Feld1 & 0x102000000i64) == 0x102000000i64 && Height[3]<5) return 0;
			if((Feld1 & 0x2040000i64) == 0x2040000i64 && Height[1]<3) return 0;
			if((Feld1 & 0x100040000i64) == 0x100040000i64 && Height[2]<4) return 0;
			break;
		case 3:
			if((Feld1 & 0x104000000i64) == 0x104000000i64 && Height[3]<3) return 0;
			if((Feld1 & 0x4100000i64) == 0x4100000i64 && Height[1]<3) return 0;
			if((Feld1 & 0x100100000i64) == 0x100100000i64 && Height[2]<3) return 0;
			if((Feld1 & 0x10800000i64) == 0x10800000i64 && Height[1]<2) return 0;
			if((Feld1 & 0x200800000i64) == 0x200800000i64 && Height[2]<1) return 0;
			break;
		case 4:
			if((Feld1 & 0x82000000i64) == 0x82000000i64 && Height[3]<4) return 0;
			if((Feld1 & 0x2080000i64) == 0x2080000i64 && Height[1]<4) return 0;
			if((Feld1 & 0x80080000i64) == 0x80080000i64 && Height[2]<4) return 0;
			if((Feld1 & 0x108000000i64) == 0x108000000i64 && Height[3]<1) return 0;
			if((Feld1 & 0x8400000i64) == 0x8400000i64 && Height[1]<3) return 0;
			if((Feld1 & 0x100400000i64) == 0x100400000i64 && Height[2]<2) return 0;
			break;
		case 5:
			if((Feld1 & 0x41000000i64) == 0x41000000i64 && Height[3]<5) return 0;
			if((Feld1 & 0x1040000i64) == 0x1040000i64 && Height[1]<5) return 0;
			if((Feld1 & 0x40040000i64) == 0x40040000i64 && Height[2]<5) return 0;
			if((Feld1 & 0x84000000i64) == 0x84000000i64 && Height[3]<2) return 0;
			if((Feld1 & 0x4200000i64) == 0x4200000i64 && Height[1]<4) return 0;
			if((Feld1 & 0x80200000i64) == 0x80200000i64 && Height[2]<3) return 0;
			break;
		default:
			break;
	}

Beim durcharbeiten des Spiel-Baumes wird die Funktion in jedem Knoten aufgerufen, die dann diese 7 switch-Anweisungen durcharbeitet. Je tiefer man im Spielbaum gelangt, desto weniger dieser If-Abfragen werden benötigt, weil man schon weiß, dass diese nicht erfüllt werden können. Da in den tieferen Bereichen des Spielbaums ja die meisten Knoten abgearbeitet werden und in diesen Bereichen die meisten If-Abfragen eingespart werden könnten, sehe ich dort Potential um noch Zeit rauszuholen. Die Frage ist nur wie??? Man kann dem Programm ja nicht so einfach ohne viel Aufwand sagen, dass er im nächst tieferen Knoten diese if-Abfragen einfach überspringen soll, weil die sowieso nicht erfüllt werden.

Ihr scheint ja euer Fach zu verstehen, vllt. habt ihr ja ne Idee???
Hoffentlich konnte ich klar machen, worum es geht...

rapso

pruefst du etwa in jedem durchgang alle felder durch? oder hab ich das missverstanden?

an sich musst du nur pro feld in das du was reinsetzt einmal pruefen ob daraus jetzt ein 4er entsteht.

wenn du das spielfeld nicht 7*6, sondern 13*12 machst, kannst du dir jegliche sonderbehandlungen ersparen und normal testen, wobei ich, wie Nobuo T auch schon sagte, eher arrays statt bitmasken nutzen wuerde, ist um einige schneller afaik.

Die Funktion prüft ja nicht ob man einen Vierer bekommt, sondern ob man eine Drohung erstellen kann und gibt dann die entsprechende Spalte zurück, daher muss ich alle 7 Spalten prüfen. Aber die Funktion für die Vierer ist dieser sehr ähnlich, nur nen bisschen einfacher. Alles was sich auf diese Funktion anwenden kann, müsste ich normalerweise auch auf die Vierer-Funktion anwenden können. Diese Drohungen-Suchen-Funktion ist für die Zugsortierung sehr wichtig und wird daher in jedem Knoten bis zur Tiefe 22 aufgerufen, für größere Tiefen ist Sie uninteressant, weil dort in der Regel nicht mehr so viele Drohungen erstellt werden können...

Hab ich das richtig verstanden, dass ich das Spielfeld durch ein Array darstellen soll oder meintest du was anderes???