7

我试图查看预初始化ArrayList给定容量与使用默认容量和扩展需求之间的性能差异。只是出于好奇。我发现默认容量数组代码比将数组初始化为所需容量的代码快10% 。这是我使用的代码：

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 ms，而如果我将 List 初始化更改为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）。所以我认为自动装箱实际上是罪魁祸首。

4

2 回答 2

5

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

默认列表：74ms
预大小列表：54ms
整数数组：42ms
整数数组：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 中编写正确的微基准测试？

于 2013-04-03T14:41:07.443 回答
0

add()让我们做这个实验，在不同容量的列表上测量单个 所需的时间

        ArrayList<Integer> list = new ArrayList<Integer>(N);
        for(int i=0;i<N;++i) 
            list.add(new Integer(i));  // how many ns does this take?

在我的机器上

       N      ns per add(new)

   32000      10
   64000      10
  128000      10
  256000      10
  512000      11
 1024000      11
 2048000      11
 4096000      15
 8192000      48
16384000     132
    1000      23
    2000      13
    4000      11
    8000      11
   16000      11
   32000      10

显然，填充 4 个容量为 2M 的列表比填充 1 个容量为 8M 的列表要快得多。

这表明您观察到的情况是可能的 - 当列表以小容量开始时，事情运行得更快，并且节省的时间超过了以后的数组复制开销。

但是为什么容量增加后会变慢呢？我不确定。也许它与L2缓存有关。也许 JVM 在分配更大的数组时有更多的开销。

测试代码：

static void test(int N)
{
    long t0 = System.nanoTime();
    long x = 0;
    long t = 0;
    while(true)
    {
        ArrayList<Integer> list = new ArrayList<Integer>(N);
        for(int i=0;i<N;++i)
            list.add(new Integer(i));

        t = System.nanoTime()-t0;
        x+=N;

        if(t>1000_000_000)
            break;
    }

    System.out.printf("%8s\t%4s%n", N, t/x);
}

public static void main(String[] args)
{
    while(true)
        for(int N=1000; N<20_000_000; N*=2)
            test(N);
}
于 2013-04-03T16:22:11.797 回答