java - ¿Por qué esto es más lento cuando se le da a ArrayList una capacidad inicial?

performance capacity

Question

Para un experimento, hice este pequeño programa. Solo genera 10 millones de cadenas aleatorias y las agrega a un arraylist. Observe que el arraylist no tiene una capacidad inicial.

// 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);
}
}

Lo ejecuté 5 veces, y los resultados en ms fueron:

8917
8720
7814
8768
8867

Luego modifiqué el programa para darle una capacidad inicial a ArrayList:

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

Otra vez lo ejecuté 5 veces, y estos fueron los resultados:

11562
10454
10499
10481
10415

Definitivamente se volvió más lento. Asumí que habría sido todo lo contrario, ya que al declarar un tamaño inicial lo suficientemente grande, eliminé toda la sobrecarga de ArrayList aumentando su propia capacidad. ¿Por qué fue más lento?

Más información: Jre 1.8.051, 64 bits (en Windows 10);

Answer 1

La lista de randNums con 10 millones de elementos requiere aproximadamente 700 MB de espacio de memoria. Para evitar los efectos de GC (seguro que significa mucho en esta prueba), establezco los argumentos de Hotspot VM como este:

-XX:+PrintGC
-XX:+PrintGCTimeStamps
-XX:+UseParNewGC
-XX:+UseConcMarkSweepGC
-Xmx1000m
-Xms1000m
-Xmn999m
-XX:SurvivorRatio=65535

hacer que la generación Joven sea lo suficientemente grande como para guardar todos los elementos y no hacer GC durante la asignación de elementos. Hago más grande la Región Edén de Generación Joven para evitar que se copien elementos dentro de Generación Joven.
El resultado es sorprendente! . ¡El tiempo total de ejecución disminuye de 8s a 0.6s!

Aquí, hice un trabajo adicional para el interrogador, es decir, si la asignación previa de ArrayList puede ahorrar tiempo y cuánto ayuda.
Aquí está mi código:

 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();
}

La salida es:

-----------------------------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]

Striping GC info, es:

-----------------------------ArrayList With Enough Capacity Allocated:----------
615
540
480
511
480
-----------------------------ArrayList Auto-Capacity:----------
680
708
640
644
663

Usamos los últimos tres datos de cada grupo para calcular la optimización (para evitar la optimización de JIT y VM). La respuesta viene así:

(480+511+511)/(640+644+663) = 1502/1947 = 501/639 = 100/128

Answer 2

Uno pensaría que era al revés, pero tiene que ver con la recolección de basura.

No vi la gran diferencia que hiciste (3900 vs 5100), pero como esto está relacionado con GC, probablemente estés ejecutando con menos memoria. Corrí con 64-bit y -Xmx4g .

Al -Xloggc:path/to/file.log registro del GC ( -Xloggc:path/to/file.log ), obtengo esto sin tamaño:

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]

Y me sale esto con el tamaño:

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]

Debido a que la segunda ejecución asignó mucha más memoria inicialmente, la ejecución del GC se vuelve más lenta. Eso aparentemente supera la copia de matriz adicional que se produce cuando la lista cambia de tamaño.