Java - Vector vs ArrayList 性能测试

Question

大家都说应该使用向量，因为它可以提高性能（因为向量在每次操作后同步）。我写了一个简单的测试：

import java.util.ArrayList;
import java.util.Date;
import java.util.Vector;

public class ComparePerformance {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Vector<Integer> vector = new Vector<Integer>();

        int size = 10000000;
        int listSum = 0;
        int vectorSum = 0;

        long startList = new Date().getTime();
        for (int i = 0; i < size; i++) {
            list.add(new Integer(1));
        }
        for (Integer integer : list) {
            listSum += integer;
        }
        long endList = new Date().getTime();
        System.out.println("List time: " + (endList - startList));

        long startVector = new Date().getTime();
        for (int i = 0; i < size; i++) {
            vector.add(new Integer(1));
        }
        for (Integer integer : list) {
            vectorSum += integer;
        }
        long endVector = new Date().getTime();
        System.out.println("Vector time: " + (endVector - startVector));
    }
}

结果如下：

List time: 4360
Vector time: 4103

根据这个看起来，Vector 在迭代和读取方面的性能稍微好一些。也许这是一个愚蠢的问题，或者我做出了错误的假设 - 能有人解释一下吗？

- dstronczak

---

1. "Vector is discouraged" 可以翻译为“不建议使用 Vector”。
2. "your test should be run in 2 times.. not one after other you don't know what JIT magic do, and use System.nanotime()" 可以翻译为“你的测试应该分成两次运行，而不是连续运行，因为你不知道即时编译器会发生什么神奇的事情，同时使用 System.nanotime()。”

- nachokk

所以，两个评论：（1）使用向量包括由于同步而产生的轻微开销，这可能使其比 ArrayList 更慢。（2）在这里，您实际上正在进行 VM 预热，这使得 ArrayList 的微基准比 Vector 慢一些。尝试交换两个基准测试并查看发生了什么！ - Alexandre Dupriez

不确定你从哪里听到的，可以看看为什么Java中的Vector类被认为是过时的。也许你应该在C++中使用它，而不是在Java中。 - Steve P.

请参见https://dev59.com/WnM_5IYBdhLWcg3waieJ。 - Paul Vargas

你的代码似乎有一个拼写错误，出现在你进行向量遍历时。 - Alex Popov

Answer 1

你编写了一个朴素的微基准测试。在JVM上进行微基准测试非常棘手，甚至很难列举所有的陷阱，但以下是一些经典的陷阱：

1. 必须预热代码；
2. 必须控制垃圾收集暂停；
3. System.currentTimeMillis不精确，但您似乎甚至没有意识到这个方法(your new Date().getTime() 等价，但速度较慢)。

如果想要正确地做这件事，请查看Oracle的jmh工具或Google的Caliper。

我的测试结果

由于我对这些数字感兴趣，以下是jmh的输出结果。首先是测试代码：

public class Benchmark1
{
  static Integer[] ints = new Integer[0];
  static {
    final List<Integer> list = new ArrayList(asList(1,2,3,4,5,6,7,8,9,10));
    for (int i = 0; i < 5; i++) list.addAll(list);
    ints = list.toArray(ints);
  }
  static List<Integer> intList = Arrays.asList(ints);
  static Vector<Integer> vec = new Vector<Integer>(intList);
  static List<Integer> list = new ArrayList<Integer>(intList);

  @GenerateMicroBenchmark
  public Vector<Integer> testVectorAdd() {
    final Vector<Integer> v = new Vector<Integer>();
    for (Integer i : ints) v.add(i);
    return v;
  }
  @GenerateMicroBenchmark
  public long testVectorTraverse() {
    long sum = (long)Math.random()*10;
    for (int i = 0; i < vec.size(); i++) sum += vec.get(i);
    return sum;
  }
  @GenerateMicroBenchmark
  public List<Integer> testArrayListAdd() {
    final List<Integer> l = new ArrayList<Integer>();
    for (Integer i : ints) l.add(i);
    return l;
  }
  @GenerateMicroBenchmark
  public long testArrayListTraverse() {
    long sum = (long)Math.random()*10;
    for (int i = 0; i < list.size(); i++) sum += list.get(i);
    return sum;
  }
}

结果如下：

testArrayListAdd          234.896  ops/msec
testVectorAdd             274.886  ops/msec
testArrayListTraverse    1718.711  ops/msec
testVectorTraverse         34.843  ops/msec

请注意以下内容：

• 在...add方法中，我创建了一个新的本地集合。JIT编译器利用这一事实，并省略Vector方法上的锁定，因此几乎具有相同的性能；
• 在...traverse方法中，我从全局集合中读取；锁定不能被省略，这就是Vector真正表现出性能惩罚的地方。

从这里应该得到的主要结论是：JVM上的性能模型非常复杂，有时甚至是不可预测的。从微基准测试中推断，即使它们被认真地执行，也可能会导致关于生产系统性能的危险错误预测。

- Marko Topolnik

Answer 2

我同意Marko关于使用Caliper的看法，这是一个很棒的框架。

但是如果你更好地组织你的基准测试，你也可以自己完成其中的一部分：

public class ComparePerformance {

    private static final int SIZE = 1000000;
    private static final int RUNS = 500;
    private static final Integer ONE = Integer.valueOf(1);

    static class Run {
        private final List<Integer> list;

        Run(final List<Integer> list) {
            this.list = list;
        }

        public long perform() {
            long oldNanos = System.nanoTime();
            for (int i = 0; i < SIZE; i++) {
                list.add(ONE);
            }

            return System.nanoTime() - oldNanos;
        }
    }

    public static void main(final String[] args) {

        long arrayListTotal = 0L;
        long vectorTotal = 0L;
        for (int i = 0; i < RUNS; i++) {
            if (i % 50 == 49) {
                System.out.println("Run " + (i + 1));
            }

            arrayListTotal += new Run(new ArrayList<Integer>()).perform();
            vectorTotal += new Run(new Vector<Integer>()).perform();
        }

        System.out.println();


        System.out.println("Runs: "+RUNS+", list size: "+SIZE);
        output(arrayListTotal, "List");
        output(vectorTotal, "Vector");
    }

    private static void output(final long value, final String name) {
        System.out.println(name + " total time: " + value + " (" + TimeUnit.NANOSECONDS.toMillis(value) + " " + "ms)");

        long avg = value / RUNS;
        System.out.println(name + " average time: " + avg + " (" + TimeUnit.NANOSECONDS.toMillis(avg) + " " + "ms)");
    }
}

重要的是要经常运行你的代码。同时，删除与基准测试无关的内容。重复使用整数而不是创建新的整数。

上面的基准测试代码在我的机器上生成以下输出：

Runs: 500, list size: 1000000
List total time: 3524708559 (3524 ms)
List average time: 7049417 (7 ms)
Vector total time: 6459070419 (6459 ms)
Vector average time: 12918140 (12 ms)

我认为这应该能让您了解性能差异。

- Sean Patrick Floyd

---

非常好的回答，谢谢！如果我之前没有接受过，我会“接受”你的回答！ - dstronczak

@dstronczak 好的，没问题。当我写这篇文章时，被接受的答案已经改进了，而且本来就是最好的答案。 - Sean Patrick Floyd

Answer 3

如Marko Topolnik所说，编写正确的微基准测试并正确解释结果很困难。有关此主题的好文章可用。

根据我的经验和我所知道的实现，我使用以下经验法则：

- 使用ArrayList - 如果集合必须同步，请考虑使用向量。（我从未使用过它，因为还有其他解决方案可用于同步、并发和并行编程） - 如果集合中有许多元素，并且在列表内部频繁插入或删除操作（不是在末尾），则使用LinkedList。

大多数集合不包含许多元素，花费更多精力对它们进行优化是浪费时间的。在Scala中也有并行集合，可以并行执行某些操作。也许在纯Java中也有类似的东西可用。

尽可能使用List接口来隐藏实现细节，并尝试添加注释以显示您选择特定实现的原因。

- user573215

Answer 4

我进行了测试，当大小为1000000时，ArrayList比Vector更快。

 public static void main(String[] args) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            Vector<Integer> vector = new Vector<Integer>();

            int size= 1000000;
            int listSum = 0;
            int vectorSum = 0;

            long startList = System.nanoTime();
            for (int i = 0; i < size; i++) {
                list.add(Integer.valueOf(1));
            }
            for (Integer integer : list) {
                listSum += integer;
            }
            long endList = System.nanoTime();
            System.out.println("List time: " + (endList - startList)/1000000);
//
//          long startVector = System.nanoTime();
//          for (int i = 0; i < size; i++) {
//              vector.add(Integer.valueOf(1));
//          }
//          for (Integer integer : list) {
//              vectorSum += integer;
//          }
//          long endVector = System.nanoTime();
//          System.out.println("Vector time: " + (endVector - startVector)/1000000);
        }
    }   

输出在不同的时间运行。

Code : list time 83 
       vector time 113

- nachokk