Niektóre regresje podczas używania początkowej pojemności dla ArrayList w pierwszych iteracjach

Question

Jestem trochę zdezorientowany. W pierwszych iteracjach pętli wypełnienia widzę pewną regresję w czasie wypełniania, gdy używam initial capacity dla ArrayList vs bez użycia początkowej pojemności.

Według zdrowego rozsądku i to pytanie: Why start an ArrayList with an initial capacity?

musi być całkowicie odwrotnie.

To nie jest dobrze napisany testów, i zastanawiam się: dlaczego na pierwszej iteracji to zawsze pochłania znacznie więcej czasu i procesora podczas korzystania z początkową zdolność do ArrayList?

To jest test:

public class TestListGen { 
    public static final int TEST = 100_000_000; 

    public static void main(String[] args) { 
     test(false); 
    }  

    private static void test(boolean withInitCapacity) { 
     System.out.println("Init with capacity? " + withInitCapacity); 
     for (int i = 0; i < 5; i++) 
      av += fillAndTest(TEST, withInitCapacity ? new ArrayList<Integer>(TEST) : new ArrayList<Integer>()); 

     System.out.println("Average: " + (av/5)); 
    }  

    private static long fillAndTest(int capacity, List<Integer> list) { 
     long time1 = System.nanoTime(); 
     for (int i = 0; i < capacity; i++) list.add(i); 
     long delta = System.nanoTime() - time1; 
     System.out.println(delta); 
     return delta; 
    } 
} 

wyjściowa: 1)

Init with capacity? false 
17571882469 
12179868327 
18460127904 
5894883202 
13223941250 
Average: 13466140630 

2)

Init with capacity? true 
37271627087 
16341545990 
19973801769 
4888093008 
2442179779 
Average: 16183449526 

Przetestowałem go na: JDK 1.7.0.40, JDK 1.8.0.31

Answer 1

Jest to artefakt alokacji sterty Java, który powoduje wyniki, których się nie spodziewasz. Dostosuj początkową alokację sterty, a zobaczysz bardziej spójne wyniki, usuwając czasy przydzielania sterty z miksu. Ponadto należy się upewnić, że proces testowania nie jest zamieniany. W moim systemie wystąpił błąd OOM po TEST = 100_000_000 i musiałem go zredukować do 10_000_000 dla moich testów. Też przepuściłem oba test(false) i test(true) jeden po drugim. Zwróć uwagę, w jaki sposób przydzielanie sterty podczas uruchamiania i dodawanie wyraźnej wartości gc w poniższych wynikach powoduje, że poszczególne czasy są o wiele bardziej spójne. Odtworzenie rozgrzewki byłoby również ważne, aby test był bardziej spójny, ale nie zawracałem sobie tym głowy.

badaniu pierwotnym

Init with capacity? false 
1714537208 
1259523722 
1215986030 
1098740959 
1029914697 
Average: 1263740523 
Init with capacity? true 
343100302 
612709138 
355210333 
603609642 
348401796 
Average: 452606242 

test z -Xms500m -Xmx500m

Init with capacity? false 
682827716 
738137558 
576581143 
662777089 
555706338 
Average: 643205968 
Init with capacity? true 
368245589 
312674836 
297705054 
392935762 
307209139 
Average: 335754076 

test z -Xms500m -Xmx500m + System.gc() przed fillAndTest()

Init with capacity? false 
502767979 
435508363 
420956590 
487184801 
416041923 
Average: 452491931 
Init with capacity? true 
300744404 
298446734 
299080656 
300084036 
298473576 
Average: 299365881