java - 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 毫秒，而如果我将列表初始化更改为 new ArrayList<Integer>(1000000)，我得到约 85 毫秒.为什么会这样？不应该反过来吗？事实上，没有预初始化的列表始终比使用普通 Integer[] 快一点点(~0.5-1 毫秒) .基本上，它说的是 default capacity arraylist > simple array > pre-capacity-ensured arraylist在插入性能方面。

这对我来说很奇怪。我最初的猜测是它与内存分配有关，比如一次性提供 1000000 个 int block 可能比慢慢获得更多空间更慢？这甚至可以在其他机器上重现吗？我正在使用 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 )。所以我认为自动装箱实际上是罪魁祸首。

Answer 1

我对此进行了一些试验，我的结论是您的基准测试存在缺陷。当我解决最明显的问题时，我会得到截然不同的结果。我的时间安排如下:

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

Note that these are in units of milliseconds. Your code performs measurements in tens of milliseconds: (t2-t1)/10.0.

For reference, the code I've used is as follows:

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 代码进行基准测试的一些指示，请参阅 How do I write a correct micro-benchmark in Java?