performance 為什麼處理排序數組*比未排序數組慢? (Java的ArrayList.indexOf)


1 Answers

我認為我們看到了內存緩存未命中的影響:

當你創建未排序的列表

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

所有的double都很可能分配在連續的內存區域中。 迭代通過這將產生很少的緩存未命中。

另一方面,在排序列表中,引用以混沌的方式指向內存。

現在,如果您使用連續內存創建一個排序列表:

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

這個排序的列表具有與原始列表相同的性能(我的時間)。

java performance arraylist

標題的內容是為什麼處理排序後的數組比處理未排序的數組更快?

這也是分支預測效果嗎? 當心:這裡排序數組的處理速度較慢

考慮下面的代碼:

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,64位),在Windows 10下運行,在Eclipse Mars中進行JUnit測試。

UPDATE

似乎與連續內存訪問有關(Double對象按順序與隨機順序訪問)。 對於我約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
 */


Related