ArrayList的性能

Question

我试图看到预先初始化ArrayList给定容量与使用默认容量和扩展需求之间的性能差异.只是出于好奇.我发现,缺省容量阵列码是〜10%FASTER比初始化数组所需的容量的代码.这是我使用的代码:

public class Test {
    public static void main(String[] args) {

        long t1 = System.currentTimeMillis();
        for(int j=0;j<10;++j) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<1000000;++i) {
                list.add(i);
            }
        }
        long t2 = System.currentTimeMillis();
        System.out.println("Time taken: " + (t2-t1)/10.0);
    }
}

我的盒子上的这个版本一直得到~77毫秒,而如果我将列表初始化改为,我得到~85毫秒new ArrayList<Integer>(1000000).为什么会这样？不应该反过来吗？事实上,没有pre-init的List一直比使用plain更快(~0.5-1 ms)Integer[].基本上,它说的是default capacity arraylist > simple array > pre-capacity-ensured arraylist插入性能.

这对我来说很奇怪.我最初的猜测是它与内存分配有关,比如一次性给出1000000个int块可能比慢慢获得更多空间慢？这在其他机器中是否可以重现？我正在使用jdk 1.6.0,Mac OS X,运行eclipse.

我在其他两个环境中尝试过: - >尝试从命令行而不是eclipse运行java + javac - 这是我得到的pre-capacity-ensured arraylist > simple array > default capacity arraylist,一贯的.

- >尝试在我的linux(RHEL)桌面上运行java + javac.这个盒子有24 GB RAM,而我的笔记本电脑只有8 GB.在这里,我明白了plain array >>> default capacity arraylist > pre-capacity-ensured arraylist.普通阵列超快,在这种情况下比其他两个快约2-3倍.

编辑:在评论中关注@ JonSkeet的建议,我使用了nanoTime(),而Integer不是int.它仍然没有解决JIT热身未被考虑的问题.经过这些更改后,我始终看到普通数组在所有测试中都是最快的.但是,与上面所有3种环境中的默认容量列表相比,容量保证列表仍然慢了大约5-10%.但是有些用户似乎得到了正确的行为,所以这可能是一个非常具体的案例.

EDIT2:如果我使用String而不是Integer作为元素,行为是正确的(plain array > pre-capacity-ensured arraylist > default capacity array).所以我认为autoboxing实际上是罪魁祸首.

Answer 1

我已经尝试了一点,我的结论是你的基准是有缺陷的.当我解决最明显的问题时,我会得到截然不同的结果.我的时间如下:

default list: 74ms
pre-sized list: 54ms
Integer array: 42ms
int array: 9ms

请注意,这些以毫秒为单位.您的代码在几十毫秒内执行测量:(t2-t1)/10.0.

作为参考,我使用的代码如下:

public class Clazz {

    static final int N = 1000000;

    interface Test {
        void test();
    }
    static final class DfltListTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                List<Integer> list = new ArrayList<Integer>();
                for (int i = 0; i < N; ++i) {
                    list.add(i);
                }
            }
        }
    }
    static final class SizedListTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                List<Integer> list = new ArrayList<Integer>(N);
                for (int i = 0; i < N; ++i) {
                    list.add(i);
                }
            }
        }
    }
    static final class IntegerArrayTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                Integer[] arr = new Integer[N];
                for (int i = 0; i < N; ++i) {
                    arr[i] = i;
                }
            }
        }
    }
    static final class IntArrayTest implements Test {
        public void test() {
            for (int j = 0; j < 10; ++j) {
                int[] arr = new int[N];
                for (int i = 0; i < N; ++i) {
                    arr[i] = i;
                }
            }
        }
    }

    static void test(Test t, String name) {
        final int iter = 11;
        final long timings[] = new long[iter];
        for (int k = 0; k < iter; ++k) {
            long t1 = System.currentTimeMillis();
            t.test();
            long t2 = System.currentTimeMillis();
            timings[k] = t2 - t1;
            System.gc();
        }
        Arrays.sort(timings);
        System.out.printf("%s: %dms\n", name, timings[iter / 2]);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; ++i) {
            test(new DfltListTest(), "default list");
            test(new SizedListTest(), "pre-sized list");
            test(new IntegerArrayTest(), "Integer array");
            test(new IntArrayTest(), "int array");
        }
    }
}

我用Java 1.7.0_09测试过它-XX:+AggressiveOpts -XX:CompileThreshold=1.

当我使用Java 6测试相同的代码时,排名是相同的,但默认列表和预先调整大小的列表之间的差异更为显着.我并没有试图理解Java 7的含义是如此之小.

有关如何对Java代码进行基准测试的一些指示,请参阅如何在Java中编写正确的微基准测试？