Me la meno!

Ho recentemente scoperto il sito rosettacode.org, che tratta la soluzione di determinati problemi o design patterns in diversi linguaggi, oltre che come i vari linguaggi approccino problematiche diffuse.
Nella seconda casistica ricadono cose tipo la chiamata di funzione con il passaggio di parametri per nome, di cui avevo parlato tempo fa nel mondo Python.
Nella prima casistica ci sono approcci di linguaggi differenti a problematiche ben note, fra cui per esempio la scomposizione in fattori primi.
Problema matematicamente noto, quindi non particolarmente interessante, che in Python viene risolto facendo uso di alcuni costruiti che non avevo mai usato.
Mi sono quindi imbastito a confrontare il programma fornito, la sua versione ottimizzata e la mia soluzione al problema.
Dopo qualche tentativo andato in fumo a causa di un erroraccio di ottimizzazione da parte mia, sono fottutamente orgoglioso di dire che la mia versione disintegra la soluzione ottimizzata proposta, con un fattore che in svariati casi è vicina al 2 a 1 su numeri oltre le 10 cifre.
Le versioni originali le trovate qui, quelle python esattamente qui, mentre la mia, la potete leggere a seguire:



Per la cronaca ho preso e completato la versione Java proposta e l'ho paragonata alla mia e risulta piuttosto evidente la superiorità della mia soluzione. Il paragone è fra Java 1.5 e Py 2.6 (lo dico a beneficio di chi dovesse confrontare java 1.6 contro Py3 e trovare risultati magari eclatantemente diversi).
Il problema è, ovviamente, di sola mancata ottimizzazione del codice Java. Dico ovviamente perché Java è più performante di py di parecchie lunghezze, se si parla di calcoli puri fortemente iterativi. L'inghippo sta nel fatto che il codice Java è scarsamente ottimizzato, mentre quello Py, e il mio in particolare, è piuttosto ben limato.
Questo per ricollegarci in modo nuovo al discorso sui benchmark di qualche tempo fa: un algoritmo ottimizzato in un linguaggio lento spesso è prestazionalmente migliore di uno scritto alla buona in un linguaggio veloce.
Ovviamente ottimizzando per quanto possibile la versione Java (non ho trovato in 5 minuti di googling come fare la radice quadrata di un BigInteger) siamo andati a pari sino a cifre molto molto grosse, poi dai 16 digits in su....ha vinto lui. Capita.

Ultima nota di colore: guardate questa implementazione nel liguaggio False (mai sentito nominare): [2[\$@$$*@>~][\$@$@$@$@\/*=$[%$." "$@\/\0~]?~[1+1|]?]#%.]d:

Astonishing!

Read more

benchmark

Prima dell'estate ho letto un sacco di benchmark di paragone fra vari linguaggi di programmazione.
Cercavo, spunti, conferme e dati interessanti che mi permettessero di avere una valutazione prestazionale di varie tecnologie, che comunque rimane solo uno dei mille aspetti che determinano una scelta tecnologica rispetto ad altre.

Sono sempre stato un appassionato di classifiche, quasi un feticista delle classifiche. Delle scarpe col tacco o della lingerie no, ma delle classifiche sì, quindi in prima posizione la lingerie e in seconda i tacchi. Quindi i benchmark mi appassionano anche perché hanno sempre questo aspetto di confronto che definisce, spesso, un sacco di classifiche, per dati semplici, poi per aggregazione di dati non omogenei in partenza che vengono pesati...un'orgia di classifiche, insomma. Ma questa è un'altra storia.

Ho trovato un sacco di pane per i miei denti in rete. Ho letto ed elaborato informazioni. Poi sono stato assalito da dubbi. Ho cercato dove possibile di capire la natura delle prove che costituivano i benchmark in questione. I più interessanti si trovano qui: Computer Language Benchmark Game.

Sono tutti o quasi benchmark di problemi dalla soluzione nota risolubili con un algoritmo computazionale più o meno pesante, quasi sempre su interi o numeri in virgola mobile. Qualche eccezione prevede operazioni su stringhe e espressioni regolari triviali.

Mi ha colpito come su decine di prove si verifichino sempre le stesse cose, creando sproporzioni artificiose in favore di alcuni e contro altri: chi risolve bene i problemi di una categoria risolve bene, con minime varianti, i problemi della stessa categoria che presentano solo piccole varianti sul problema originale. Ergo chi vince sul primo vince su tutti, cioè piazza invece che un 1 a 0 un 10 a 0. Poi magari di un'altra categoria si pone un solo problema, in cui il primo linguaggio perde in favore del secondo, ma non esistendo varianti nel benchmark il risultato è 10 a 1 e non un 1 pari come forse sarebbe stato più giusto...

Vabbeh. Poco male. Le classifiche sono associazioni di dati, quando si vuole il dettaglio bisogna scavare.

E scavando appare anche evidente che l'obiettivo sembra quello di porre problemi relativamente facili da rappresentare, ma questo, seppure in senso lato, è un altro modo di categorizzare il mondo. Chi fa della flessibilità o della capacità di modellare situazioni il suo punto di forza perde magari tutti i confronti sui casi ben definiti, ma vince in quelli più difficili.

Per ora tutti discorsi generici, entro nello specifico, prendendo 4 linguaggi di cui ho una conoscenza di base sufficiente per poterne parlare con cognizione di causa: C, C++ (e chi dice C/C++ probabilmente è perché il C++ ha mantenuto la backward compatibility e crede quindi che sia una estensione con le stringhe nella STL del C), Python 2.x e Java 6. Li abbrevierò in C, C++, Py e J6.

Che in problemi strettamente computazionali il C batta Py e J6 è così evidente che serve a poco scriverlo...ma è comunque interessante sapere di quante lunghezze. Sul confronto C vs C++ si dovrebbero spendere troppe parole, fatto sta che i 2 per problemi del genere possono risolvere il problema in modo così simile da risultare quasi indistinguibili.

J6 straccia Py, merito soprattutto dell'ottimo JIT di Java e dell'esclusione di Psyco dai benchmark di Py (che farebbe scendere il rapporto da x30 a circa x1.3, che insomma, ha il suo peso).

I valori medi dei 4 linguaggi per tutti i benchmark su grossi numeri è:
C : 1.01
C++ : 1.00
J6 : 1.68
Py :54.03

Dove 1 è il valore del migliore, il resto in rapporto, credo.

Cosa emerge cercando meglio? che sono quasi tutti dei mega loop con operazioni matematiche semplici, ossia cose che se dici a un compilatore C di sbrogliare i loop, lui bello bello ti cabla la ripetizione delle operazioni nel programma, facendotelo diventare sì un tonno, ma togliendo pure quell'overhead dei jump a fine ciclo. Che se hai un JIT o simili il peso del JIT scompare. Che se sei un interpretato interpreterai 10mila volte 1+1...

Ora vediamo nello specifico che invece, se si prende il test regex-dna, che ha un po' di smanettamento sulle stringhe, si ottiene questa classifica, questa volta in secondi di esecuzione:

C++ : 19sec (ma bara, usando un botto di librerie di terze parti, e anche al soluzione da 26 secondi usa una libreria di espressioni regolari non standard)
Py : 29sec
j6 : 31sec (in server edition, per questo test)
C : 32sec

Questo perché? come può C perdere contro Py?
Diamo una risposta di base un po' strana: l'interprete Python è scritto in C, quindi formalmente un programma Python potrebbe essere considerato come un file di configurazione un programma C incredibilmente complesso. Quindi Py non batte realmente C. Il problema è che bisogna trovare un soluzione che tenga conto anche delle dimensioni e non solo delle prestazioni. Cioè non posso scrivere una applicazione da alcuni mega per uno stupido programma Py da 20 righe circa...
La realtà è che quindi il modulo delle espressioni regolari in Py lavora meglio di quanto possa fare uno bravo che scrive una soluzione specifica al problema senza voler costruire un missile nucleare per uccidere una zanzara.

Ora andiamo avanti con il ragionamento, ma spostiamoci nell'astratto: cosa succederebbe se a dover essere rappresentato fosse un problema abbastanza complesso da spingere un programmatore medio a scrivere una gerarchia di classi?
Il C++ lo affronterebbe benissimo, allo stesso modo J6 e Py, almeno da un punto di vista della rappresentazione della soluzione. In C si comincerebbe a chiedersi se il problema abbia complessità tale da imbarcarsi in una serie di struct di puntatori a funzioni, ossia della cosa che più si avvicina a una classe, senza però tutte le facility del C++, senza costruttori e distruttori, con meccanismi di ereditarietà tutti da inventare....

E se il problema fosse abbastanza complesso da spingere un programmatore C++ o Py a scrivere un programma strutturato con ereditarietà multipla? In J6 te la cavi o tramutando il canonico rapporto is-a con un has-a poi ridefinendo tutto il flusso della soluzione, o duplicando tonnellate di codice o smanettando con pratiche non molto comuni. In C ti metti le mani nei capelli e poi ti rassegni: comincia a costruire un castello immenso che richiede analisi approfondita del caso in questione...oppure abbandoni e lo fai in C++ :)

Però se un problema arriva a quel livello di complessità, sicuramente esistono più soluzioni plausibili per affrontarlo e quindi le soluzioni proposte non sempre sono pienamente paragonabili. Peggio, quelle più preformanti sono probabilmente quelle che prescindono da una buona rappresentazione del problema e vanno dritte al nocciolo, con buona pace della manutenibilità del codice e, peggio, della sua estensibilità.

Purtroppo banchmark su problemi di questo tipo è veramente dura trovarne, quindi ci si rassegna a un po' di speculazioni, che riguardano la bontà di tenersi una tabella di riferimenti ai metodi come fanno C++ e Py contro la ricerca in risalita lungo la gerarchia come fa (o faceva, su questo punto sono rimasto indietro, ma non credo abbiano cambiato) Java.

Poi c'è la questione che Java arriva insieme a librerie per fare di tutto di più, Python un po' meno, C++ mostruosamente meno, C è un disastro. Quindi quello che è un problema banale in un linguaggio in un altro potrebbe essere fonte di non pochi grattacapi, anche se poi, la soluzione specifica al problema potrebbe essere più performante.

Insomma, mi hanno detto in mille modi che una ferrari va più veloce di una persona, ma non mi hanno detto che la persona poteva tagliare per un vicoletto di 15 metri e la ferrari ha dovuto fare un giro di 15 km con 4 semafori per arrivare allo stesso punto.

Resta il fatto che se uno deve fare un loop in cui fa 10000 mila volte una somma e lo deve fare in modo performante, se sceglie un linguaggio interpretato è probabilmente un imbecille...

Read more