Java - LinkedList - Performance decreases with the number of different classes in it

Question

The following code measure the time it takes for 100 invocations of the method handle(Object o) from the interface Handler (Yes it's bad quality profiling):

package test;

import java.util.LinkedList;

public class Test {

    static int i = 0;

    private interface Handler {
        public void handle(Object o);
    }
    private static class SuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class NoSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LulSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LilSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LolSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LalSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LylSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }
    private static class LzlSuperHandler implements Handler {
        public void handle(Object o) { i += 1; }
    }

    public static void main(String[] args) {
        LinkedList<Handler> ll = new LinkedList<Handler>();
        for(int j = 0; j < 100; j++) {
            if((j % 8) == 0) ll.add(new SuperHandler());
            if((j % 8) == 1) ll.add(new NoSuperHandler());
            if((j % 8) == 2) ll.add(new LulSuperHandler());
            if((j % 8) == 3) ll.add(new LilSuperHandler());
            if((j % 8) == 4) ll.add(new LolSuperHandler());
            if((j % 8) == 5) ll.add(new LalSuperHandler());
            if((j % 8) == 6) ll.add(new LylSuperHandler());
            if((j % 8) == 7) ll.add(new LzlSuperHandler());
        }
        long begin = System.currentTimeMillis();
        for(int j = 0; j < 1000000; j++) for(Handler h: ll) h.handle(null);
        System.out.println("time in ms: " + (System.currentTimeMillis() - begin));
        System.out.println("i: " + i);
    }
}

The fact is that if the LinkedList contains only one kind of Handler, for example SuperHandler, the execution time is smaller than if they were 2, 3, etc different kinds of Handler. And every time I add a new kind of Handler in the list, the performances decreases.

For example when I change only this part I get better performances than above:

for(int j = 0; j < 100; j++) {
    if((j % 2) == 0) ll.add(new SuperHandler());
    if((j % 2) == 1) ll.add(new NoSuperHandler());
}

Is there a special optimization operating here ? What in the JAVA architecture does the performances decrease ? Is my test wrong because the unused Handler are "removed", or "hidden" by the compiler ? (I'm using Linux Ubuntu - JAVA 1.7, from Oracle)

Answer 1

Is there a special optimization operating here ?

Yes. Hotspot is very clever about how it handles virtual methods. If there are only a couple of implementations of an interface, and those implementations are small, it can avoid a full vtable-lookup by just checking for the right type, and inlining the code.

By the time you've got several different implementations, it goes back to the vtable implementation. (Hotspot is clever enough to undo optimizations which are no longer practical. I'm shocked that it all hangs together, but apparently it does.)

Note that this isn't a matter of how many different classes are in the list - there's rather more going on here. See Peter's answer for details.

Answer 2

I agree with Jon's answer except I believe that it's the number of types called at the point of the code which makes the difference. In the following example, all 8 classes are loaded and the same code runs for the same number of elements in the list, except one list has 8 and the other has 2 different types.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {

    static int i = 0;

    private interface Handler {
        public void handle();
    }

    public static void main(String[] args) {
        List<Handler> ll8 = new ArrayList<Handler>();
        for (int j = 0; j < 128; j += 8) {
            ll8.add(new SuperHandler());
            ll8.add(new NoSuperHandler());
            ll8.add(new LulSuperHandler());
            ll8.add(new LilSuperHandler());
            ll8.add(new LolSuperHandler());
            ll8.add(new LalSuperHandler());
            ll8.add(new LylSuperHandler());
            ll8.add(new LzlSuperHandler());
        }
        List<Handler> ll2 = new ArrayList<Handler>();
        for (int j = 0; j < 128; j += 2) {
            ll2.add(new SuperHandler());
            ll2.add(new NoSuperHandler());
        }
        for (int j = 0; j < 5; j++) {
            test8(ll8);
            test8a(ll8);
            test2(ll2);
        }
        System.out.println("i: " + i);
    }

    private static void test8(List<Handler> ll8) {
        long begin = System.nanoTime();
        for (int j = 0; j < 1000000; j++) for (Handler h : ll8) h.handle();
        System.out.println("8 classes, time in ms: " + (System.nanoTime() - begin) / 100000 / 10.0);
    }

    private static void test8a(List<Handler> ll8) {
        long begin = System.nanoTime();
        for (int j = 0; j < 1000000; j++)
            for (int k = 0; k < ll8.size(); k += 8) {
                ll8.get(k + 0).handle();
                ll8.get(k + 1).handle();
                ll8.get(k + 2).handle();
                ll8.get(k + 3).handle();
                ll8.get(k + 4).handle();
                ll8.get(k + 5).handle();
                ll8.get(k + 6).handle();
                ll8.get(k + 7).handle();
            }
        System.out.println("8 classes unrolled, time in ms: " + (System.nanoTime() - begin) / 100000 / 10.0);
    }

    private static void test2(List<Handler> ll2) {
        long begin = System.nanoTime();
        for (int j = 0; j < 1000000; j++) for (Handler h : ll2) h.handle();
        System.out.println("2 classes, time in ms: " + (System.nanoTime() - begin) / 100000 / 10.0);
    }

    private static class SuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class NoSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LulSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LilSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LolSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LalSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LylSuperHandler implements Handler {
        public void handle() { i += 1; }
    }

    private static class LzlSuperHandler implements Handler {
        public void handle() { i += 1; }
    }
}

prints

8 classes, time in ms: 1467.9
8 classes unrolled, time in ms: 144.7
2 classes, time in ms: 515.8
8 classes, time in ms: 1455.1
8 classes unrolled, time in ms: 126.2
2 classes, time in ms: 509.6
8 classes, time in ms: 1234.1
8 classes unrolled, time in ms: 107.8
2 classes, time in ms: 274.3
8 classes, time in ms: 1212.0
8 classes unrolled, time in ms: 108.1
2 classes, time in ms: 273.0
8 classes, time in ms: 1208.8
8 classes unrolled, time in ms: 107.8
2 classes, time in ms: 274.5
i: 1920000000