Unerwarteter Performance-Nachteil in Java

Question

Ich habe eine GapBuffer-Liste in Java implementiert, und ich kann nicht herausfinden, warum es eine solche Leistungseinbuße bekommt. Ähnlicher in C# geschriebener Code verhält sich wie erwartet: Das Einfügen in die Mitte der Liste ist viel schneller als die Implementierung von List in C#. Aber die Java-Version verhält sich merkwürdig.

Hier einige Benchmark-Informationen:

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. 

Wie Sie sehen können, wenn Sie an den Anfang der Liste einfügen, verhält sich die Lücke Puffer wie erwartet: es viele, viele, viele Male besser als Arraylist ist . Beim Einfügen und Entfernen an einer zufälligen Stelle in der Liste hat der Lückenpuffer jedoch eine merkwürdige Leistungseinbuße, die ich nicht erklären kann. Noch seltsamer ist die Tatsache, dass das Entfernen von Objekten aus der GapBufferList langsamer ist als das Hinzufügen von Objekten - nach jedem Test, den ich bisher ausgeführt habe, dauert das Entfernen eines Objekts etwa dreimal länger als das Hinzufügen eines Elements fast identisch, dass ihr Code ist:

@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]; 
} 

der Code für die Lücke Puffer kann für den Benchmark Einstiegspunkt zu finden ist here bei here und der Code zu finden. (Sie können einen beliebigen Verweis auf Flow.***Exception durch RuntimeException ersetzen.)

Answer 1

Sie kopieren den gesamten Inhalt des Arrays manuell. Verwenden Sie stattdessen System.arraycopy. Es ist viel schneller, als eine manuelle Kopie (es ist nativ und nutzt spezielle Magie). Sie können auch ArrayList-Quelle betrachten, es bewegt Elemente definitiv mit System.arraycopy und nicht eins nach dem anderen.

Über verschiedene Leistung von Hinzufügen/Entfernen-Methoden. Das Schreiben von Microbenchmarks in Java ist keine leichte Aufgabe. Für Details lesen Sie How do I write a correct micro-benchmark in Java? Es ist schwer zu sagen, was genau in Ihrem Fall passiert. Aber ich sehe, dass Sie zuerst Ihre Liste auffüllen und nur dann Elemente daraus entfernen. In diesem Szenario wird nur der Zweig (index> gapPos) ausgeführt. Wenn also JIT diesen Code kompiliert, kann eine CPU-Verzweigungsvorhersage stattfinden, was diesen Code weiter beschleunigen wird (weil der erste Zweig in Ihrem Testfall unwahrscheinlich ist). Die Entfernung wird beide Zweige fast gleich oft treffen und es kann keine Optimierung stattfinden. Es ist wirklich schwer zu sagen, was wirklich passiert. Sie sollten beispielsweise andere Zugriffsmuster ausprobieren. Oder besonders crafter Array mit Lücke darin. Oder andere Beispiele. Außerdem sollten Sie einige Debugging-Informationen von JVM ausgeben, was hilfreich sein kann.

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; 

} 

Das ist die Quelle der ArrayList Remove-Methode. Da es System.arraycopy (ziemlich clever) verwendet und Sie Schleifen verwenden, ArrayList Scores. Versuchen Sie, etwas Ähnliches zu implementieren, und Sie werden eine ähnliche Leistung sehen.