为什么给 ArrayList 一个初始容量时会变慢？
Why is this slower when giving ArrayList an initial capacity?
为了实验，我做了这个小程序。它只生成 1000 万个 运行dom 字符串并将它们添加到数组列表中。请注意，arraylist not 具有初始容量。
// 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次，以毫秒为单位的结果是：
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 上）；
你可能认为它是相反的，但它与垃圾收集有关。
我没有看到你做的有什么大的不同（3900 与 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 运行 变得更慢。这显然超过了列表调整大小时进行的额外数组复制。
列出具有 1000 万个元素的 randNums 需要大约 700MB 内存Space。
为了避免GC的影响（当然，这在这个测试中意义重大），我这样设置了Hotspot VM参数：
-XX:+PrintGC
-XX:+PrintGCTimeStamps
-XX:+UseParNewGC
-XX:+UseConcMarkSweepGC
-Xmx1000m
-Xms1000m
-Xmn999m
-XX:SurvivorRatio=65535
使新生代足够大以保存所有元素并且在元素分配期间不进行GC。我把年轻一代的伊甸园区域变大，以避免在年轻一代中复制元素。
结果令人惊讶！。总执行时间从 8 秒减少到 0.6 秒！
在这里，我为提问者做了一些额外的工作，即测试ArrayList的预分配是否可以节省时间以及有多大帮助。
这是我的代码：
long startTime;
List<String> randNums;
Random r = new Random(1);
System.out.println("-----------------------------ArrayList With Enough Capacity Allocated:----------");
for(int loop=0;loop<5;loop++) {
startTime = System.currentTimeMillis();
randNums = new ArrayList<String>(SIZE);
for (int i = 0; i <SIZE ; i++) {
int randomNum = r.nextInt();
randNums.add(Integer.toString(randomNum));
}
System.out.println(System.currentTimeMillis() - startTime); //print time of this loop
randNums.clear();
System.gc();
}
System.out.println("\n-----------------------------ArrayList Auto-Capacity:----------");
for(int loop=0;loop<5;loop++) {
startTime = System.currentTimeMillis();
randNums = new ArrayList<String>();
for (int i = 0; i <SIZE ; i++) {
int randomNum = r.nextInt();
randNums.add(Integer.toString(randomNum));
}
System.out.println(System.currentTimeMillis() - startTime); //print time of this loop
randNums.clear();
System.gc();
}
输出为：
-----------------------------ArrayList With Enough Capacity Allocated:----------
625
0.712: [Full GC (System.gc()) 714143K->39628K(1023936K), 0.1450449 secs]
0.863: [GC (CMS Initial Mark) 98268K(1023936K), 0.0549729 secs]
545
1.413: [Full GC (System.gc()) 705185K->564K(1023936K), 0.1239084 secs]
483
2.031: [Full GC (System.gc()) 679570K->564K(1023936K), 0.1256323 secs]
2.160: [GC (CMS Initial Mark) 59357K(1023936K), 0.0274108 secs]
523
2.688: [Full GC (System.gc()) 670987K->564K(1023936K), 0.1222910 secs]
482
3.302: [Full GC (System.gc()) 673223K->564K(1023936K), 0.1299938 secs]
-----------------------------ArrayList Auto-Capacity:----------
3.432: [GC (CMS Initial Mark) 40961K(1023936K), 0.0003740 secs]
3.907: [GC (CMS Final Remark) 698381K(1023936K), 0.1091347 secs]
796
4.240: [Full GC (System.gc()) 911984K->56183K(1023936K), 0.1719540 secs]
4.412: [GC (CMS Initial Mark) 56183K(1023936K), 0.0394210 secs]
4.770: [GC (CMS Final Remark) 528894K(1023936K), 0.0726012 secs]
690
5.111: [Full GC (System.gc()) 893818K->2060K(1023936K), 0.1364215 secs]
5.248: [GC (CMS Initial Mark) 20769K(1023936K), 0.0008902 secs]
5.750: [GC (CMS Final Remark) 694113K(1023936K), 0.1124856 secs]
704
5.962: [Full GC (System.gc()) 808646K->2081K(1023936K), 0.1338328 secs]
6.096: [GC (CMS Initial Mark) 21137K(1023936K), 0.0010118 secs]
6.599: [GC (CMS Final Remark) 688155K(1023936K), 0.0899929 secs]
661
6.767: [Full GC (System.gc()) 810872K->2081K(1023936K), 0.1287272 secs]
6.896: [GC (CMS Initial Mark) 21512K(1023936K), 0.0010619 secs]
7.398: [GC (CMS Final Remark) 691216K(1023936K), 0.1083076 secs]
681
7.586: [Full GC (System.gc()) 803590K->2081K(1023936K), 0.1269813 secs]
7.714: [GC (CMS Initial Mark) 2081K(1023936K), 0.0008965 secs]
条带化 GC 信息，它是：
-----------------------------ArrayList With Enough Capacity Allocated:----------
615
540
480
511
480
-----------------------------ArrayList Auto-Capacity:----------
680
708
640
644
663
我们使用每组的最后三个数据计算优化（避免 JIT 和 VM 优化）。答案是这样的：
(480+511+511)/(640+644+663) = 1502/1947 = 501/639 = 100/128
为了实验，我做了这个小程序。它只生成 1000 万个 运行dom 字符串并将它们添加到数组列表中。请注意，arraylist not 具有初始容量。
// 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次，以毫秒为单位的结果是：
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 上）；
你可能认为它是相反的，但它与垃圾收集有关。
我没有看到你做的有什么大的不同（3900 与 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 运行 变得更慢。这显然超过了列表调整大小时进行的额外数组复制。
列出具有 1000 万个元素的 randNums 需要大约 700MB 内存Space。 为了避免GC的影响（当然，这在这个测试中意义重大），我这样设置了Hotspot VM参数：
-XX:+PrintGC
-XX:+PrintGCTimeStamps
-XX:+UseParNewGC
-XX:+UseConcMarkSweepGC
-Xmx1000m
-Xms1000m
-Xmn999m
-XX:SurvivorRatio=65535
使新生代足够大以保存所有元素并且在元素分配期间不进行GC。我把年轻一代的伊甸园区域变大，以避免在年轻一代中复制元素。
结果令人惊讶！。总执行时间从 8 秒减少到 0.6 秒！
在这里，我为提问者做了一些额外的工作，即测试ArrayList的预分配是否可以节省时间以及有多大帮助。
这是我的代码：
long startTime;
List<String> randNums;
Random r = new Random(1);
System.out.println("-----------------------------ArrayList With Enough Capacity Allocated:----------");
for(int loop=0;loop<5;loop++) {
startTime = System.currentTimeMillis();
randNums = new ArrayList<String>(SIZE);
for (int i = 0; i <SIZE ; i++) {
int randomNum = r.nextInt();
randNums.add(Integer.toString(randomNum));
}
System.out.println(System.currentTimeMillis() - startTime); //print time of this loop
randNums.clear();
System.gc();
}
System.out.println("\n-----------------------------ArrayList Auto-Capacity:----------");
for(int loop=0;loop<5;loop++) {
startTime = System.currentTimeMillis();
randNums = new ArrayList<String>();
for (int i = 0; i <SIZE ; i++) {
int randomNum = r.nextInt();
randNums.add(Integer.toString(randomNum));
}
System.out.println(System.currentTimeMillis() - startTime); //print time of this loop
randNums.clear();
System.gc();
}
输出为：
-----------------------------ArrayList With Enough Capacity Allocated:----------
625
0.712: [Full GC (System.gc()) 714143K->39628K(1023936K), 0.1450449 secs]
0.863: [GC (CMS Initial Mark) 98268K(1023936K), 0.0549729 secs]
545
1.413: [Full GC (System.gc()) 705185K->564K(1023936K), 0.1239084 secs]
483
2.031: [Full GC (System.gc()) 679570K->564K(1023936K), 0.1256323 secs]
2.160: [GC (CMS Initial Mark) 59357K(1023936K), 0.0274108 secs]
523
2.688: [Full GC (System.gc()) 670987K->564K(1023936K), 0.1222910 secs]
482
3.302: [Full GC (System.gc()) 673223K->564K(1023936K), 0.1299938 secs]
-----------------------------ArrayList Auto-Capacity:----------
3.432: [GC (CMS Initial Mark) 40961K(1023936K), 0.0003740 secs]
3.907: [GC (CMS Final Remark) 698381K(1023936K), 0.1091347 secs]
796
4.240: [Full GC (System.gc()) 911984K->56183K(1023936K), 0.1719540 secs]
4.412: [GC (CMS Initial Mark) 56183K(1023936K), 0.0394210 secs]
4.770: [GC (CMS Final Remark) 528894K(1023936K), 0.0726012 secs]
690
5.111: [Full GC (System.gc()) 893818K->2060K(1023936K), 0.1364215 secs]
5.248: [GC (CMS Initial Mark) 20769K(1023936K), 0.0008902 secs]
5.750: [GC (CMS Final Remark) 694113K(1023936K), 0.1124856 secs]
704
5.962: [Full GC (System.gc()) 808646K->2081K(1023936K), 0.1338328 secs]
6.096: [GC (CMS Initial Mark) 21137K(1023936K), 0.0010118 secs]
6.599: [GC (CMS Final Remark) 688155K(1023936K), 0.0899929 secs]
661
6.767: [Full GC (System.gc()) 810872K->2081K(1023936K), 0.1287272 secs]
6.896: [GC (CMS Initial Mark) 21512K(1023936K), 0.0010619 secs]
7.398: [GC (CMS Final Remark) 691216K(1023936K), 0.1083076 secs]
681
7.586: [Full GC (System.gc()) 803590K->2081K(1023936K), 0.1269813 secs]
7.714: [GC (CMS Initial Mark) 2081K(1023936K), 0.0008965 secs]
条带化 GC 信息，它是：
-----------------------------ArrayList With Enough Capacity Allocated:----------
615
540
480
511
480
-----------------------------ArrayList Auto-Capacity:----------
680
708
640
644
663
我们使用每组的最后三个数据计算优化（避免 JIT 和 VM 优化）。答案是这样的：
(480+511+511)/(640+644+663) = 1502/1947 = 501/639 = 100/128