Vector VS ArrayList

E’ da un pò che non scrivo sul blog (troppo lavoro…), lo faccio oggi per una questione che si è aperta qualche giorno fa nel team di sviluppo con cui collaboro da qualche mese. Vado al sodo (tanto siete già passati per il titolo, no?): meglio Vector o ArrayList?

Innanzitutto non c’è alcun motivo per cui a priori si debba optare per l’una o per l’altra indistintamente. In quest’articolo la scelta dell’implementazione da utilizzare verte sui seguenti fattori:

• le API
  Dal punto di vista delle API, le due classi sono praticamente analoghe. Ci sono solo alcune quisquilie che intrecciate agli altri fattori possono fare la differenza.

• la concorrenza
  Per quanto concerne la concorrenza, i Vector sono thread safe, mentre dall’altra parte gli ArrayList non lo sono. Il prezzo della sincronizzazione lo si paga in termini di performance (quanto sia questo prezzo lo vedremo in seguito).
  Qui si potrebbe già effettuare una prima scelta: se non si hanno problemi sulla concorrenza… Why pay the price of synchronization unnecessarily?

• la dinamica di crescita degli elementi
  Internamente, nella loro implementazione, ArrayList e Vector gestiscono gli elementi con un Array. Se quando si instanzia la lista non si indica la grandezza, ArrayList e Vector cambiano dinamicamente la grandezza del loro Array interno e giustamente lo fanno solo quando non c’è più spazio per il nuovo elemento che si desidera inserire. La differenza sostanziale tra ArrayList e Vector, in questo caso, sta nella nuova grandezza che l’array interno assume: ArrayList lo aumenta del 50%, Vector lo raddoppia.
  Ecco perchè il guru di Java sconsiglia di instanziare una lista e incominciare ad addare gli elementi in maniera brutale. E’ preferibile infatti settare una grandezza massima alla lista, tale da rientrare con gli inserimenti ed evitare di pagare il resize dinamico dell’array interno.
  Vector ha però un vantaggio: se si conosce il rate con cui crescono gli inserimenti è possibile settare il valore di incremento dell’array interno (con le API a tempo di costruttore).

• le operazioni
  Sia ArrayList che Vector permettono di recuperare un elemento in una determinata posizione e di aggiungere o rimuovere in coda al costo di O(1). Aggiungere o rimuovere elementi in una qualsiasi altra posizione ha costo lineare O(n), in quanto è necessario lo shift (rispettivamente in avanti o in indietro) degli elementi successivi. In particolare, se risulta quest’ultima l’operazione dominante, allora sarebbe utile scartare sia ArrayList che Vector ed utilizzare LinkedList, che aggiunge o rimuove elementi al costo di O(1), in cambio di un peggiore costo per l’indicizzazione e di un maggiore garbage (viene costruito un oggetto interno per ogni elemento).

Ho lasciato in sospeso il discorso sul costo effettivo della sincronizzazione di Vector. Lo affronto con la prova sul campo e più precisamente con una classe di test (la trovate qui) e, armato del più semplice microbenchmark, System.currentTimeMillis(), misurerò le differenze di performance tra le due implementazioni.
Se siete arrivati fin qui e ancora siete indecisi se per il vostro caso è meglio ArrayList o Vector, potreste far girare questo test sull’ambiente di esecuzione eclissando ogni responsabilità con i benefici della scelta effettuata.
Naturalmente nell’era del multiprocessore e con una JVM multithreading non mi sento di stabilire sentenze dopo un semplice run, consiglio quindi di lanciare più run e di stabilire una media dei tempi su cui poter trarre delle conclusioni affidabili.
La classe di test (il cui nome non può dare scapito a fraintendimenti) va lanciata con i seguenti parametri:

• [warmup] – Rappresenta il numero di iterazioni che si vogliono effettuare sulla lista; queste iterazioni non vengono misurate ma hanno lo scopo di far sì che la JVM possa effettuare le sue ottimizzazioni.

• [num] – Rappresenta il numero di elementi da inserire nella lista.

• [outer] – Rappresenta il numero di volte che si vuole iterare per intero la lista.

• [sleep] (in msec) – Rappresenta l’attesa tra il warmup e il test taimizzato. Ha lo scopo di rilasciare il processore per un lasso di tempo e permettere alla JVM di completare il processo di compilazione in background.

• [total] – Rappresenta il numero di run (il numero di tests da effettuare).

I risultati effettuati su una macchina con processore Intel P4, 1GB Ram con WindowsXP Professional e JVM 1.5 update 9 sono i seguenti:

--------------------------------------------------------------
VectorVSArrayList 3000 3000 3000 500 50
--------------------------------------------------------------
Testing with
warmup: 3000
num: 3000
outer: 3000
sleep: 500
total: 50
Vector  1156msec               ArrayList       250msec
Vector  1141msec               ArrayList       250msec
Vector  844msec                ArrayList       235msec
Vector  766msec                ArrayList       235msec
Vector  1172msec               ArrayList       234msec
Vector  813msec                ArrayList       234msec
[...]

I dati indicano approssimativamente una velocità di ArrayList superiore di circa 3-4 volte rispetto a Vector.

I risultati effettuati su una macchina con processore Intel P4, 1GB Ram con Ubuntu 6.06 e JVM 1.5 update 9 sono i seguenti:

--------------------------------------------------------------
VectorVSArrayList 3000 3000 3000 500 50
--------------------------------------------------------------
Testing with
warmup: 3000
num: 3000
outer: 3000
sleep: 500
total: 50
Vector  650msec               ArrayList       233msec
Vector  631msec               ArrayList       215msec
Vector  544msec               ArrayList       204msec
Vector  566msec               ArrayList       215msec
Vector  572msec               ArrayList       214msec
Vector  513msec               ArrayList       214msec
[...]

Anche in questo caso i dati indicano una velocità di ArrayList superiore, ma dell’ordine di 2 volte e mezzo circa.

I risultati effettuati sulla macchina precedente ma utilizzando JVM 1.6 sono i seguenti:

--------------------------------------------------------------
VectorVSArrayList 3000 3000 3000 500 50
--------------------------------------------------------------
Testing with
warmup: 3000
num: 3000
outer: 3000
sleep: 500
total: 50
Vector  570msec               ArrayList       180msec
Vector  531msec               ArrayList       149msec
Vector  504msec               ArrayList       158msec
Vector  506msec               ArrayList       150msec
Vector  512msec               ArrayList       149msec
Vector  501msec               ArrayList       148msec
[...]

La JVM 1.6 ha aumentato le performance di entrambe le implementazioni, ma per ArrayList la differenza è tale che adesso è più veloce di oltre 3 volte rispetto a Vector (avvicinandosi ai dati del primo test).

In tutti i test portando il warmup al valore di 1, la prima iterazione è di quasi 2 volte più lenta rispetto ai tempi delle successive.
Mentre se si riduce ad 1 solo msec lo sleep i tempi in totale sono più lenti di una volta e mezza ed il tempo ottimizzato viene raggiunto dopo circa 3 o anche 4 iterazioni.

Come concludere? Beh, io credo che, se per decidere, si è ridotti a dover far girare questi test allora si rischia poi di non dormirci la notte.
Alla prossima…