4. Verbesserungswürdiger Assembler Code???

Verbesserungswürdiger Assembler Code???

  • C
    Mod

    masm schrieb:

    du must dir die Bitmasken anschauen und auf Gemeinsamkeiten achten:

    Da ist nur sinnvoll, wenn die Wortbreite des Prozessors deutlich kleiner als die zu vergleichenden Werte sind oder bestimmte Teilmuster dominieren. Ansonsten dürfte es genügen, die Werte der Größe nach zu ordnen, um bei Architekturen mit kleiner Wortbreite Vergleiche des höherwertigen Teils sparen zu können, wenn er zwischen aufeinanderfolgenden Werten gleich ist (das schafft der Compiler dann auch selber).
    Visual C++ spukt das aus:

    bool SpielBeenden1(void)
{
    i64 x = ~Feld1;
    return !( x & 0x20820000000i64
           && x & 0x00820020000i64
           && x & 0x00020020800i64
           && x & 0x00000020820i64
           && x & 0x00000010204i64
           && x & 0x04210000000i64 );
}

00401800  push        ebp  
00401801  mov         ebp,esp 
00401803  and         esp,0FFFFFFF8h 
00401806  push        ecx  
00401807  mov         eax,dword ptr [Feld1 (403378h)] 
0040180C  mov         ecx,dword ptr [Feld1+4 (40337Ch)] 
00401812  push        esi  
00401813  not         eax  
00401815  not         ecx  
00401817  mov         edx,eax 
00401819  mov         esi,ecx 
0040181B  and         edx,20000000h 
00401821  and         esi,208h 
00401827  or          edx,esi 
00401829  je          SpielBeenden1+75h (401875h) 
0040182B  mov         edx,eax 
0040182D  mov         esi,ecx 
0040182F  and         edx,20020000h 
00401835  and         esi,8 
00401838  or          edx,esi 
0040183A  je          SpielBeenden1+75h (401875h) 
0040183C  mov         edx,eax 
0040183E  and         edx,20020800h 
00401844  xor         esi,esi 
00401846  or          edx,esi 
00401848  je          SpielBeenden1+75h (401875h) 
0040184A  mov         edx,eax 
0040184C  and         edx,20820h 
00401852  or          edx,esi 
00401854  je          SpielBeenden1+75h (401875h) 
00401856  mov         edx,eax 
00401858  and         edx,10204h 
0040185E  or          edx,esi 
00401860  je          SpielBeenden1+75h (401875h) 
00401862  and         eax,10000000h 
00401867  and         ecx,42h 
0040186A  or          eax,ecx 
0040186C  je          SpielBeenden1+75h (401875h) 
0040186E  xor         eax,eax 
00401870  pop         esi  
00401871  mov         esp,ebp 
00401873  pop         ebp  
00401874  ret              
00401875  mov         eax,1 
0040187A  pop         esi  
0040187B  mov         esp,ebp 
0040187D  pop         ebp  
0040187E  ret

    ... sieht ineffizient aus.

    mov     ecx, dword ptr [Feld]
        mov     edx, dword ptr [Feld+4]
        xor     eax, eax
        not     ecx
        test    edx, edx
        jnz     @1
        test    ecx, 20020800h
        jz      @exit
        test    ecx,    20820h
        jz      @exit
        test    ecx,    10204h
        jmp     @exit
@1:     not     edx
        test    edx, 8h
        jnz     @2
        test    edx, 208h
        jz      @3
        test    ecx, 20020000h
        jmp     @exit
@3:     test    ecx, 20000000h
        jmp     @exit
@2:     test    edx, 42h
        jnz     @exit
        test    ecx, 10000000h
@exit:  setz    eax, 1
        ret

    wäre handgeschrieben. maximal 3 bedingte Sprünge je nach gewähltem Pfad.

    0
  • A

    camper schrieb:

    ...Z.b.

    bool SpielBeenden1()
{
    i64 x = ~Feld1;
    return !( x & 0x20820000000i64 && x & 0x00820020000i64 && x & 0x00020020800i64 && x & 0x00000020820i64 && x & 0x00000010204i64 && x & 0x04210000000i64 );
}

    Musste zwei mal draufgucken, aber, das ist gut 👍
    Ich würde es vielleicht noch extra "klammern":

    ...
    return !((x & 0x20820000000i64) && (x & 0x00820020000i64) && (x & 0x00020020800i64) && (x & 0x00000020820i64) && (x & 0x00000010204i64) && (x & 0x04210000000i64));
    0
  • ?

    Schonmal Vielen Dank für die Antworten...

    @camper: Ja, das sieht schon um einiges besser aus als meine Lösung, das spart mit Sicherheit einiges an Rechenzeit. Vielen Dank für den SUPER Tipp. Ich versuche erstmal das in C zu programmieren und guck mir dann den Assembler-Code an.

    @Nobuo T: Beim Compiler habe ich "auf Geschwindigkeit optimieren" eingestellt. Da ich aber noch nie viel mit Optimierung zu tun hatte muss ich mich erstmal in die ganze Thematik einarbeiten. Mir wurde gesagt, dass der Compiler vom C++-Builder schon so hocheffizienten Code erzeugt, ohne große Frickeleien. Hoffentlich war das richtig...

    Trotzdem allen meinen Dank für die Ratschläge. Werde mich jetzt erstmal an die Arbeit machen und gucken was rauskommt...

    0
  • ?

    camper schrieb:

    mov     ecx, dword ptr [Feld]
        mov     edx, dword ptr [Feld+4]
        xor     eax, eax
        not     ecx
        test    edx, edx
        jnz     @1
        test    ecx, 20020800h
        jz      @exit
        test    ecx,    20820h
        jz      @exit
        test    ecx,    10204h
        jmp     @exit
@1:     not     edx
        test    edx, 8h
        jnz     @2
        test    edx, 208h
        jz      @3
        test    ecx, 20020000h
        jmp     @exit
@3:     test    ecx, 20000000h
        jmp     @exit
@2:     test    edx, 42h
        jnz     @exit
        test    ecx, 10000000h
@exit:  setz    eax, 1
        ret

    wäre handgeschrieben. maximal 3 bedingte Sprünge je nach gewähltem Pfad.

    das sieht doch schon deutlich besser aus 👍
    Das vorherige Inverteiren macht deutlich mehr sinn als and/cmp

    0
  • L

    Franz von und zu Assisi schrieb:

    Nachtrag:
    Da die eigentliche Funktion aus einigen Hundert solcher if-Abfragen besteht, wird es schwer, den Code von Hand anzupassen. Vllt. hat ja jemand eine elegante Lösung in C parat ...

    Also ich kenne kein Spiel, das zu Ende ist, wenn bestimmte Bits gesetzt sind. Vielleicht solltest du einfach einen anderen Algorithmus nehmen, um das Ende des Spiels zu bestimmen.

    0
  • V

    Franz von und zu Assisi schrieb:

    Da die eigentliche Funktion aus einigen Hundert solcher if-Abfragen besteht, wird es schwer, den Code von Hand anzupassen. Vllt. hat ja jemand eine elegante Lösung in C parat ...

    Die werden doch was gemeinsam haben, was man abfragen kann. Zur Not baut man eine perfekte oder nur gute hashtable. hab ich noch nie gemacht. poste doch mal ein array mit den 100 den werten.

    0
  • ?

    Naja, viel hat die Änderung leider nicht gebracht, weil der Compiler ziemlichen Blödsinn daraus macht, so ähnlich wie bei dir camper. Das sieht in etwa so aus:

    @4:
	mov       eax,dword ptr [_Feld1]
	add       esp,-8
	not       eax
	mov       edx,dword ptr [_Feld1+4]
	mov       dword ptr [esp],eax
	not       edx
	mov       dword ptr [esp+4],edx
@5:
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,536870912
	and       edx,520
	cmp       edx,0
	jne       short @8
	cmp       eax,0
@8:
	je        @7
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,537001984
	and       edx,8
	cmp       edx,0
	jne       short @9
	cmp       eax,0
@9:
	je        short @7
	mov       eax,dword ptr [esp]
	mov       edx,dword ptr [esp+4]
	and       eax,537004032
	xor       edx,edx
	cmp       edx,0
	jne       short @10
	cmp       eax,0
.
.
.
.

    Naja, muss ich mir Morgen dann noch ein paar Gedanken zu machen. Vllt. hat auch jemand eine Idee, wie ich dem Compiler beibringen kann, einen Assembler-Code ohne diese cmp/and zu erzeugen...

    0
  • V

    EDIT: Alles falsch! Du sucht ja nicht bestimmte Werte, sondern welche der vielen Bitmaskee paßt. Alles vergebens. Ich bin ja soo doof.

    Hab ein Testprogramm geschieben

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

using namespace std;

typedef unsigned long long u64;
typedef unsigned int u32;

bool test(u64 x) {
	u32 t=u32(x)^u32(x>>32);
	u32 y=(t*2175734977u)>>29;
	static u64 table[]={
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x10204ull,
		0x4210000000ull,
		0x10204ull,
		0x20820ull,
		0x20820000000ull,
	};
	return x==table[y];
}

u64 goodValues[]={
	0x20820000000ull,
	0x820020000ull,
	0x20020800ull,
	0x20820ull,
	0x10204ull,
	0x4210000000ull,
};

int main() {
	size_t const goodValuesSize=sizeof(goodValues)/sizeof(goodValues[0]);
	size_t const tableSizeBits=3;
	size_t const tableSize=1<<tableSizeBits;
	u64 table[tableSize];
	u32 const step=2654435761u;
	for (u32 a=step;a!=0;a+=step) {
		if (a%1048576==0)
			cout<<"checking "<<a<<'\n';
		bool seen[tableSize]={};
		for (size_t i=0;i!=goodValuesSize;++i) {
			u64 x=goodValues[i];
			u32 t=u32(x)^u32(x>>(32-tableSizeBits));
			u32 y=(t*a)>>29;
//			cout<<x<<' '<<y<<'\n';
//			Sleep(1000);
			if (seen[y])
				goto collission;
			table[y]=x;
			seen[y]=true;
		}
		cout<<"found\n";
		cout<<"\ty=(t*"<<a<<"u)>>"<<32-tableSizeBits<<";\n";
		cout<<hex;
		cout<<"\tstatic u64 table[]={\n";
		for (size_t i=0;i!=tableSize;++i) {
			if (seen[i])
				cout<<"\t\t0x"<<table[i]<<"ull,\n";
			else
				cout<<"\t\t0x"<<table[0]<<"ull,\n";
		}
		cout<<"\t};\n";
		break;
collission:
		;
	}
	cout<<test(1)<<'\n';
	return 0;
}

    Es fand

    bool test(u64 x) {
	u32 t=u32(x)^u32(x>>32);
	u32 y=(t*2175734977u)>>29;
	static u64 table[]={
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x10204ull,
		0x4210000000ull,
		0x10204ull,
		0x20820ull,
		0x20820000000ull,
	};
	return x==table[y];
}

    Code aus dem Compilat von GCC kopiert:

    LFE652:
	.text
	.p2align 4,,15
.globl __Z4testy
	.def	__Z4testy;	.scl	2;	.type	32;	.endef
__Z4testy:
LFB991:
	pushl	%ebp
LCFI2:
	movl	%esp, %ebp
LCFI3:
	movl	12(%ebp), %edx
	movl	8(%ebp), %ecx
	movl	%edx, %eax
	xorl	%ecx, %eax
	imull	$-2119232319, %eax, %eax
	shrl	$29, %eax
	xorl	__ZZ4testyE5table(,%eax,8), %ecx
	xorl	__ZZ4testyE5table+4(,%eax,8), %edx
	leave
	orl	%edx, %ecx
	sete	%al
	ret
LFE991:

    nur ein MUL und kein bedingter Sprung.
    Hunderte von Werten werden wohl eine kompliziertere Hash-Funktion als nur u32 t=u32(x)^u32(x>>32); u32 y=(t*2175734977u)>>29; brauchen, aber wer weiß, vielleicht nur wenige Takte schlimmer.

    Wenns kein AMD ist, ist vielleicht

    u32 y=(t*40004u)>>29;
	static u64 table[]={
		0x10204ull,
		0x20820ull,
		0x4210000000ull,
		0x10204ull,
		0x820020000ull,
		0x20020800ull,
		0x20820000000ull,
		0x10204ull,
	};

    netter mit

    __Z4testy:
LFB991:
	pushl	%ebp
LCFI2:
	movl	%esp, %ebp
LCFI3:
	pushl	%ebx
LCFI4:
	movl	8(%ebp), %ebx
	movl	12(%ebp), %ecx
	movl	%ecx, %eax
	xorl	%ebx, %eax
	leal	(%eax,%eax,4), %edx
	leal	(%edx,%edx,4), %edx
	leal	(%edx,%edx,4), %edx
	leal	(%edx,%edx,4), %edx
	sall	$4, %edx
	leal	(%edx,%eax), %eax
	sall	$2, %eax
	shrl	$29, %eax
	xorl	__ZZ4testyE5table(,%eax,8), %ebx
	xorl	__ZZ4testyE5table+4(,%eax,8), %ecx
	orl	%ecx, %ebx
	sete	%al
	popl	%ebx
	leave
	ret
LFE991:
    0
  • ?

    Wow, Volkard, du sollst mir nicht das ganze Programm schreiben 😃 .Ich will auch noch was machen. Naja, das was ich jetzt mal versuche, sieht in etwa so aus(Hoffentlich ist das kein kompletter Blödsinn):

    mov       eax,dword ptr [_Feld1]
	mov       edx,dword ptr [_Feld1+4]
	not       eax
	not       edx

	test      eax,536870912
	jnz       @7
	test      edx,520
	jz		  @exittrue

@7:
	test      eax,537001984
	jnz       @8
	test      edx,8
	jz		  @exittrue
@8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue

@11:
	test      eax,537001984
	jnz       @exitfalse
	test      edx,8
	jz		  @exittrue

    Das entspräche diesem C-Code (Hoffe ich):

    if(!(x & 0x20820000000i64 &&
			x & 0x820020000i64 &&
			x & 0x20020800i64 &&
			x & 0x20820i64 &&
			x & 0x10204i64 &&
			x & 0x4210000000i64)) return true;
    0
  • V

    Franz von und zu Assisi schrieb:

    @8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue

    Damit begehst DU meinen Fehler, fürchte ich, und Du testest nicht mehr, ob unter anderem diese 3 Bits gesetzt sind, sondern ob nur genau diese 3 Bits gesetzt sind.

    0
  • ?

    volkard schrieb:

    Franz von und zu Assisi schrieb:

    @8:
	test      eax,537004032
	jz        @exittrue

@9:
	test      eax, 133152
	jz        @exittrue

@10:
	test      eax,66052
	jz        @exittrue

    Damit begehst DU meinen Fehler, fürchte ich, und Du testest nicht mehr, ob unter anderem diese 3 Bits gesetzt sind, sondern ob nur genau diese 3 Bits gesetzt sind.

    Ne, meine Lösung müsste richtig sein. Ich hab sie mit allen relevanten Spielstellungen getestet. Ich hab meinen Assembler-Code auch auf Laufzeit getestet, erstaunlicherweise ist der aber langsamer als der reine C-Code. Daher gehe ich davon aus, dass der Assembler-Code, den der Compiler ausspuckt, noch nicht optimiert ist, die Optimierung also zu einem späteren Zeitpunkt erfolgt. Daher macht eine Optimierung von Hand meiner Meinung nach keinen Sinn mehr (außer im C-Code), obwohl meine Lösung sicherlich noch nicht optimal ist.
    Trotzdem hat Campers Idee

    bool SpielBeenden1()
{
    i64 x = ~Feld1;
    return !( x & 0x20820000000i64 && x & 0x00820020000i64 && x & 0x00020020800i64 && x & 0x00000020820i64 && x & 0x00000010204i64 && x & 0x04210000000i64 );
}

    einiges gebracht (5-10% Laufzeitvorteil). Und damit kann ich ganz gut leben. Meiner Meinung nach kann der Thread jetzt auch geschlossen werden.

    Vielen Dank an alle Helfer

    0
  • C
    Mod

    volkard schrieb:

    EDIT: Alles falsch! Du sucht ja nicht bestimmte Werte, sondern welche der vielen Bitmaskee paßt. Alles vergebens. Ich bin ja soo doof.

    Der Ansatz ist vielleicht trotzdem nicht so doof. Jedenfalls die Faltung könnte brauchbar sein:
    Wenn im echten Programm so wie hier nur ein Teil aller bits überhaupt an der Ergebnisfindung teilnimmt (einfach alle Masken ver-or-en), könnte man den Rest vergessen und aus einem 64bittigen Problem z.B. wie hier ein 12bittiges machen. Klein genug für eine lookup-table.

    0
  • ?

    camper schrieb:

    Der Ansatz ist vielleicht trotzdem nicht so doof. Jedenfalls die Faltung könnte brauchbar sein:
    Wenn im echten Programm so wie hier nur ein Teil aller bits überhaupt an der Ergebnisfindung teilnimmt (einfach alle Masken ver-or-en), könnte man den Rest vergessen und aus einem 64bittigen Problem z.B. wie hier ein 12bittiges machen. Klein genug für eine lookup-table.

    Alle diese Konstanten bestehen aus genau drei gesetzten Bits. Das mit der lookup-Tabelle habe ich aber nicht so ganz verstanden

    0
  • C
    Mod

    Franz von und zu Assisi schrieb:

    Alle diese Konstanten bestehen aus genau drei gesetzten Bits. Das mit der lookup-Tabelle habe ich aber nicht so ganz verstanden

    Wie viele Bits sind gesetzt, wenn alle Konstanten or-verknüpft werden?

    0
  • ?

    camper schrieb:

    Wie viele Bits sind gesetzt, wenn alle Konstanten or-verknüpft werden?

    Das kann man so nicht ohne weiteres sagen, das hängt von den einzelnen Cases der Switch-Anweisung ab. Ich weiß jetzt nicht genau auf was du hinaus willst, ich poste einfach mal den ersten Teil meiner Funktion:

    Boolean SpielBeenden1(void)
{
	const __int64 x = ~Feld1;
    switch(Hoehe[3])
    {
		case 0:
			if(!(x & 0x20820000000i64 &&
			x & 0x820020000i64 &&
			x & 0x20020800i64 &&
			x & 0x20820i64 &&
			x & 0x10204i64 &&
			x & 0x4210000000i64)) return true;
            break;
        case 1:
			if(!(x & 0x20008100i64 &&
			x & 0x10410i64 &&
			x & 0x10410000000i64 &&
			x & 0x2108000000i64 &&
			x & 0x108020000i64 &&
			x & 0x10010400i64 &&
			x & 0x8102i64 &&
			x & 0x410010000i64)) return true;
            break;
		case 2:
			if(!(x & 0x810004000i64 &&
			x & 0x4010800i64 &&
			x & 0x8208000000i64 &&
			x & 0x208008000i64 &&
			x & 0x8008200i64 &&
			x & 0x8208i64 &&
			x & 0x84010000i64 &&
			x & 0x10004080i64 &&
			x & 0x4081i64 &&
			x & 0x1084000000i64)) return true;
            break;
        case 3:
.
.
.
.
.
        case 5:
			if(!(x & 0x380000i64 &&
			x & 0x8102000000i64 &&
			x & 0x2108i64 &&
			x & 0x1041000000i64 &&
			x & 0x41001000i64 &&
			x & 0x1001040i64 &&
			x & 0x1041i64)) return true;
            break;
        default:
            break;
}

switch(Hoehe[4])
{
.
.
.
.
}
    0
  • ?

    Darf man fragen wie das Spiel heißt? 😃

    0
  • N

    Der Fluch der Mumie... 🙄

    0
Anmelden zum Antworten