ArrayListのパフォーマンス

Question

ArrayListを既定の容量と所定の容量で事前初期化してから要件を拡張するまでのパフォーマンスの違いを確認しようとしました。単なる好奇心から。私は、デフォルトの容量アレイコードが〜10％ファーストであることが、アレイを必要な容量に初期化するコードよりも高いことがわかりました。ここで私が使用したコードは次のとおりです。

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); 
    } 
} 

私は一貫して私のボックスで、このバージョンのために〜77ミリ秒を取得し、私はnew ArrayList<Integer>(1000000)にリストの初期化を変更した場合、私は〜85ミリ秒を取得する一方。それはなぜそうですか？それはそれ以外の方法ではいけませんか？実際、プレ初期化のないリストは、一貫して、普通のInteger[]を使用するよりもわずかなビット（〜0.5-1ms）で高速です。基本的には、それは挿入のパフォーマンスでdefault capacity arraylist > simple array > pre-capacity-ensured arraylistと言います。

これは私にとって非常に奇妙です。私の最初の推測では、メモリ割り当てと何か関係があるということです.1000000のintブロックを一度に与えるのは、ゆっくりと余裕を持たせるよりも遅くなるでしょうか？これは他のマシンでも再現可能ですか？私は、Eclipseを実行しているJDK 1.6.0、Mac OS Xを使用しています。

私は別の2つの環境で試しました。 - > Eclipseではなくコマンドラインからjava + javacを実行しようとしました - ここでは一貫してpre-capacity-ensured arraylist > simple array > default capacity arraylistが得られます。

- > Linux（RHEL）デスクトップでJava + javacを試してみました。このボックスには24 GBのRAMがありますが、ノートパソコンには8 GBしかありませんでした。ここでは、私はplain array >>> default capacity arraylist > pre-capacity-ensured arraylistを取得します。プレーンアレイは超高速で、この場合、他の2つよりも約2〜3倍高速です。

EDIT：コメントでJonSkeetの提案@以下は、私がnanoTime()、およびInteger代わりにintを使用しました。それでも、JITウォームアップが考慮されていないという問題はまだ解決していません。これらの変更の後、私は一貫してプレーンな配列がすべてのテストで最も速いことを知っています。しかし、容量を保証したリストは、上記の3つの環境全体のデフォルト容量リストと比較して、まだ5〜10％遅くなっています。しかし、一部のユーザーは正しい動作をしているようですので、これは非常に特殊なケースかもしれません。

EDIT2：要素としてIntegerの代わりにStringを使用すると、動作は正しくなります（plain array > pre-capacity-ensured arraylist > default capacity array）。だから、私はオートバイが実際には犯人だと思う。

Answer 1

これを少し実験しましたが、私の結論はベンチマークに欠陥があることです。最も明白な問題を修正すると、私は劇的に異なる結果になります。私のタイミングは次の通りです：

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

これらはミリ秒単位であることに注意してください。あなたのコードは、数十ミリ秒で測定を実行します：(t2-t1)/10.0。参考のため

次のように、私が使用したコードは次のとおりです。

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"); 
     } 
    } 
} 

私は-XX:+AggressiveOpts -XX:CompileThreshold=1でのJava 1.7.0_09を使用してそれをテストしてみました。

Java 6を使用して同じコードをテストしたところ、ランキングは同じでしたが、デフォルトリストと事前サイズリストの違いははるかに重要でした。私は、Java 7の違いがはるかに小さいことを理解しようとしていませんでした。どのようにベンチマークJavaコードへのいくつかのポインタについては

、異なる容量の私のマシン上で

 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? 

のリストに、それは単一add()のにかかる時間を測定し、How do I write a correct micro-benchmark in Java?

Answer 2

だが、この実験をやってみましょう見ます

 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 

明らかに、容量2Mの4つのリストを容量8Mの1つのリストに書き込むよりもはるかに高速です。

これは、リストが小さな容量で開始された場合、より速く実行され、保存された時間がアレイコピーの後のオーバーヘッドよりも大きいことを示しています。

しかし容量が増えると、なぜそれは遅くなりますか？よく分かりません。たぶんそれはL2キャッシュと関係があります。おそらく、JVMはより大きな配列を割り当てるためのオーバーヘッドがあります。

---

テストコード：

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); 
}