Le avventure di un Pythonista in Schemeland /5

Il sottotitolo di questa puntata potrebbe essere “I pericoli del
benchmark”. I benchmark sono utili negli articoli, in quanto
suscitano discussioni e accesi dibattiti e costituiscono
un trucco strategico per attirarsi lettori.
D’altra parte, il pericolo maggiore dei benchmark è quello di
crederci: parafrasando Mark Twain there are lies, damned lies, and
benchmarks
. Questo vuol dire non soltanto che i benchmark lasciano il
tempo che trovano perché la realtà è diversa dal benchmark, ma anche
che è facilissimo sbagliare un benchmark o non interpretarlo
correttamente. In questa puntata mostrerò alcuni dei pericoli
inerenti al benchmark del fattoriale mostrato nella puntata precedente,
che pure potrebbe sembrare banale ed inoppugnabile. Se un benchmark
così semplice è così delicato, vi lascio immaginare che succede per
benchmark più complessi. L’unico vantaggio dei benchmark è che spesso e
volentieri fanno capire quanto siano sbagliati i pregiudizi che
abbiamo sull’efficienza di una certa soluzione rispetto all’efficienza
di un’altra soluzione.

Attenzione ai tempi morti

tartaruga.jpg

Un pericolo abbastanza ovvio nei benchmark è quello dei tempi morti.
Siccome tipicamente i benchmark vengono eseguiti chiamando N volte
una funzione, il tempo speso nel loop va sottratto dal tempo effettivo
di calcolo. Se la funzione su cui si fa il benchmark non è troppo veloce,
di solito il tempo speso nelle chiamate spurie è trascurabile rispetto al
tempo di calcolo effettivo, ma in certi casi non è così.

Nell’esempio del fattoriale il tempo morto si può stimare come il
tempo speso a calcolare il fattoriale di zero (calcolo in cui non vi
è nessuna moltiplicazione, tutto il tempo è speso nel loop).
Sul mio sistema è di 0.23 secondi per dieci
milioni di cicli, da confrontare con i 3.08 secondi spesi a calcolare
il fattoriale di 7. Non è troppo grande, ma apprezzabile. Nel caso
di funzioni particolarmente veloci, il tempo morto può falsare
complementamente i risultati del benchmark.

Per esempio add1 è la funzione che incrementa un numero di una
unità ed è estremamente veloce. Il tempo per sommare 1+1 dieci milioni
di volte è

> (time (call 10000000 add1 1))
running stats for (call 10000000 add1 1):
no collections
307 ms elapsed cpu time, including 0 ms collecting
308 ms elapsed real time, including 0 ms collecting
24 bytes allocated

I due terzi di questo tempo sono tempo morto, speso nelle chiamate
alla funzione ausiliaria call, come si vede misurando
il tempo speso a chiamare dieci milioni di volte una funzione
che non fa nulla:

> (define (identity x)  x)
> (time (call 10000000 identity 1))
running stats for (call 10000000 do-nothing):
no collections
214 ms elapsed cpu time, including 0 ms collecting
216 ms elapsed real time, including 0 ms collecting
16 bytes allocated

In un benchmark serio bisogna stare attenti a sottrarre i tempi morti, se questi
sono rilevanti. Meglio ancora è ridurre i tempi morti, se possibile. In una
puntata futura vedremo come questo sia realizzabile in pratica
utilizzando una macro nvece della funzione ausiliaria call,
che è relativamente inefficiente.

Attenzione agli imbrogli

il+gatto+e+la+volpe.jpg

Il problema dei tempi morti è abbastanza ovvio; d’altra parte spesso i
benchmark sono soggetti a sottigliezze meno ovvie. In questo paragrafo vi
farò vedere come sia possibile ottenere prestazioni enormemente
superiori imbrogliando. Consideriamo ancora l’esempio del fattoriale,
ma questa volta usiamo Chicken Scheme come linguaggio di
implementazione. Chicken è un compilatore che converte codice Scheme
in codice C e quindi può sfruttare tutte le ottimizzazioni e gli
sporchi trucchi del compilatore C sottostante. In particolare Chicken
ha una modalità benchmark in cui si disabilitano tutti i check di
consistenza, si assume di avere sempre interi a 32 bit e si abilita
l’ottimizzazione -O3 del gcc. Compilando il
benchmark del fattoriale in tale modalità si ottengono delle performance
impressionanti:

$  csc -Ob fact.scm # csc = Chicken Scheme Compiler
$ ./fact 7
./fact 7
0.176 seconds elapsed
0 seconds in (major) GC
0 mutations
1 minor GCs
0 major GCs
result:5040

Siamo sedici volte più veloci di Ikarus e CENTOSETTANTATRE volte più veloci
di Python!

Peccato solo che non funzioni: quando il fattoriale diventa abbastanza
grande (più di 2^31) Chicken (o meglio il C sottostante) comincia a dare
valori senza senso. Fino a 12! tutto va bene:

$ ./fact 12 # this is smaller than 2^31, perfectly correct
0.332 seconds elapsed
0 seconds in (major) GC
0 mutations
1 minor GCs
0 major GCs
result:479001600

A partire da 13! iniziano le sorprese:

$ ./fact 13 # the correct value is 6227020800, larger than 2^31
0.352 seconds elapsed
0 seconds in (major) GC
0 mutations
1 minor GCs
0 major GCs
result:-215430144

Visto che succede a imbrogliare? 😉

Attenzione a non ottimizzare troppo

exclamation-mark.jpg

In questo ultimo paragrafo mostrerò il lato positivo dei benchmark,
facendo vedere come possono essere impiegati utilmente per evitarci
dell’inutile lavoro di ottimizzazione.

Come tutti dovrebbero sapere è sempre meglio non
ottimizzare troppo, perché si rischia di sprecare lavoro, specialmente
con i compilatori moderni che spesso sono più intelligenti di
noi. Tanto per dare un esempio, proviamo ad ottimizzare il
benchmark del fattoriale sostituendo
l’espressione con la closure
(call 10000000 (lambda () (fac n))) con l’espressione senza closure
(call 10000000 fac n). In teoria ci aspetteremmo
un miglioramento delle prestazione in quanto c’è un livello di indirezione
in meno (chiamiamo direttamente fac invece di chiamare una closure
che chiama fac) ed infatti questo è quello che succede con Ikarus:
per n=7 impiega 3.07 secondi con la closure e 2.95 secondi senza.
In Chicken, invece, in modalità benchmark, succede un disastro:

$  csc -Ob fact.scm
$ ./fact 7
1.631 seconds elapsed
0.011 seconds in (major) GC
0 mutations
1881 minor GCs
23 major GCs
result:5040

Il programma è quasi 10 volte più lento! Tutto il tempo viene speso
nel garbage collector, che prima invece non veniva minimamente
sfruttato. C’è da notare che questo comportamento è proprio
soltanto del benchmark mode: compilando con
le opzioni di default non si vedono differenze molto significative nei
tempi di esecuzione, che comunque sono molto superiori (7.07 secondi
con la closure contro 6.88 secondi senza la closure:
con le opzioni standard usare la closure vi penalizza leggermente, come
vi aspettereste, mentre in benchmark mode vi migliora le performance
di dieci volte!). Ho chiesto spiegazioni a Felix Winkelmann, l’autore
di Chicken, e vi riporto la sua risposta testuale:

In the first case, the compiler can see that all references to fac
are call sites: the value of “fac” is only used in positions where
the compiler can be absolutely sure it is a call. In the second case
the value of fac is passed to “call” (and the compiler is not clever
enough to trace the value through the execution of “call” – this
would need flow analysis). So in the first case, a specialized
representation of fac can be used (“direct” lambdas, i.e. direct-style
calls which are very fast).

Compiling with “-debug o” and/or “-debug 7” can also be very instructive.

Questo dovrebbe illustrare sufficientemente il fatto che
i benchmark sono bestie delicatissime, dove cambi apparentemente
insignificanti possono completamente falsare i numeri che si
ottengono. Insomma, state attenti ai benchmark a meno che voi
non siate degli esperti di compilatori (e in quel caso state doppiamente
attenti! ;).

Ricorsione e iterazione

Di solito i linguaggi imperativi non supportano troppo bene la ricorsione
(nel senso che ci sono possono essere problemi  di recursion limit
e di efficienza). In questi
linguaggi è spesso conveniente convertire problemi ricorsivi in problemi
iterativi. Allo scopo conviene prima scrivere il problema ricorsivo
in forma di tail call, eventualmente aggiungendo delle variabili
ausiliari che fungono da accumulatori. A questo punto, la riscrittura
in termini di un ciclo while è banale.
Per esempio, implementare il fattoriale in maniera iterativa in Python
ha i suoi vantaggi; se fate girare lo script

# fact_it.py
import sys, timeit

def fact(x):
acc = 1
while x > 0:
acc *= x
x -= 1
return acc

if __name__ == '__main__':
n = int(sys.argv[-1])
t = timeit.Timer('fact(%d)' % n, 'from fact_it import fact')
print t.repeat(1, number=10000000)
print fact(n)

vi accorgerete di uno speed-up del 50% circa rispetto alla versione
ricorsiva per numeri “piccoli”.
Se invece eseguite l’equivalente codice Scheme

(import (rnrs) (only (ikarus) time) (only (repeat) call))

(define (fac x acc)
(if (= x 0) acc
(fac (- x 1) (* x acc))))

(define n
(string->number (car (reverse (command-line)))))

(time (call 10000000 (lambda () (fac n 1))))
(display "result:") (display (fac n 1)) (newline)

scoprirete che è leggermente più lento
rispetto alla versione non tail-call (comunque la versione tail-call
ha il vantaggio di richiedere meno spazio).
Siamo sempre però un ordine di grandezza sopra l’efficienza di Python.
Se prendiamo dei benchmark che dipendono fortemente
dall’efficienza delle chiamate a funzioni, come per esempio
il benchmark dei numeri di Fibonacci reso celebre dal nostro amato
boss Antonio Cangiano, la differenza tra Python e Scheme è ancora
più marcata: nei miei test Ikarus è trenta volte più veloce di
Python. Altri implementazioni di Scheme o altri linguaggi funzionali
(ML, Haskell) possono essere anche più performanti (io personalmente
ho provato l’implementazione SML/NJ che è quaranta volte più
veloce di Python 2.5). Ovviamente questi benchmark non dicono
nulla. Con i benchmark uno può anche provare che Python è più veloce
di Fortran e C++ nei calcoli matriciali. Se non ci credete, leggetevi
questo 😉

Per oggi è tutto, arrivederci alla prossima puntata!

Comments

  1. unwiredbrain says:

    Interessante. Come sempre d’altronde.

    Io però rivedrei la prima frase del paragrafo «Ricorsione e iterazione»: non è particolarmente chiara 😛

    A parte questo: complimenti; una serie di articoli davvero notevole.

    Spero vorrete continuarla.

  2. Michele Simionato says:

    C’era un refuso, l’ho appena sistemata.

  3. unwiredbrain says:
    c’è ancora un ‘che’ in più… 🙂 😛

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.