Javaでの予期しないパフォーマンスの低下

Question

私はGapBufferリストをJavaで実装しましたが、なぜこのようなパフォーマンスの低下が起こっているのかわかりません。 C＃で書かれた同様のコードは期待通りに動作します。リストの中央に挿入すると、C＃のリストの実装よりもはるかに高速です。しかし、Javaのバージョンは奇妙な動作をしています。ここで

いくつかのベンチマーク情報です：

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. 

あなたが見ることができるように、あなたがリストの先頭に挿入すると、ギャップバッファが期待通りに動作します。それは、ArrayListをより多くの、多くの、何回も優れています。しかし、リスト内の任意の場所に挿入したり削除したりするとき、ギャップバッファーには私が説明できない奇妙なパフォーマンスのペナルティがあります。見知らぬ人でも、GapBufferListから項目を削除するのは、項目を追加するよりも遅いということです。これまで実行したすべてのテストでは、項目を削除するのに約3倍の時間がかかります。

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

ギャップバッファのコードがhereで見つけることができ、及びベンチマークエントリポイントのコードがhere見出すことができる：それらのコードがほぼ同じです。 Flow.***Exceptionへの参照をRuntimeExceptionに置き換えることができます。

Answer 1

アレイのすべての内容を手動でコピーします。代わりにSystem.arraycopyを使用してください。手動コピーよりもはるかに高速です（ネイティブで特別な魔法を使用しています）。また、ArrayListソースを見ることができます。System.arraycopyで要素を1つずつ移動させるのは間違いありません。

追加/削除メソッドのパフォーマンスについてJavaでマイクロベンチマークを書くことは簡単ではありません。詳細は、How do I write a correct micro-benchmark in Java?を読んでください。あなたのケースではどういうことが起こるのかは言うまでもありません。しかし、私はあなたが最初にあなたのリストを作成し、それからそれから項目を削除することがわかります。このシナリオでは、（index> gapPos）ブランチのみが実行されます。したがって、JITがそのコードをコンパイルすると、CPU分岐の予測が行われ、このコードがさらに高速化されます（最初の分岐はテストケースでは起こりそうにないので）。削除は両方のブランチにほぼ同じ回数だけヒットし、最適化は実行されません。だから実際に何が起こるか、言うのは本当に難しいです。たとえば、他のアクセスパターンを試す必要があります。またはそれの中に隙間を持つ特別なクラフターアレイ。または他の例。また、JVMからデバッグ情報を出力する必要があります。役立つかもしれません。

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; 

} 

これは、ArrayListのremoveメソッドのソースです。それはSystem.arraycopy（かなり巧みに）を使用しているので、あなたはループ、ArrayListのスコアを使用しています。同様のものを実装しようとすると、同様のパフォーマンスが表示されます。