[ARRAY] A volte l’ottimizzazione…
A volte l’ottimizzazione…
Capita spesso che durante lo sviluppo di una applicazione si tenda ad estremizzare l’ottimizzazione del codice. Nella maggior parte dei casi tuttavia i risultati riguardano un guadagno insignificante al pari di un codice talmente criptico ed ingestibile che sarebbe degno di un messaggio di guerra.
In questo post facciamo qualche benchmark sugli array e vediamo che succede, mettiamo quindi a cronfronto tre linguaggi/frameworks: C, C++ e il nostro Objective-C (o meglio le Foundation Classes di Cocoa).
C++ mette a disposizione del programmatore 17 classi per la gestione delle liste (niente di sorprendente, rispetto a Java che va oltre le 22). La cosa interessante è che spesso e volentieri i nomi delle classi descrivono, in qualche modo, come lavora l’implementazione: vector, list hash_multiset e così via per il C++ e LinkedBlockingQueue,IdentityHashMap etc per Java.
Al contrario in Core Foundation i nomi descrivono soltanto il tipo di classe (ed è questo in effetti lo spirito del messaging dinamico di Objective-C; il messagio dice cosa fà ma non come lo fà).
Prendiamo ad esempio una delle 7 classi (ripeto 7!) più utilizzate di Core Foundation, NSArray (o meglio CFArray) e diamo un’occhiata ad uno dei commenti apparsi sulla mailing list di Darwin (se ve lo state domandando, Core Foundation è opensource).
In poche parole:
Il tempo (e quindi il costo) di accesso a un valore all’interno della lista è al peggio O(lg N) per ogni implementazione, presente e futura (ovvero cresce in maniera logaritmica in base all’indice della chiave richiesta). Tuttavia nella maggior parte dei casi sarà O(1) (ovvero un tempo costante per ogni chiave in ogni posizione). Le operazioni di ricerca lineare, inserimento e cancellamento di oggetti avranno similarmente un grado di complessità pari a O(N*lg N) ma in generale sarà molto minore. In pratica non c’è nessun bisogno di portare in posizioni “strategiche” le chiavi più importanti.
La cosa curiosa è che in generale gli array non hanno tempi di lettura logaritmici quanto piuttosto risultano essere a tempo costante. Ma non questi array. Array? Chi ha parlato di veri e propri array? Sembrano più dei dizionari o degli alberi binari…
…In effetti facendo qualche prova si hanno dei risultati quasi ’stravaganti’. Diamo un’occhiata ai grafici sotto. I risultati sono espressi come multipli degli originali e il crescere delle linee indica un maggior costo di esecuzione al pari della dimensione dell’array. Questo significa che, ad esempio, se la ricerca punta come una retta in alto, il costo sarà proporzionale alla crescita degli elementi dell’array.
Ecco qui cosa si ottiene con degli array in C.
Ok allora? Beh possiamo notare che un inserimento in posizioni casuali è circa 50 volte più lento se la dimensione dell’array è 100,000 anzichè 1,000,000. La cosa in realtà non ci sorprende, i dati non fanno altro che dirci che non c’è molta differenza tra inserimento in posizioni casuali anzichè all’inizio della lista.
In C++ la differenza di costi tra le operazioni risulta essere più lieve (c’è soltanto da far notare una leggera differenza tra cancellazione lineare e in posizioni casuali).
Al contrario con CFArray… il grafico risulta essere totalmente diverso dai due precedenti!. A partire da un certo punto (intorno ai 300,000 valori) l’inserimento o la cancellazione all’inizio o alla fine non comporta nessun aumento di costo al variare della dimensione degli array.
Cancellazione e inserimento in posizioni casuali inizia con un consumo lineare per poi ridursi fino a diventare costante. In soldoni stiamo dicendo che non c’è differenza tra inserire 1,000,000 elementi o 100,000 ma sicuramente inserirne 200,000 è più dispendioso del resto (a vederla così sembra assurdo…sembra).
Scorrere avanti/indietro l’array invece comporta un costo costante sopra i 300,000 elementi. Questo ci porta a pensare che in effeti ci sia una sorta di cache per l’accesso al CFArray (cosa che tra l’altro è rafforzata da una ulteriore classe chiamata CFStorage).
Cosa abbiamo imparato?
Non abbiamo sicuramente testato a fondo la cosa, tuttavia questi piccoli esperimenti ci portano a dire che CFArray (e quindi NSArray) sono una ottima soluzione in caso di dimensioni medie e medio-alte, senza doverci per forza sobbarcare l’onere di creare classi apposite o lavorare di ottimizzazione. Apple ha già lavorato per noi e sembra averlo fatto ottimamente!
Nella prossima puntata daremo uno sguardo ad array di dimensione basse.
(Questo articolo è stato realizzato grazie alla collaborazione di alcuni utenti su #macdev e grazie a RFish).
