为ArrayList提供初始容量时,为什么这会变慢？

Question

对于一个实验,我做了这个小程序.它只生成1000万个随机字符串并将它们添加到arraylist中.请注意,ArrayList中并没有有一个初步的能力.

// editors note: added the necessary boilerplate to run,
// and take initial capacity as an optional cmdline arg for easier testing
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class ArrayListTest {
    public static void main(String[] args)
    {
        int initsize = -1;
        if (args.length > 0) {
            initsize = Integer.parseInt(args[0]);
        }

        long startTime = System.currentTimeMillis();

        List<String> randNums = initsize>=0 ? new ArrayList<>(initsize) : new ArrayList<>();
        // final List<String> randNums = initsize>=0 ? new ArrayList<String>(initsize) : new ArrayList<String>();

        Random r = new Random(1);

        for (int i = 0; i < 10_000_000; i++) {
            final int randomNum = r.nextInt();
            randNums.add(Integer.toString(randomNum));
        }

        System.out.println(System.currentTimeMillis() - startTime);
    }
}

我运行了5次,结果以ms为单位:

8917
8720
7814
8768
8867

然后我改变了程序,给ArrayList一个初始容量:

    List<String> randNums = new ArrayList<>(10_000_000);

我再次跑了5次,结果如下:

11562
10454
10499
10481
10415

它肯定一直变慢.我认为它是相反的,因为通过声明一个足够大的初始大小,我带走了ArrayList的所有开销,增加了自己的容量.它为什么慢？

更多信息:Jre 1.8.051,64位(在Windows 10上);

Answer 1

你认为这是另一种方式,但它与垃圾收集有关.

我没有看到你所做的巨大差异(3900 vs 5100),但由于这与GC相关,你可能会以较低的内存运行.我用64位和-Xmx4g.

打开GC日志(-Xloggc:path\to\file.log),我得到这个没有大小:

Java HotSpot(TM) 64-Bit Server VM (25.51-b03) for windows-amd64 JRE (1.8.0_51-b16), built on Jun  8 2015 18:03:07 by "java_re" with MS VC++ 10.0 (VS2010)
Memory: 4k page, physical 33478384k(25822824k free), swap 33476532k(26121788k free)
CommandLine flags: -XX:InitialHeapSize=535654144 -XX:MaxHeapSize=4294967296 -XX:+PrintGC -XX:+PrintGCTimeStamps -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:-UseLargePagesIndividualAllocation -XX:+UseParallelGC 
0.188: [GC (Allocation Failure)  131584K->114906K(502784K), 0.0795857 secs]
0.358: [GC (Allocation Failure)  246490K->229080K(634368K), 0.0794026 secs]
0.631: [GC (Allocation Failure)  492248K->452871K(716288K), 0.1389293 secs]
0.770: [Full GC (Ergonomics)     452871K->451407K(1188864K), 3.3224726 secs]
4.270: [GC (Allocation Failure)  714575K->714179K(1271808K), 0.2607092 secs]
4.531: [Full GC (Ergonomics)     714179K->814K(1050624K), 0.0070693 secs]

我得到这个大小:

Java HotSpot(TM) 64-Bit Server VM (25.51-b03) for windows-amd64 JRE (1.8.0_51-b16), built on Jun  8 2015 18:03:07 by "java_re" with MS VC++ 10.0 (VS2010)
Memory: 4k page, physical 33478384k(25818308k free), swap 33476532k(26123684k free)
CommandLine flags: -XX:InitialHeapSize=535654144 -XX:MaxHeapSize=4294967296 -XX:+PrintGC -XX:+PrintGCTimeStamps -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:-UseLargePagesIndividualAllocation -XX:+UseParallelGC 
0.171: [GC (Allocation Failure)  131584K->129070K(502784K), 0.0919490 secs]
0.370: [GC (Allocation Failure)  260654K->261166K(634368K), 0.4433150 secs]
0.813: [Full GC (Ergonomics)     261166K->260351K(899072K), 1.4135289 secs]
2.460: [GC (Allocation Failure)  523519K->524487K(899072K), 0.7901689 secs]
3.250: [Full GC (Ergonomics)     524487K->523517K(1421312K), 2.3177831 secs]

因为第二次运行最初分配了更多的内存,所以GC运行速度变慢.这显然超过了列表调整大小时进行的额外数组复制.