ソートされた配列を未処理の配列よりも処理速度が遅くなっているのはなぜですか？ （JavaのArrayList.indexOf）

Question

タイトルはWhy is it faster to process a sorted array than an unsorted array?を参照しています

これもブランチ予測効果ですか？注意：ここではソートされた配列の処理は遅いです！

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のバージョンは、Windows 10で実行されている1.8.0_71（Oracle VM、64ビット）、Eclipse MarsでのJUnitテストです。

UPDATE

（ダブルオブジェクトがランダムな順序で対順番にアクセスされる）連続するメモリアクセスに関連すると思われます。アレイの長さが約10k以下の場合、効果が消えてしまいます。 the resultsを提供するための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 
*/ 

Answer 1

キャッシュ/プリフェッチ効果のようです。

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

リストをソートした後でも、同じ数のメモリ参照を平均して実行する必要がありますが、今回はメモリアクセスがランダムな順序で行われます。割り当てられたオブジェクトの順序が重要ということを証明するために

UPDATE

Here is the benchmark。 answer by weroとanswer by apangin（！1）を確認簡単な例として

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 

Answer 2

は、私たちは、メモリ・キャッシュ・ミスの効果を見ていると思う：

あなたは

for (int i = 0; i < LIST_LENGTH; i++) { 
    list.add(r.nextDouble()); 
} 

すべてダブルソートされていないリストを作成するとき連続したメモリ領域に割り当てられる可能性が最も高い。 これを繰り返すことで、キャッシュミスはほとんど発生しません。

一方、ソートされたリストでは、リファレンスが混乱してメモリを指しています。

今、あなたは、連続したメモリでソートされたリストを作成した場合：

Collection.sort(list); 
List<Double> list2 = new ArrayList<>(); 
for (int i = 0; i < LIST_LENGTH; i++) { 
    list2.add(new Double(list.get(i).doubleValue())); 
} 

このソートされたリストは、元の（私のタイミング）よりも同じ性能を持っています。

Answer 3

：

• は、乱数を作成し、必要に応じて
それらを並べ替え：以下は、両方のオプションの簡単な比較を行います
• 連続番号を作成し、それらを任意にシャッフルする

これはJMHベンチマークとして実装されていませんが、効果を観察するためにわずかな修正を加えたオリジナルのコード、：ランダムな番号がソートされている場合は、次の

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 
import java.util.Random; 

public class SortedListTest 
{ 
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L; 

    public static void main(String[] args) 
    { 
     int size = 100000; 
     testBinarySearchOriginal(size, true); 
     testBinarySearchOriginal(size, false); 
     testBinarySearchShuffled(size, true); 
     testBinarySearchShuffled(size, false); 
    } 

    public static void testBinarySearchOriginal(int size, boolean sort) 
    { 
     Random r = new Random(0); 
     List<Double> list = new ArrayList<>(size); 
     for (int i = 0; i < size; i++) 
     { 
      list.add(r.nextDouble()); 
     } 
     if (sort) 
     { 
      Collections.sort(list); 
     } 
     list = new ArrayList<>(list); 

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

     System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n", 
      size, sort, slowFindsPerSec, count); 
    } 

    public static void testBinarySearchShuffled(int size, boolean sort) 
    { 
     Random r = new Random(0); 
     List<Double> list = new ArrayList<>(size); 
     for (int i = 0; i < size; i++) 
     { 
      list.add((double) i/size); 
     } 
     if (!sort) 
     { 
      Collections.shuffle(list); 
     } 
     list = new ArrayList<>(list); 

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

     System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n", 
      size, sort, slowFindsPerSec, count); 
    } 

} 

出力私のマシンではうまくタイミングが他の丁度反対であることを示す

Size 100000 sort true iterations 8560,333 count  25681 
Size 100000 sort false iterations 19358,667 count  58076 
Size 100000 sort true iterations 18554,000 count  55662 
Size 100000 sort false iterations 8845,333 count  26536 

ですソートされたバージョンは遅くなります。連続番号がシャッフルされると、シャッフルされたバージョンは遅くなります。