[解決済み] なぜソートされた配列の処理は、ソートされていない配列よりも*遅い*のですか？(JavaのArrayList.indexOf)

質問

タイトルは なぜソートされていない配列よりもソートされた配列の方が処理が速いのですか？

これも分岐予測効果なのでしょうか？注意：ここではソート済み配列に対する処理は より遅い !!

次のようなコードを考えてみましょう。

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

これは私のマシンでは約720の値をプリントアウトします。

今、私がコレクションのソート呼び出しをアクティブにすると、その値は142に下がります。なぜでしょうか!

結果 は であり、反復回数/時間を増やしても変わりません。

Javaバージョンは1.8.0_71（Oracle VM、64bit）、Windows10で動作、Eclipse MarsでJUnitテストを行っています。

アップデイト

連続したメモリアクセス（ダブルオブジェクトが順次アクセスされる場合とランダムな順序でアクセスされる場合）に関連しているようです。配列の長さが約 10k 以下である場合、私の場合、効果は消え始めます。

を提供してくれた assylias に感謝します。 結果 :

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */

どのように解決するのですか？

キャッシュ／プリフェッチの効果があるようです。

ヒントは、ダブル（プリミティブ）ではなく、ダブル（オブジェクト）を比較していることです。1 つのスレッドでオブジェクトを割り当てるとき、それらは通常、メモリ内に順次割り当てられます。そのため、いつ indexOf がリストをスキャンするとき、連続したメモリアドレスを通過します。これは CPU キャッシュのプリフェッチ ヒューリスティックに適しています。

しかし、リストをソートした後も、平均して同じ数のメモリ検索を行う必要がありますが、この時のメモリアクセスはランダムな順番になります。

UPDATE

ベンチマークはこちら で、割り当てられたオブジェクトの順序が重要であることを証明しています。

Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op