Optimisation : Trouver la valeur max d'un tableau

Pour discuter de l'assembleur
ker2x
Messages : 61
Inscription : dim. 11/mai/2008 7:27

Optimisation : Trouver la valeur max d'un tableau

Message par ker2x »

J'ai le code purebasic suivant :

Code : Tout sélectionner

Global Dim exposure(#screenSize2)
Procedure findMaxExposure()
  maxexposure = 0
  For i = 0 To #screenSize2
    If (exposure(i) > maxexposure)
      maxexposure = exposure(i)
    EndIf
  Next i
EndProcedure
Simple et... efficace ?

Qui genere le code asm suivant (option : CPU with SSE2)

Code : Tout sélectionner

; Procedure findMaxExposure()
macro {MP4
_Procedure4:
	PUSH	 rbp
	PUSH	 r15
PS4=80
	XOR	 rax,rax
	PUSH	 rax
	PUSH	 rax
	SUB	 rsp,40                                                                                                                                                                                                                                    
; maxexposure = 0
	MOV	 qword [v_maxexposure],0
; For i = 0 To #screenSize2
	MOV	 qword [rsp+40],0
_For15:
	MOV	 rax,1000000
	CMP	 rax,qword [rsp+40]
	JL	 _Next16
; If (exposure(i) > maxexposure)
	MOV	 r15,qword [rsp+40]
	MOV	 rbp,qword [a_exposure]
	SAL	 r15,3
	MOV	 r15,qword [rbp+r15]
	CMP	 r15,qword [v_maxexposure]
	JLE	 _EndIf18
; maxexposure = exposure(i)
	MOV	 r15,qword [rsp+40]
	MOV	 rbp,qword [a_exposure]
	SAL	 r15,3
	PUSH	 qword [rbp+r15]
	POP	 rax
	MOV	 qword [v_maxexposure],rax
; EndIf
_EndIf18:
; Next i
_NextContinue16:
	INC	 qword [rsp+40]
	JNO	 _For15
_Next16:
; EndProcedure
	XOR	 rax,rax
_EndProcedure5:
	ADD	 rsp,56
	POP	 r15
	POP	 rbp
	RET
}
Berk berk berk !
En purebasic, je vois difficillement comment faire mieux.
En asm... je trouve que cela a un peu trop d'instruction a mon gout.

Cette partie du code n'est pas la plus critique de mon application, mais il me semblai qu'elle serai la plus simple a transformer en InlineASM ... jusqu'a que je vois le code genéré ...

Une idée ?
Fred
Site Admin
Messages : 2649
Inscription : mer. 21/janv./2004 11:03

Re: Optimisation : Trouver la valeur max d'un tableau

Message par Fred »

Elle prend combien de % de ton temps global ?
ker2x
Messages : 61
Inscription : dim. 11/mai/2008 7:27

Re: Optimisation : Trouver la valeur max d'un tableau

Message par ker2x »

Je sais pas exactement, certainement moins de 1%
C'est vraiment pas une partie critique.

Mais je voulais commencer a ASMifier mon code ... j'ai pensé que ca serai le plus simple... Mais vu le code... carremenet pas !!!
Soit le compilo fait pas ce qu'il faut, soit c'est vraiment aussi complexe que ca de trouver une valeur maxi dans un tableau et... tant pis.

Ma partie a optimiser pour de vrai ca sera plutot

Code : Tout sélectionner

  For i = 0 To #bailout
    xnew.d = (x.d * x.d) - (y.d * y.d) + x0
    ynew.d = 2 * (x.d * y.d) + y0
    If ((dodraw.i <> 0) And (i > #miniter))
      ix = Int(#screenSize * (xnew.d + 2.0) / 4.0)
      iy = Int(#screenSize * (ynew.d + 2.0) / 4.0)
      If ((ix>= 0) And (iy >= 0) And (ix < #screenSize) And (iy < #screenSize))
        exposure(ix*#screenSize+iy) = exposure(ix*#screenSize+iy) + 1
      EndIf
    EndIf
    
    If ((xnew.d*xnew.d + ynew.d*ynew.d) > 4)
      ;Debug 1
      ProcedureReturn 1
    EndIf
    x.d = xnew.d
    y.d = ynew.d
  Next i
Coté algo pour commencer (s'assurer que c'est bien ok).
Puis coté ASM (SSE3 ?)

Le truc, surtout, c'est que j'ai surtout envie de faire de l'asm... pour le plaisir d'en faire :)

Je vois des broutille facile a changer.
Par exemple, sauf erreur de ma part :

Code : Tout sélectionner

; y.d = 0.0
	FLD	 qword [D1]
	FSTP	 qword [rsp+48]
pour se transformer en :

Code : Tout sélectionner

FLDZ
FSTP	 qword [rsp+48]
fld1, fldz, fldl2t, fldl2e, fldpi, fldlg2 and fldln2 load the commonly used contants onto the FPU register stack. The loaded constants are +1.0, +0.0, log210, log2e, π, log102 and ln 2 respectively. These instructions have no operands.

Par contre c'est vraiment une broutille :)

Edit : sauf que visiblement FLD = 1 cycle. FLDZ = 2 cycle ...
ker2x
Messages : 61
Inscription : dim. 11/mai/2008 7:27

Re: Optimisation : Trouver la valeur max d'un tableau

Message par ker2x »

Ouai ... bon... vraiment galere d'optimiser le code asm genéré par purebasic :)
Il est quand meme bien foutu !!

Code : Tout sélectionner

; xnew.d = (x.d * x.d) - (y.d * y.d) + x0
	FLD	 qword [rsp+72]
	FMUL	 qword [rsp+72]
	FLD	 qword [rsp+80]
	FMUL	 qword [rsp+80]
	FSUBP	 st1,st0
	FADD	 qword [rsp+PS0+0]
	FADD	 qword [D1]
	FSTP	 qword [rsp+64]
; ynew.d = 2 * (x.d * y.d) + y0
	FLD	 qword [rsp+72]
	FMUL	 qword [rsp+80]
	FMUL	 qword [D2]
	FADD	 qword [rsp+PS0+8]
	FADD	 qword [D1]
	FSTP	 qword [rsp+88]
C'est ma partie de code la plus critique.
Je vois pas trop comment optimiser ca a partir du moment ou il utilise la FPU.

Des gens ont deja codé des fractales de mandelbrot en asm : http://www.codeproject.com/KB/recipes/fractalssse.aspx
La veritable optimisation asm possible, serait d'utiliser les instructions SSE ... Et encore dans mon cas c'est carrement pas gagné.

Je vais plutot bidouiller dans le code purebasic et voir le resultat asm genéré pour decider de la meilleure solution.
Fred
Site Admin
Messages : 2649
Inscription : mer. 21/janv./2004 11:03

Re: Optimisation : Trouver la valeur max d'un tableau

Message par Fred »

Le code généré est rarement optimal, mais il est souvent dans la moyenne. Il vaut souvent mieux tenter de modifier ton algo pour en trouver un plus performant en PureBasic et en dernier recours essayer d'optimiser en ASM.
ker2x
Messages : 61
Inscription : dim. 11/mai/2008 7:27

Re: Optimisation : Trouver la valeur max d'un tableau

Message par ker2x »

J'ai fini par optimiser tout ca a coup de SSE et d'utilisation maline des registre SSE dans la boucle :)

pour repondre a la premiere question de ce thread, il existe une instruction SSE4 pour aider a la recherche d'une valeur max d'un tableau.
Mais comme je n'ai pas de cpu qui gere le SSE4 ... j'peux pas tester :)
Répondre