Penalità imprevista delle prestazioni in Java

Question

Ho implementato un elenco GapBuffer in Java e non riesco a capire perché stia ottenendo una simile penalizzazione delle prestazioni. Il codice simile scritto in C# si comporta come previsto: l'inserimento al centro della lista è molto più veloce dell'implementazione di List di C#. Ma la versione di Java si sta comportando in modo strano.

Ecco alcune informazioni di benchmarking:

Adding/removing 10,000,000 items @ the end of the dynamic array... 
ArrayList: 683 milliseconds 
GapBufferList: 416 milliseconds 

Adding/removing 100,000 items @ a random spot in the dynamic array... 
    - ArrayList add: 721 milliseconds 
    - ArrayList remove: 612 milliseconds 
ArrayList: 1333 milliseconds 
    - GapBufferList add: 1293 milliseconds 
    - GapBufferList remove: 2775 milliseconds 
GapBufferList: 4068 milliseconds 

Adding/removing 100,000 items @ the beginning of the dynamic array... 
ArrayList: 2422 milliseconds 
GapBufferList: 13 milliseconds 

Clearly, the GapBufferList is the better option. 

Come si può vedere, quando si inserisce all'inizio della lista, il buffer gap si comporta come previsto: si tratta di molte, molte, molte volte meglio di ArrayList . Tuttavia, quando si inserisce e si rimuove in un punto casuale nella lista, il buffer gap ha una strana penalità di prestazioni che non riesco a spiegare. Ancora più strano è il fatto che rimuovere elementi da GapBufferList è più lento dell'aggiunta di elementi ad esso - in base ad ogni test che ho eseguito fino ad ora, ci vuole circa tre volte più tempo per rimuovere un oggetto di quanto ne faccia uno, nonostante il fatto che il loro codice è quasi identica:

@Override 
public void add(int index, T t) 
{ 
    if (index < 0 || index > back.length - gapSize) throw new IndexOutOfBoundsException(); 
    if (gapPos > index) 
    { 
     int diff = gapPos - index; 
     for (int q = 1; q <= diff; q++) 
      back[gapPos - q + gapSize] = back[gapPos - q]; 
    } 
    else if (index > gapPos) 
    { 
     int diff = gapPos - index; 
     for (int q = 0; q < diff; q++) 
      back[gapPos + q] = back[gapPos + gapSize + q]; 
    } 
    gapPos = index; 
    if (gapSize == 0) increaseSize(); 
    back[gapPos++] = t; gapSize--; 
} 
@Override 
public T remove(int index) 
{ 
    if (index < 0 || index >= back.length - gapSize) throw new IndexOutOfBoundsException(); 
    if (gapPos > index + 1) 
    { 
     int diff = gapPos - (index + 1); 
     for (int q = 1; q <= diff; q++) 
      back[gapPos - q + gapSize] = back[gapPos - q]; 
    } 
    else 
    { 
     int diff = (index + 1) - gapPos; 
     for (int q = 0; q < diff; q++) 
      back[gapPos + q] = back[gapPos + gapSize + q]; 
    } 
    gapSize++; 
    return back[gapPos = index]; 
} 

il codice per il buffer gap può essere trovato alla here, e il codice per l'entrypoint riferimento può essere trovato here. (È possibile sostituire qualsiasi riferimento a Flow.***Exception con RuntimeException.)

Answer 1

Copia manualmente tutto il contenuto dell'array. Utilizzare invece System.arraycopy. È molto più veloce di una copia manuale (è nativa e usa la magia speciale). Inoltre puoi guardare il sorgente ArrayList, sposta decisamente gli elementi con System.arraycopy e non uno alla volta.

Informazioni sulle diverse prestazioni dei metodi di aggiunta/rimozione. Scrivere i microbenchmarks in java non è un compito facile. Per i dettagli, leggi How do I write a correct micro-benchmark in Java? È difficile dire cosa succede esattamente nel tuo caso. Ma vedo che per prima cosa compila la tua lista e solo dopo rimuovi gli elementi da essa. In questo scenario, viene eseguito solo il ramo (index> gapPos). Quindi, se JIT compila quel codice, allora potrebbe avvenire la previsione del ramo CPU, il che velocizzerà ulteriormente questo codice (perché il primo ramo è improbabile nel tuo caso di test). La rimozione colpirà entrambe le diramazioni quasi lo stesso numero di volte e nessuna ottimizzazione può aver luogo. Quindi è davvero difficile dire cosa succede realmente. Ad esempio, dovresti provare altri modelli di accesso. O una matrice speciale con uno spazio vuoto al suo interno. O altri esempi. Inoltre, dovresti pubblicare alcune informazioni di debug da JVM, potrebbe essere utile.

Answer 2

public E remove(int index) { 

    rangeCheck(index); 

    modCount++; 

    E oldValue = elementData(index); 

    int numMoved = size - index - 1; 

    if (numMoved > 0) 
     System.arraycopy(elementData, index+1, elementData, index, numMoved); 

    elementData[--size] = null; // Let gc do its work 

    return oldValue; 

} 

Questa è la fonte del metodo di rimozione di ArrayList. Dal momento che sta usando System.arraycopy (abbastanza abilmente) e stai usando loop, i punteggi ArrayList. Prova a implementare qualcosa di simile e vedrai prestazioni simili.