A volte gli umani ancora…
April 1st, 2006
Ci sono alcuni tipi di ottimizzazione che per un
umano sono “evidenti”, per una macchina no. Trovo molto interessanti i problemi nel campo della correttezza (ovvero cercatr di insegnare ad un computer a dimostrare se un sorgente è o meno corretto, se presenta certi errori, in generale capire cosa fa). Il problema gemello è
quello dell’ottimizzazione (si tratta per il computer di capire cosa fa
il tuo codice e di modificarlo in uno equivalente più veloce)
Per esempio prendiamo questa funzione:
int func(){
int i;
int x = 2<<10;
for ( i=0; i < MAX; ++i){
if (i>= 0 && sqrt(i) >= 0)
x/=i;
}
}
Ad occhio si vede benissimo che il check dell’if è oltremodo pesante.
*sai* che i è sempre maggiore o uguale di 0. Si può anche farne una
dimostrazione formale abbastanza agevole.
In pratica la guardia dell’if è inutile. Il check sul >= 0 non serve e
meno ancora sqrt. Nessuno dei due ha effetti collaterali (per il primo
si vede, è facile, ma per il secondo bisogna sapere come è fatta sqrt, a
sboccio non si modo di sapere che non setta un globale ad i, che stampa qualcosa o che ha un altro effetto collaterale, per cui
effettivamente non si può semplicemente eliminarla senza cambiare la
semantica del programma.
Dicevo. Senza ottimizzare, questo compila tenendo tutta la guardia
dell’if:
L3:
cmpl $0, -16(%ebp)
js L4
cvtsi2sd -16(%ebp), %xmm0
sqrtsd %xmm0, %xmm0
movapd %xmm0, %xmm1
leal LC0-"L00000000001$pb"(%ebx), %eax
movsd (%eax), %xmm0
ucomisd %xmm0, %xmm1
jae L7
jmp L4
C'è il primo confronto i>= 0
cmpl $0, -16(%ebp)
js L4
e c’è pure il confronto con la radice (sta usando dei registri mmx).
Bene… tutta la sezione L3 in effetti si può semplicemente togliere.
Ora in questo caso è semplicemente banale fare l’ottimizzazione. E in
effetti tutto il codice completo per la funzione di cui sopra
ottimizzato è:
.text
.globl _func
_func:
pushl %ebp
movl %esp, %ebp
xorl %eax, %eax
L2:
addl $1, %eax
cmpl $10, %eax
jne L2
popl %ebp
ret
.subsections_via_symbols
Lungo da solo quanto il controllo. E questo è quasi esattamente quello che
avrebbe scritto un programmatore:
Piccolo preludio, azzera il primo registro. Poi nel loop, incrementa il
primo registro (addl $1, %eax), confrontalo con il valore guardia
(nel sorgente MAX era una define a 10 ; cmpl $10, %eax), se è minore o uguale torna a L2 (jne L2). Esci.
Ha ottimizzato perfino x/=i. Siccome vede che con x non ci faccio nulla,
allora dice: che lo calcolo a fare? Fa solo il ciclo. Fosse stato più
furbo non avrebbe fatto manco quello. Stupido io a prendere l’esempio fatto male.
Modifichiamo quindi la funzione in modo che ritorni x, e che quindi x vada calcolato.
Ecco… vediamo che a questo punto non è più tanto furbo:
.text
.globl _func
_func:
pushl %ebp
movl %esp, %ebp
pushl %ebx
xorl %ecx, %ecx
movl $2048, %eax
pxor %xmm1, %xmm1
jmp L2
L3:
testl %ecx, %ecx
js L11
L2:
cvtsi2sd %ecx, %xmm0
sqrtsd %xmm0, %xmm0
ucomisd %xmm1, %xmm0
jb L11
cltd
idivl %ecx
L11:
addl $1, %ecx
cmpl $9, %ecx
jle L3
popl %ebx
popl %ebp
ret
.subsections_via_symbols
Ricompare la radice quadrata ( sqrtsd %xmm0, %xmm0 ). Il
programmatore che avesse scritto l’assembly a mano avrebbe scritto [
nel caso in cui questo loop sia molto ricorrente ] un codice
significativamente più veloce.
Ammesso che questo mio esempio è del tutto cretino, è vero che il
compilatore in genere sa su quale architettura certe istruzioni sono più
sgamate, ma è vero ancora che le tecniche per le dimostrazioni formali
sono ancora relativamente poco usate (anche perchè suddette
dimostrazioni dilatano di moltissimo il tempo di compilazione, sono
*molto* difficili da scrivere, e rischiano di portare bachi su bachi con
errori minimi). Questo è parte di quasi tutti gli ambienti, non solo del
gcc.
Come dire… l’umano sulle cose “furbe” resta più furbo, anche se sulla forza bruta non ha speranza.
Leave a Reply