Prestazioni di ArrayList

Question

Stavo cercando di vedere la differenza di prestazioni tra la pre-inizializzazione di un ArrayList a una determinata capacità, l'andare con la capacità predefinita e l'espansione su richiesta. Solo per curiosità. Ho scoperto che il codice array di capacità predefinito è ~ 10% FASTER rispetto al codice che inizializza la matrice alla capacità richiesta. Ecco il codice che ho usato:

public class Test { 
    public static void main(String[] args) { 

     long t1 = System.currentTimeMillis(); 
     for(int j=0;j<10;++j) { 
      List<Integer> list = new ArrayList<Integer>(); 
      for(int i=0;i<1000000;++i) { 
       list.add(i); 
      } 
     } 
     long t2 = System.currentTimeMillis(); 
     System.out.println("Time taken: " + (t2-t1)/10.0); 
    } 
} 

ho sempre ottengo ~ 77 ms per questa versione sulla mia macchina, mentre io ottengo ~ 85 ms se cambio l'inizializzazione List per new ArrayList<Integer>(1000000). Perché è così? Non dovrebbe essere il contrario? In effetti, la lista senza pre-init è costantemente un bit minimo (~ 0,5-1 ms) più veloce rispetto all'utilizzo di Integer[]. Fondamentalmente, quello che dice è default capacity arraylist > simple array > pre-capacity-ensured arraylist in prestazioni di inserimento.

Questo è molto strano per me. La mia ipotesi iniziale è che abbia qualcosa a che fare con l'allocazione della memoria, qualcosa come dare 1000000 blocchi int in una volta sola è forse più lento di ottenere lentamente più spazio? È riproducibile anche su altre macchine? Sto usando jdk 1.6.0, Mac OS X, usando eclipse.

ho provato in altri due ambienti: -> provato a fare funzionare java + javac da linea di comando, invece di Eclipse - Qui ho pre-capacity-ensured arraylist > simple array > default capacity arraylist, in modo coerente.

-> Ho provato a eseguire java + javac sul mio desktop Linux (RHEL). Questa scatola ha 24 GB di RAM, mentre il mio portatile aveva solo 8 GB. Qui ottengo plain array >>> default capacity arraylist > pre-capacity-ensured arraylist. La matrice semplice è super veloce, circa 2-3 volte più veloce in questo caso rispetto agli altri due.

EDIT: Seguendo @ suggerimento di JonSkeet nei commenti, ho usato nanoTime() e Integer invece di int. Non si tratta ancora del problema che il riscaldamento JIT non viene preso in considerazione. Dopo queste modifiche, vedo costantemente che la matrice semplice è la più veloce in tutti i test. Ma la lista di capacità garantita è ancora più lenta di circa il 5-10% rispetto alla lista di capacità di default per me in tutti e 3 gli ambienti sopra. MA alcuni utenti sembrano avere il comportamento corretto, quindi questo potrebbe essere un caso molto specifico.

EDIT2: Se uso String anziché intero come elemento, il comportamento è corretto (plain array > pre-capacity-ensured arraylist > default capacity array). Quindi penso che l'autoboxing sia in realtà il colpevole.

Answer 1

Ho sperimentato un po 'questo, e la mia conclusione è che il vostro punto di riferimento è imperfetto. Quando sistemo i problemi più ovvi, ottengo risultati drammaticamente diversi. I miei orari sono i seguenti:

 
default list: 74ms 
pre-sized list: 54ms 
Integer array: 42ms 
int array: 9ms 

Si noti che questi sono in unità di millisecondi. Il tuo codice esegue misurazioni in decine di millisecondi: (t2-t1)/10.0.

Per riferimento, il codice che ho usato è il seguente:

public class Clazz { 

    static final int N = 1000000; 

    interface Test { 
     void test(); 
    } 
    static final class DfltListTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       List<Integer> list = new ArrayList<Integer>(); 
       for (int i = 0; i < N; ++i) { 
        list.add(i); 
       } 
      } 
     } 
    } 
    static final class SizedListTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       List<Integer> list = new ArrayList<Integer>(N); 
       for (int i = 0; i < N; ++i) { 
        list.add(i); 
       } 
      } 
     } 
    } 
    static final class IntegerArrayTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       Integer[] arr = new Integer[N]; 
       for (int i = 0; i < N; ++i) { 
        arr[i] = i; 
       } 
      } 
     } 
    } 
    static final class IntArrayTest implements Test { 
     public void test() { 
      for (int j = 0; j < 10; ++j) { 
       int[] arr = new int[N]; 
       for (int i = 0; i < N; ++i) { 
        arr[i] = i; 
       } 
      } 
     } 
    } 

    static void test(Test t, String name) { 
     final int iter = 11; 
     final long timings[] = new long[iter]; 
     for (int k = 0; k < iter; ++k) { 
      long t1 = System.currentTimeMillis(); 
      t.test(); 
      long t2 = System.currentTimeMillis(); 
      timings[k] = t2 - t1; 
      System.gc(); 
     } 
     Arrays.sort(timings); 
     System.out.printf("%s: %dms\n", name, timings[iter/2]); 
    } 

    public static void main(String[] args) { 
     for (int i = 0; i < 5; ++i) { 
      test(new DfltListTest(), "default list"); 
      test(new SizedListTest(), "pre-sized list"); 
      test(new IntegerArrayTest(), "Integer array"); 
      test(new IntArrayTest(), "int array"); 
     } 
    } 
} 

ho provato utilizzando Java 1.7.0_09 con -XX:+AggressiveOpts -XX:CompileThreshold=1.

Quando ho provato lo stesso codice utilizzando Java 6, la classifica era la stessa, ma la differenza tra lista di default e la lista di pre-size era molto più significativo. Non ho tentato di capire di cosa si tratta Java 7 che rende la differenza molto più piccola.

Per alcune indicazioni su come il codice Java di riferimento, si veda How do I write a correct micro-benchmark in Java?

Answer 2

Facciamo questo esperimento, misurare il tempo necessario per una singola add(), sulle liste di diverse capacità

 ArrayList<Integer> list = new ArrayList<Integer>(N); 
     for(int i=0;i<N;++i) 
      list.add(new Integer(i)); // how many ns does this take? 

Sulla mia macchina

 N  ns per add(new) 

    32000  10 
    64000  10 
    128000  10 
    256000  10 
    512000  11 
1024000  11 
2048000  11 
4096000  15 
8192000  48 
16384000  132 
    1000  23 
    2000  13 
    4000  11 
    8000  11 
    16000  11 
    32000  10 

a quanto pare è molto più veloce per riempire 4 liste con 2M capacità rispetto a riempire 1 lista con 8M capacità.

Questo suggerisce che è possibile osservare ciò che è stato osservato: quando l'elenco inizia con una capacità ridotta, le cose girano più velocemente e il tempo risparmiato è più del sovraccarico successivo della copia di array.

Ma perché diventa più lento quando l'aumenti di capacità? Non ne sono sicuro. Forse ha qualcosa a che fare con la cache L2. Forse JVM ha un sovraccarico maggiore nell'assegnazione di array più grandi.

---

codice di prova:

static void test(int N) 
{ 
    long t0 = System.nanoTime(); 
    long x = 0; 
    long t = 0; 
    while(true) 
    { 
     ArrayList<Integer> list = new ArrayList<Integer>(N); 
     for(int i=0;i<N;++i) 
      list.add(new Integer(i)); 

     t = System.nanoTime()-t0; 
     x+=N; 

     if(t>1000_000_000) 
      break; 
    } 

    System.out.printf("%8s\t%4s%n", N, t/x); 
} 

public static void main(String[] args) 
{ 
    while(true) 
     for(int N=1000; N<20_000_000; N*=2) 
      test(N); 
}