wpc115

TomasRiker

Ich habe mir von VC++ mal den Assembler-Code von der optimierten Version ausgeben lassen. Dort ist kein "mul" oder "imul" zu finden. Es ist mir ehrlich gesagt rätselhaft, wie dieser Code überhaupt funktionieren kann (tut er aber!).

00000	8b 4c 24 04	 mov	 ecx, DWORD PTR _t1$[esp-4]
  00004	8b 54 24 08	 mov	 edx, DWORD PTR _t2$[esp-4]
  00008	0f be 02	 movsx	 eax, BYTE PTR [edx]
  0000b	56		 push	 esi
  0000c	0f be 31	 movsx	 esi, BYTE PTR [ecx]
  0000f	2b c6		 sub	 eax, esi
  00011	0f be 71 01	 movsx	 esi, BYTE PTR [ecx+1]
  00015	8d 04 80	 lea	 eax, DWORD PTR [eax+eax*4]
  00018	d1 e0		 shl	 eax, 1
  0001a	2b c6		 sub	 eax, esi
  0001c	0f be 72 01	 movsx	 esi, BYTE PTR [edx+1]
  00020	03 c6		 add	 eax, esi
  00022	0f be 71 03	 movsx	 esi, BYTE PTR [ecx+3]
  00026	8d 04 40	 lea	 eax, DWORD PTR [eax+eax*2]
  00029	d1 e0		 shl	 eax, 1
  0002b	2b c6		 sub	 eax, esi
  0002d	0f be 72 03	 movsx	 esi, BYTE PTR [edx+3]
  00031	03 c6		 add	 eax, esi
  00033	0f be 71 04	 movsx	 esi, BYTE PTR [ecx+4]
  00037	8d 04 80	 lea	 eax, DWORD PTR [eax+eax*4]
  0003a	d1 e0		 shl	 eax, 1
  0003c	2b c6		 sub	 eax, esi
  0003e	0f be 72 04	 movsx	 esi, BYTE PTR [edx+4]
  00042	03 c6		 add	 eax, esi
  00044	0f be 71 06	 movsx	 esi, BYTE PTR [ecx+6]
  00048	0f be 49 07	 movsx	 ecx, BYTE PTR [ecx+7]
  0004c	8d 04 40	 lea	 eax, DWORD PTR [eax+eax*2]
  0004f	d1 e0		 shl	 eax, 1
  00051	2b c6		 sub	 eax, esi
  00053	0f be 72 06	 movsx	 esi, BYTE PTR [edx+6]
  00057	0f be 52 07	 movsx	 edx, BYTE PTR [edx+7]
  0005b	03 c6		 add	 eax, esi
  0005d	8d 04 80	 lea	 eax, DWORD PTR [eax+eax*4]
  00060	d1 e0		 shl	 eax, 1
  00062	2b c1		 sub	 eax, ecx
  00064	03 c2		 add	 eax, edx
  00066	5e		 pop	 esi

ERROR

EDIT: mal genau überprüft, so sieht auch mein asm aus

cu

TomasRiker

Aber wie funktioniert dieser Code?
Wo stehen die Multiplikation mit 36000, 3600, 600, 60 und 10?

EDIT:
Witzig ist Folgendes: wenn ich mit 36001 multipliziere, steht auf einmal folgendes im Code:

imul	 edi, 36001

Irgendwie produziert der Compiler aus der 10 die 60, aus der 60 die 600 usw.. Echt nicht übel, hätte ich nicht gedacht, dass der so gut optimiert!

ERROR

kenn mich mit asm nicht so besonders aus, aber habe gerade per hilfe rausgefunden, dass multiplikationen wohl

"als Folge von Schiebe- und LEA-Anweisungen zu implementieren" sind

hatte in der hilfe einfach mal nach "lea" gesucht

hier ein bsp. aus der hilfe!!:

<ZITAT>

Das nachfolgende Codebeispiel zeigt den Unterschied zwischen den Optionen Weniger Code bevorzugen (/Os) und Schnellen Code bevorzugen (/Ot):

/* differ.c
Dieses Programm implementiert einen Multiplikations-
Operator.
Mit /Os kompilieren, um Multiplizieren explizit als Multiplizieren zu implementieren.
Mit /Ot kompilieren, um als Folge von Schiebe- und LEA-Anweisungen zu implementieren.
*/
int differ(int x)
{
return x * 71;
}

Der nachfolgende Ausschnitt aus dem Maschinen-Code zeigt, daß der Compiler den Multiplikationsausdruck in der Return-Anweisung explizit als eine Multiplikation implementiert, um eine kurze, aber langsamere Codefolge zu erzeugen, wenn bei der Kompilierung von DIFFER.C weniger Code bevorzugt wird (/Os):

mov eax, DWORD PTR _x$[ebp]
imul eax, 71 ; 00000047H

Wenn bei der Kompilierung von DIFFER.C dagegen Geschwindigkeit bevorzugt wird (/Ot), implementiert der Compiler den Multiplikationsausdruck in der Return-Anweisung als eine Folge von Schiebe- und LEA-Anweisungen, um eine schnelle, aber längere Codefolge zu erzeugen:

mov eax, DWORD PTR _x$[ebp]
mov ecx, eax
shl eax, 3
lea eax, DWORD PTR [eax+eax*8]
sub eax, ecx

</ZITAT>

Interessant ist, wie er erst eax = t2[0]-t1[0] berechnet, was ja durchaus nicht verkehrt ist, dann aber eax als Zeiger verwendet (lea eax, DWORD PTR [eax+eax*4]). Kann aber auch sein, dass ich mich verguckt habe, AT&T Syntax ist doch ein wenig anders.

ERROR

ah jetzt habe ich das einigermaßen verstanden:

shl eax, 3 verschiebt bitweise nach links(3 stellen)
und lea ... ist dann eine multiplikation
(Skalierung eines Registers; Register können nur mit den Werten 1, 2, 4 oder 8 skaliert werden.)

also nehmen wir an, wir multiplizieren 3 mit der 71

3= 00000011
um 3 nach links:

24=00011000

und jetzt die lea anweisung

24+24*8 = 216

jetzt noch sub:

216-3 = 213 =3*71

ist ja cool

und jetzt bei us:

lea eax, DWORD PTR [eax+eax*4]
00018 d1 e0 shl eax, 1

= mal zehn

cu

tag

ERROR schrieb:

also ich habe 6- 5+ und 5*

also ein + weniger

aber den unterschied macht auf jeden fall der zugriff auf die einzellnen zahlen
da hebe ich die unterschiede meiner versuche drastisch gemerkt

cu

Das hatte ich im ersten Versuch auch. Im zweiten Versuch habe ich 8 Subtraktionen, 5 Multiplikationen, 6 bitweise UND, ein paar Shifts und 4 Additionen.
Damit bin ich auf meinem PC bei 4000000000 Aufrufen ganze 4,5 Sekunden schneller

00000	8b 4c 24 08	 mov	 ecx, DWORD PTR _t2$[esp-4]
  00004	8b 54 24 04	 mov	 edx, DWORD PTR _t1$[esp-4]
  00008	56		 push	 esi
  00009	8b 01		 mov	 eax, DWORD PTR [ecx]
  0000b	8b 32		 mov	 esi, DWORD PTR [edx]
  0000d	2b c6		 sub	 eax, esi
  0000f	8b 72 04	 mov	 esi, DWORD PTR [edx+4]
  00012	05 10 10 10 10	 add	 eax, 269488144		; 10101010H
  00017	33 d2		 xor	 edx, edx
  00019	89 44 24 08	 mov	 DWORD PTR _first$[esp], eax
  0001d	8a d4		 mov	 dl, ah
  0001f	25 ff 00 00 00	 and	 eax, 255		; 000000ffH
  00024	8b 49 04	 mov	 ecx, DWORD PTR [ecx+4]
  00027	2b ce		 sub	 ecx, esi
  00029	5e		 pop	 esi
  0002a	8d 04 80	 lea	 eax, DWORD PTR [eax+eax*4]
  0002d	81 c1 10 10 10
	10		 add	 ecx, 269488144		; 10101010H
  00033	d1 e0		 shl	 eax, 1
  00035	03 c2		 add	 eax, edx
  00037	89 4c 24 08	 mov	 DWORD PTR _second$[esp-4], ecx
  0003b	81 e1 ff 00 00
	00		 and	 ecx, 255		; 000000ffH
  00041	8d 14 40	 lea	 edx, DWORD PTR [eax+eax*2]
  00044	33 c0		 xor	 eax, eax
  00046	8a 44 24 07	 mov	 al, BYTE PTR _first$[esp-1]
  0004a	8d 04 50	 lea	 eax, DWORD PTR [eax+edx*2]
  0004d	8d 14 80	 lea	 edx, DWORD PTR [eax+eax*4]
  00050	8d 04 51	 lea	 eax, DWORD PTR [ecx+edx*2]
  00053	33 c9		 xor	 ecx, ecx
  00055	8a 4c 24 0a	 mov	 cl, BYTE PTR _second$[esp-2]
  00059	8d 04 40	 lea	 eax, DWORD PTR [eax+eax*2]
  0005c	8d 04 41	 lea	 eax, DWORD PTR [ecx+eax*2]
  0005f	8d 14 80	 lea	 edx, DWORD PTR [eax+eax*4]
  00062	33 c0		 xor	 eax, eax
  00064	8a 44 24 0b	 mov	 al, BYTE PTR _second$[esp-1]
  00068	8d 84 50 10 2b
	f6 ff		 lea	 eax, DWORD PTR [eax+edx*2-644336]

Was mir allerdings Kopfschmerzen macht, ist das Abfangen von Überläufen: von 01:30:00 bis 02:00:00 sind es schließlich nicht 00:70:00 (und ich habe meinen Vorschlag schon abgeschickt )

/Edit: Kommando zurück. Das wird ja nicht 00:70:00, sondern 01:-30:00 und damit passt es wieder, stimmt's?

volkard

tag schrieb:

Im zweiten Versuch habe ich 8 Subtraktionen, 5 Multiplikationen, 6 bitweise UND, ein paar Shifts und 4 Additionen.

ich bin sogar auf drei multiplikationen runter. dazu 4 shifts, 6 subtraktionen und 5 additionen und zu viele zuweisungen.
aber schneller wird's dadurch auch nicht.

virtuell Realisticer

Wie schnell ist euer Code denn?

mfg
v R

volkard

virtuell Realisticer schrieb:

Wie schnell ist euer Code denn?

was bringt es dir, wenn ich zeit und meinen prozessor sage? damit kannste die sache mit deinem prozessor nicht vergleichen.

ERROR

ok

virtuell Realisticer

volkard schrieb:

virtuell Realisticer schrieb:

Wie schnell ist euer Code denn?

was bringt es dir, wenn ich zeit und meinen prozessor sage? damit kannste die sache mit deinem prozessor nicht vergleichen.

Da hast auch war, war auch nur interessenhalber

@ERROR: Stell den Code am besten erst rein, wenn die Aufgabe vorbei ist ;).

mfg
v R

stahl

hm ERROR, hab das vorhin ganz vergessen.. aber bei deinem code is noch bissel was drin.. so optimal gekürzt war das nicht

stahl

man is' das lange her..

int wpc116(char *t1, char *t2) {
	return  t2[7]-t1[7]+10*(t2[6]-t1[6]+6*(t2[4]-t1[4]+10*(t2[3]-t1[3]+6*(t2[1]-t1[1]+10*(t2[0]-t1[0])))));
}

nach jahren mal 'ne lösung posten

hoffe das stimmt auch, hab das nu' nicht mehr getestet