Bitweises Und + Vergleich in Assembler

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???