Performance of 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 a JIT compiler?

I could imagine that - for example - the JIT compiler doesn't do inlining or static method calls because the executed method depends on the type.

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

What I mean is that if I pass one or the other to a method as a parameter and the method doesn't modify the list does that restrict the possibilities for 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 only called this method with ArrayList the JIT compiler could inline ArrayList.get(). If I also made calls with Collections.empty() it wouldn't be possible.

Is that correct?

Resist

The JIT doesn't care about the actual type of the list passed to the method. It doesn't even know: you could pass an empty list 10% of the time, an ArrayList 45% of the time, a LinkedList 15% of the type and a CopyOnWriteArrayList the rest of the time. Why would that prevent it from optimizing the method? – Constrict

@JBNizet The JIT compiler knows the loaded bytecode and therefore can know if a method only gets one type of objects. My scenerio is only passing ArrayList vs. passing ArrayList and empty list. You're right otherwise. – Resist

So, you're asking if there would be a difference for the JIT between a method declared as foo(List<Bar> list) and foo(ArrayList<Bar> list), right? If not, clarify. Post code. But anyway, make your design clean instead of trying to optimize prematurely things that don't need to be optimized anyway. Java uses pulyporphism, and the JIT is able to handle it. No worry about that. – Constrict

@JBNizet I've once read that the JIT compiler creates different code if there is only one implementation for an interface. I think this may also apply here. I'm not using this for optimization BTW, I just trying to understand the JIT compiler. – Resist

But there are many, many implementations of List, so it clearly doesn't apply here. – Constrict

@JBNizet I know that's not the same. I wouldn't had asked the question if I had thought that. – Resist

Answer 1

Disclamer

All that is written below applies only to HotSpot JVM.

Short Answers

the JIT compiler doesn't do inlining or static method calls because the executed method depends on the type.

This is opposite of true. See my answer.

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

In rare cases - yes. See microbenchmark results.

If I only called this method with ArrayList the JIT compiler could inline ArrayList.get(). If I also made calls with Collections.empty() it wouldn't be possible. Is that correct?

The short answer - it depends. JIT compiler is smart enough to recognize monomorphic, bimorphic and polimorphic call patterns and provide appropriate implementations.

Answer

In order to get a detailed answer I would recommend to read the following post about black magic of method dispatching. In few words

C2 does an interesting profile-guided optimization based on the observed type profile. If there is only a single receiver type (that is, the call site is monomorphic), it can simply check for the predicted type, and inline the target directly. The same optimization can and will be applied if there are two receiver types observed (that is, the call site is bimorphic), at the cost of two branches.

Let's consider the following JMH example(if you haven’t learned about JMH then I suggest to read 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 are:

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 case of monomorphic and bimorphic calls JIT replaces virtual call by concrete implementations. For example in 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 case of polyList() JIT does not inline any implementation and uses true virtual call.

What is the advantages of using inline functions in these methods? Let's look at compiler-generated code 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 virtual call by getfield.

Dominoes

Nice job. The comparison would be more relevant if you add some elements to the lists. For example, leave only arrays and bimorphic tests, in bimorphic replace non-empty ArrayLists with ArrayLists containing some elements and randomly interleave empty and non-empty lists in arrays. This way you may get the idea how this slows down more real-world scenario... – Faulty

Answer 2

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

There shouldn't be a significant difference, but Collections.emptyList() does less work. The operations are not functionally equivalent. One allows getting an immutable empty list, whereas the other allows creating a new mutable list. Choose one or the other based on the functionality you want. Not for performance reasons.

Constrict

Answer 3

Collections.emptyList() and empty new ArrayList<>() work slightly different. List returned by Collections is not only empty, it is immutable, so that very list can be stored as singleton and returned on every call to emptyList() (thanks to type erasure, this is possible for any type qualifiers).

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

Scandura