Performance Collections.emptyList and empty ArrayList with JIT compiler

Question

Is there a performance difference between using Collections.emptyList() or an empty ArrayList , especially when using the JIT compiler?

I could imagine that, for example, the JIT compiler does not execute inlays or static method calls, because the method being executed depends on the type.

Edit I know that Collections.emptyList() returns an immutable list, while ArrayList is a mutable object.

I mean, if I pass one or the other method as a parameter, and the method does not change the list, does this limit the ability of the JIT compiler to optimize the method?

A simple example (just to clarify what I mean):

 int sum(List<Integer> list) { int sum = 0; for(int i=0;i<list.size();++i) sum += list.get(i); return sum; } 

If I called this method only using ArrayList , the JIT compiler could inline ArrayList.get() . If I also made calls using Collections.empty() , that would be impossible.

Is it correct?

Answer 1

Legal information

Everything written below applies only to HotSpot JVM .

Short answers

The JIT compiler does not make built-in or static method calls, because the method executed is type-dependent.

This is the opposite of truth. See my answer.

Is there a performance difference between Collections.emptyList () or an empty ArrayList, especially when using the JIT compiler?

In rare cases, yes. See Microdetection Results.

If I just called this method with an ArrayList, the JIT compiler could inline ArrayList.get (). If I also made calls with Collections.empty (), that would be impossible. It is right?

The short answer is that it depends. The JIT compiler is smart enough to recognize monomorphic, bimorph, and polymorphic call patterns and provide appropriate implementations.

Answer

To get a detailed answer, I would recommend reading the following article on the black magic of submitting a method. In a few words

C2 performs an interesting profile-based optimization based on an observable type profile. If there is only one type of receiver (which is, the call site is monomorphic), it can simply check for the predicted type and direct inclusion of the target. The same optimization can and will be applied if two types of receivers are observed (that is, the call site is bimorph), due to two branches.

Consider the following JMH example (if you did not find out about JMH, then I suggest reading about it here ).

 @State(Scope.Benchmark) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Fork(value = 5) public class ExampleBench { @Param("10000") private int count; List<Integer>[] arrays; List<Integer>[] empty; List<Integer>[] bimorphic; List<Integer>[] polimorphic; @Setup public void setup(){ Random r = new Random(0xBAD_BEEF); arrays = new List[count]; empty = new List[count]; bimorphic = new List[count]; polimorphic = new List[count]; for (int i = 0; i < arrays.length; i++) { bimorphic[i] = r.nextBoolean() ? new ArrayList<Integer>(0) : Collections.<Integer>emptyList(); int i1 = r.nextInt(3); switch (i1) { case 0 : polimorphic[i] = new ArrayList<>(0); break; case 1 : polimorphic[i] = new LinkedList<>(); break; case 2 : polimorphic[i] = Collections.emptyList(); break; } arrays[i] = new ArrayList<>(0); empty[i] = Collections.emptyList(); } } @Benchmark public float arrayList() { List<Integer>[] l = arrays; int c = count; float result = 0; for (int i = 0; i < c; i++) { result += sum(l[i]); } return result; } @Benchmark public float emptyList() { List<Integer>[] l = empty; int c = count; float result = 0; for (int i = 0; i < c; i++) { result += sum(l[i]); } return result; } @Benchmark public float biList() { List<Integer>[] l = bimorphic; int c = count; float result = 0; for (int i = 0; i < c; i++) { result += sum(l[i]); } return result; } @Benchmark public float polyList() { List<Integer>[] l = polimorphic; int c = count; float result = 0; for (int i = 0; i < c; i++) { result += sum(l[i]); } return result; } int sum(List<Integer> list) { int sum = 0; for (int i = 0; i < list.size(); ++i) { sum += list.get(i); } return sum; } } 

Results:

 Benchmark (count) Mode Cnt Score Error Units ExampleBench.arrayList 10000 avgt 5 22902.547 ± 27665.651 ns/op ExampleBench.biList 10000 avgt 5 50459.552 ± 739.379 ns/op ExampleBench.emptyList 10000 avgt 5 3745.469 ± 211.794 ns/op ExampleBench.polyList 10000 avgt 5 164879.943 ± 5830.008 ns/op 

In the case of monomorphic and bimorphic calls, JIT replaces the virtual call with specific implementations. For example, in the case of arrayList() we have the following output for -XX:+PrintInlining :

 @ 27 edu.jvm.runtime.ExampleBench::sum (38 bytes) inline (hot) @ 6 java.util.ArrayList::size (5 bytes) accessor \-> TypeProfile (15648/15648 counts) = java/util/ArrayList 

for emptyList() :

 @ 27 edu.jvm.runtime.ExampleBench::sum (38 bytes) inline (hot) @ 6 java.util.Collections$EmptyList::size (2 bytes) inline (hot) \-> TypeProfile (9913/9913 counts) = java/util/Collections$EmptyList 

for biList() :

 @ 27 edu.jvm.runtime.ExampleBench::sum (38 bytes) inline (hot) @ 6 java.util.Collections$EmptyList::size (2 bytes) inline (hot) @ 6 java.util.ArrayList::size (5 bytes) accessor \-> TypeProfile (2513/5120 counts) = java/util/ArrayList \-> TypeProfile (2607/5120 counts) = java/util/Collections$EmptyList 

In the case of polyList() JIT does not execute any implementation and uses a true virtual call.

What are the benefits of using built-in functions in these methods? Let's look at the code generated by the compiler for arrayList() :

 0x00007ff9e51bce50: cmp $0xf80036dc,%r10d ;instance of 'java/util/ArrayList' 0x00007ff9e51bce57: jne L0000 ;if false go to L0000 (invokeinterface size) 0x00007ff9e51bce59: mov 0x10(%rdx),%ebp ;*getfield size optimization java.util.ArrayList::size@1 ..... 0x00007ff9e51bce6d: retq L0000: mov $0xffffffde,%esi ; true virtual call starts here 0x00007ff9e51bce73: mov %rdx,(%rsp) 0x00007ff9e51bce77: callq 0x00007ff9e50051a0 ; OopMap{[0]=Oop off=92} ;*invokeinterface size ; - edu.jvm.runtime.ExampleBench::sum@6 (line 119) ; {runtime_call} 

As you can see, JIT replaces the virtual call with getfield .

Answer 2

Collections.emptyList () always returns the same immutable empty list object (singleton). Creating an ArrayList on the other hand actually creates a new object, allocates memory, and this object must be GCed later.

There should not be a significant difference, but Collections.emptyList () does less work. Operations are not functionally equivalent. One allows you to get an immutable empty list, while the other allows you to create a new mutable list. Select an option based on the desired function. Not for performance reasons.

Answer 3

Collections.emptyList() and empty new ArrayList<>() work a little differently. The list returned by Collections is not only empty, it is immutable, so the list itself can be saved as a singleton and returned with every call to the emptyList () method (due to type erasure, this is possible for any type of classifier).

So, the answer depends on what you are going to do with the empty list. If you are going to return an empty list in some of your code as the final value, Collections.emptyList() is definitely better (it doesn't even create a new object). If you intend to set up an empty list for further modifications, Collections.emptyList() completely unacceptable