为什么插入空 ArrayList 比插入非空 ArrayList 需要更多时间？

Question

我运行我的探查器程序进行了 1000 次迭代，以计算插入 Empty ArrayList 所花费的平均时间和插入 Non-Empty ArrayList 所花费的平均时间。我运行我的 ArrayList<Item> 分析器程序，其中 Item class 是

class Item{
  int id;
  String name;
}

分析器程序类似于

main(){
  final int iterations = 1000;

  /**** Empty List Insert ****/
  int id = 0;
  long[] timerecords = new long[iterations];
  ArrayList<Item> list = new ArrayList<>();
  for (int i = 0; i < iterations; i++) {
      long stime = System.nanoTime(); //Start Time
      list.add(new Item(id, "A"));
      long elapsedTime = System.nanoTime() - stime; //Elapsed time
      timerecords[i] = elapsedTime; //Record Elapsed time

      //reset
      list.clear();
  }
  System.out.println("Empty List Insert Takes = " + getAverageTime(timerecords) + " nanoseconds");

  /**** Non-Empty List Insert ****/
  list = new ArrayList<>();
  timerecords = new long[iterations];
  //Insert some Items
  list.add(new Item(id++, "B")); list.add(new Item(id++, "R"));
  list.add(new Item(id++, "H")); list.add(new Item(id++, "C")); 

  for (int i = 0; i < iterations; i++) {    
        Item item = new Item(id, "A");
        long stime = System.nanoTime(); //Start Time
        list.add(item);
        long elapsedTime = System.nanoTime() - stime; //Elapsed time
        timerecords[i] = elapsedTime; //Record Elapsed time

        //reset
        list.remove(item);
  }
  System.out.println("Non-Empty List Insert Takes = " + getAverageTime(timerecords) + " nanoseconds");
}

其中 getAverageTime(long [] timerecords) 方法 returns 平均时间翻倍。运行多次执行此程序后，我观察到插入空 ArrayList 比插入非空 ArrayList 花费更多时间。一个这样的运行输出是

Empty List Insert Takes = 1027.781 nanoseconds
Non-Empty List Insert Takes = 578.825 nanoseconds

这背后的原因是什么？

Answer 1

如果您查看 ArrayList 的实现 - 一个空的 ArrayList 以一个空数组开头来存储数据 - 这很容易。

但是当你第一次调用add()方法时，这个数组需要被复制——因此需要分配内存。 ensureCapacity() 和 grow() 方法尽量减少 Arrays.copyOf() 的创建，但只要内部 Array 大小仍然很小，越来越多的时候必须增加这个数组，这可能导致持续时间增加。

这是 1.7 中的 ArrayList.grow(int)：

  private void grow(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity - minCapacity < 0) {
      newCapacity = minCapacity;
    }

    if(newCapacity - 2147483639 > 0) {
      newCapacity = hugeCapacity(minCapacity);
    }

    this.elementData = Arrays.copyOf(this.elementData, newCapacity);
  }

您没有测量创建非空 ArrayLIst 所花费的时间，是吗？

Answer 2

不同之处在于实例创建 (new Item())。

  long stime = System.nanoTime(); //Start Time
  list.add(new Item(id, "A")); // at this point two things are happening
  // creation of instance & addition into ArrayList
  // both takes their own time.

  long elapsedTime = System.nanoTime() - stime; //Elapsed time

你创建stime变量的地方就是定时器开始的地方。您肯定会向列表中添加新项目。但在第一种情况下，在你做 System.nanoTime(); 之前您在添加时（在分配 stime 变量之后）在 Item 上调用 new 运算符，这会花费额外的时间。在第二种情况下，您在执行 System.nanoTime(); 之前执行此操作；

    Item item = new Item(id, "A");
    long stime = System.nanoTime(); //Start Time
    list.add(item);
    long elapsedTime = System.nanoTime() - stime; //Elapsed time

因此，仅捕获项目对象添加到 ArrayList 时间。

Answer 3

我很感兴趣，所以我对它进行了一些调试。效果来自两个不同的来源：

正如@Alexander 已经指出的那样，不断增加 Arraylist 大小的容量会影响您的测试。要 "fix" 这个，你可以创建你的 ArrayLists 有足够的准备，比如：

ArrayList<Item> list = new ArrayList<>(iterations * 2);

即使在执行此操作后，您也可以观察到第一个和第二个测试用例之间的性能差异为 100-300%。其原因与 Java 内部机制有关，即 ClassLoading 和 JIT。通过在第一次测试之前进行热身，如下所示：

    int rounds = 10000;
    long[] t = new long[rounds];
    ArrayList<Item> warmUpList = new ArrayList<>(rounds);
    for (int i = 0; i < rounds; i++) {
        warmUpList.add(new Item(0, "A"));
        long stime = System.nanoTime(); // Start Time
        long elapsedTime = System.nanoTime() - stime; // Elapsed time
        t[i] = elapsedTime; // Record Elapsed time
    }

您可以使用优化器。通过将 "round" 变量的值从 100 增加到 10.000，您可以看到您自己的测试如何变得越来越好，而不是稳定在同等速度。

Answer 4

使用 System.nanoTime() 测量每个单独的插入可能会导致不可靠的值。最好对 System.currentTimeMillis() 做同样的事情并测量整个循环。

此外，ArrayList 中的插入时间可能会影响执行内部数组增长的次数。因此，插入一个带有小内部数组的空 ArrayList 会导致很多增长。插入具有部分空的大内部数组的非空 ArrayList 可能不会导致增长，但如果发生增长，它会比空数组慢，因为您必须复制更大的数组。

为什么插入空 ArrayList 比插入非空 ArrayList 需要更多时间？

Why insertion into empty ArrayList takes more time than insertion into non-empty ArrayList?

java

arraylist

nanotime