ArrayList的性能表现

Question

ArrayList的性能表现

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毫秒的结果，如果我将List初始化更改为new ArrayList<Integer>(1000000)，则得到大约85毫秒。为什么会这样？难道不应该相反吗？实际上，没有预初始化的List比使用普通的Integer[]稍微快一点（约0.5-1毫秒）。基本上，它表明在插入性能方面，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％。但是有些用户似乎得到了正确的行为，所以这可能是一个非常特定的情况。 编辑2：如果我将元素替换为String，则行为是正确的（plain array > pre-capacity-ensured arraylist > default capacity array）。因此，自动装箱实际上是罪魁祸首。

- Hari Menon

12

首先，这不是一个良好的基准测试方式。您正在包括JIT预热时间，并使用currentTimeMillis而不是nanoTime。请尝试使用https://code.google.com/p/caliper/ - 另外，我怀疑您测试的大部分时间都花费在将一百万个int值封装成对象上。请尝试使用不需要在每次迭代中创建新对象的东西进行测试。 - Jon Skeet

2

只是一个有用的提示：运行测试两次，并查看第二次运行的结果。第一次运行通常会因为VM按需加载而受到污染。 - Kylar

@JonSkeet 包装（boxing）有什么不同之处吗？它不应该在所有测试中被视为常量吗？ - Sotirios Delimanolis

1

他的意思是说，大部分时间都花在了装箱上，而不是 ArrayList 的调整大小上。 - Steve Kuo

1

@Raze2dust：除非你已经显著修复了你基准测试的方式，否则我仍然深感怀疑。我强烈建议你改用Caliper。(我还怀疑你仍在使用装箱，但没有看到代码很难确定。只需使用List<String>和一些文字即可将其排除在外。) - Jon Skeet

显示剩余7条评论

2个回答

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

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

这表明你观察到的是可能的 - 当列表以较小的容量开始时，运行速度更快，节省的时间超过了后来的数组复制开销。

但是，当容量增加时为什么会变慢呢？我不确定。也许与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);
}

- ZhongYu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NPE · Accepted Answer

我进行了一些实验，我的结论是你的基准测试存在缺陷。当我解决了最明显的问题时，得到的结果截然不同。我的计时如下：

默认列表：74毫秒
预先设定大小的列表：54毫秒
整数数组：42毫秒
int数组：9毫秒

请注意，这些是以毫秒为单位的。你的代码执行测量值为十毫秒：(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微基准测试？