Java - LinkedList - 随着其中不同类的数量增加，性能会下降。

Question

以下代码测量了调用接口Handler中方法handle（Object o）100次所需的时间（是低质量的性能分析）：

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

事实上，如果LinkedList仅包含一种Handler类型，例如SuperHandler，执行时间比包含2个、3个等不同类型的Handler要短。每次我将一个新类型的Handler添加到列表中，性能都会降低。

例如，当我仅更改此部分时，性能比上面的更好：

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

这里有一些特别的优化操作吗？在JAVA架构中，性能下降是由什么引起的？如果未使用的Handler被“删除”或编译器“隐藏”，那么我的测试是否有误？（我正在使用Linux Ubuntu - Oracle的JAVA 1.7）

- Badabada125

Answer 1

这里有一个特殊的优化操作吗？

是的。Hotspot在处理虚拟方法时非常聪明。如果接口只有几个实现，并且这些实现很小，它可以通过检查正确的类型并内联代码来避免完整的vtable查找。

当你有几个不同的实现时，它会回到vtable实现。(Hotspot足够聪明，可以撤消不再实用的优化。我很震惊，但显然它确实可以胜任。)

请注意，这不是列表中有多少不同类的问题 - 这里还有更多内容。有关详细信息，请参见Peter的答案。

- Jon Skeet

---

据我所知，在HotSpot中内联虚方法的限制为2。我不确定仅加载类是否足以触发去优化。 - Peter Lawrey

@PeterLawrey：啊，感谢您的额外澄清。我会进行编辑。 - Jon Skeet

看我的答案就能明白。我有一个列表，在其中一个地方调用了8种不同类型，另一个列表中则将8个不同的调用排成一行，只调用了一种类型（但是从同一个列表中）。性能差异非常明显。 - Peter Lawrey

Answer 2

我同意Jon的答案，但我认为在代码执行时调用的类型数量才是造成差异的原因。在下面的例子中，所有8个类都被加载，并且对于列表中相同数量的元素运行相同的代码，但一个列表有8个不同类型的元素，而另一个只有2个。

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

打印

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

- Peter Lawrey

---

非常有趣的回答，以及相关的代码，谢谢（我也因为限制得到了2个）。我必须说，我对这些优化印象非常深刻。您的代码每次读取8x8的数组。如果您使用4或8的任意倍数，则可能会进行优化。 - Badabada125

在展开的情况下，每次调用的类型始终相同（但对于每个类型都不同）。 - Peter Lawrey