Benchmarking piccoli array vs. liste in Java: è il mio codice di benchmarking che non va?

Question

  

Avviso: Ho osservato con questo   domanda e questa domanda   ma entrambi ricevuti deragliare da piccole   dettagli e generale   ottimizzazione-è-inutili preoccupazioni.   Ho davvero bisogno di tutte le prestazioni di I   può ottenere nel mio attuale app, che è   ricevendo-elaborazione-sputa dati MIDI   in tempo reale. Inoltre ha bisogno di scalare    nel miglior modo possibile.

I sto paragonando le prestazioni array su un elevato numero di letture per i piccoli elenchi di ArrayList e anche ad avere solo le variabili in mano. Ho constatato che una matrice batte ArrayList di un fattore di 2,5 e anche batte solo per avere i riferimenti agli oggetti.

Quello che vorrei sapere è:

1. Il mio punto di riferimento va bene? Ho commutato l'ordine delle prove e numero di corse con nessun cambiamento . Ho anche usato millisecondi al posto di nanosecondi inutilmente.
2. Dovrei specificare alcuna opzione Java per ridurre al minimo questa differenza?
3. Se questa differenza è reale, in questo caso, non dovrei io preferisco Test[] a ArrayList<Test> in questa situazione e mettere in codice necessario per convertirli? Ovviamente sto leggendo molto di più di scrittura .

JVM è Java 1.6.0_17 su OSX ed è sicuramente in esecuzione in modalità Hotspot.

  public class ArraysVsLists {

    static int RUNS = 100000;

    public static void main(String[] args) {
        long t1;
        long t2;

        Test test1 = new Test();
        test1.thing = (int)Math.round(100*Math.random());
        Test test2 = new Test();
        test2.thing = (int)Math.round(100*Math.random());

        t1 = System.nanoTime();

        for (int i=0; i<RUNS; i++) {
            test1.changeThing(i);
            test2.changeThing(i);
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1) + " How long NO collection");

        ArrayList<Test> list = new ArrayList<Test>(1);
        list.add(test1);
        list.add(test2);
        // tried this too: helps a tiny tiny bit 
        list.trimToSize();

        t1= System.nanoTime();

        for (int i=0; i<RUNS; i++) {
            for (Test eachTest : list) {
                eachTest.changeThing(i);
            }
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1) + " How long collection");


        Test[] array = new Test[2];
        list.toArray(array);

        t1= System.nanoTime();

        for (int i=0; i<RUNS; i++) {
            for (Test test : array) {
                test.changeThing(i);
            }
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1) + " How long array ");

    }
}

class Test {
    int thing;
    int thing2;
    public void changeThing(int addThis) {
        thing2 = addThis + thing;
    }
}

Answer 1

Microbenchmarks sono molto, molto difficile da ottenere su una piattaforma come Java. È sicuramente per estrarre il codice da benchmark in metodi separati, eseguirli qualche migliaio di volte più di riscaldamento e quindi misurare. Ho fatto che (codice qui sotto) e il risultato è che l'accesso diretto attraverso riferimenti è poi tre volte più velocemente attraverso una serie, ma la raccolta è ancora più lento di un fattore 2.

Questi numeri sono basati sul opzioni -server -XX:+DoEscapeAnalysis JVM. Senza -server, utilizzando la collezione è drasticamente più lento (ma stranamente, l'accesso diretto e la matrice sono un bel po 'più veloce, che indica che c'è qualcosa di strano sta succedendo). -XX:+DoEscapeAnalysis produce un altro aumento di velocità del 30% per la raccolta, ma è molto questionabled se funzionerà anche per il codice di produzione reale.

Nel complesso la mia conclusione sarebbe: dimenticare microbenchmarks, possono troppo facilmente essere fuorviante. Misurare il più vicino al codice di produzione, come si può, senza dover riscrivere l'intera applicazione.

import java.util.ArrayList;

public class ArrayTest {

    static int RUNS_INNER = 1000;
    static int RUNS_WARMUP = 10000;
    static int RUNS_OUTER = 100000;

    public static void main(String[] args) {
        long t1;
        long t2;

        Test test1 = new Test();
        test1.thing = (int)Math.round(100*Math.random());
        Test test2 = new Test();
        test2.thing = (int)Math.round(100*Math.random());

        for(int i=0; i<RUNS_WARMUP; i++)
        {
            testRefs(test1, test2);            
        }
        t1 = System.nanoTime();
        for(int i=0; i<RUNS_OUTER; i++)
        {
            testRefs(test1, test2);            
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1)/1000000.0 + " How long NO collection");

        ArrayList<Test> list = new ArrayList<Test>(1);
        list.add(test1);
        list.add(test2);
        // tried this too: helps a tiny tiny bit 
        list.trimToSize();

        for(int i=0; i<RUNS_WARMUP; i++)
        {
            testColl(list);
        }
        t1= System.nanoTime();

        for(int i=0; i<RUNS_OUTER; i++)
        {
            testColl(list);
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1)/1000000.0 + " How long collection");


        Test[] array = new Test[2];
        list.toArray(array);

        for(int i=0; i<RUNS_WARMUP; i++)
        {
            testArr(array);            
        }
        t1= System.nanoTime();

        for(int i=0; i<RUNS_OUTER; i++)
        {
            testArr(array);
        }

        t2 = System.nanoTime();
        System.out.println((t2-t1)/1000000.0 + " How long array ");

    }

    private static void testArr(Test[] array)
    {
        for (int i=0; i<RUNS_INNER; i++) {
            for (Test test : array) {
                test.changeThing(i);
            }
        }
    }

    private static void testColl(ArrayList<Test> list)
    {
        for (int i=0; i<RUNS_INNER; i++) {
            for (Test eachTest : list) {
                eachTest.changeThing(i);
            }
        }
    }

    private static void testRefs(Test test1, Test test2)
    {
        for (int i=0; i<RUNS_INNER; i++) {
            test1.changeThing(i);
            test2.changeThing(i);
        }
    }
}

class Test {
    int thing;
    int thing2;
    public void changeThing(int addThis) {
        thing2 = addThis + thing;
    }
}

Answer 2

Il vostro punto di riferimento è valida solo se il caso d'uso effettivo corrisponde al codice di riferimento, vale a dire poche operazioni su ogni elemento, in modo che il tempo di esecuzione è in gran parte determinato dal tempo di accesso, piuttosto che le operazioni stesse. Se questo è il caso allora sì, si dovrebbe utilizzare array se le prestazioni sono critiche. Se invece il vostro caso reale utilizzo comporta molto più reale di calcolo per ogni elemento, quindi il tempo di accesso per ogni elemento diventerà molto meno significativa.

Answer 3

Probabilmente non è valido. Se ho ben capito il modo in cui i compilatori JIT lavoro, la compilazione di un metodo non influenzerà una chiamata a quel metodo che è già in esecuzione. Poiché il metodo main viene chiamato solo una volta, si finiscono per essere interpretato, e poiché la maggior parte del lavoro è fatto nel corpo di tale metodo, i numeri che si ottengono non sarà particolarmente indicativo di esecuzione normale.

JIT effetti di compilazione possono in qualche modo a spiegare perché il caso raccolte è stato più lento che il caso gli array. Questo risultato è contro-intuitivo, e pone in dubbio l'altro risultato benchmark che hai segnalato.