在 Java 中分配迭代器的 return 值对高性能有影响吗？

Question

我有一个 Iterable<T> 的实现（四叉树结构的一种变体），我计划将其用于对大数据集的性能至关重要的环境中，因此我一直在进行一些测试，有几百万个随机条目，运行他们重复。我对以下代码段感到奇怪：

 long start = System.currentTimeMillis();
 for (int i = 0; i < 100; i++) {
     Iterator<A> iter = it.iterator();
     while (iter.hasNext()) {
         iter.next();
     }
 }
 long end = System.currentTimeMillis();
 System.out.println("Total time: " + (end - start));

我得到的时间总是在 4000 到 5000 毫秒之间。但是，当我将 while 循环更改为：

A a = null;
while (iter.hasNext()) {
    a = iter.next();
}

时间会跳起来——不仅仅是轻微的跳，而是一直跳到 15 到 16 秒，并且完全一致。现在这似乎已经不依赖于 next() 的实现，但经过进一步调查，我发现它甚至发生在一个简单的 ArrayList 上，所以我将 post 编译代码相反：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Test {
    static class A {}

    public static void main(String[] args) {
        List<A> list = new ArrayList<>();
        // Add a lot of entries
        for (int i = 0; i < 10000000; i++) {
            list.add(new A());
        }
        // Test it
        A a = null;
        Iterator<A> iter = null;
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            iter = list.iterator();
            while (iter.hasNext()) {
                iter.next();
                // Or:
                // a = iter.next();
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("Total time: " + (end - start));
    }
}

结果：令人难以置信的 30 倍差异。而且它每次都确定性地发生。

这可能是什么原因？我看不出对一个已经分配的变量的单一赋值除了可以忽略不计之外还有什么，特别是考虑到 iter.next() 内部发生了这么多其他事情。我唯一的猜测是 System.currentTimeMillis() 调用不知何故没有在正确的时间执行，但至于它如何受到变化的影响，我不知道。

但即使这样也不太合适，因为它花费的时间明显长得多，尤其是如果我进一步增加 for 循环运行的次数。据我所知，垃圾收集器也不应该再做任何事情，因为不应该发生浪费的临时分配。显然是对 return 值的赋值，这很关键，因为除了 iter.next() 之外，还要做其他事情，比如增加 int 变量每次，对执行时间没有相同的不利影响。

编辑：我的 post 中的特定基准存在许多问题，这些问题可能会损害其结果的可信度，多人引起了我的注意。不过，为了 posterity，我会把它留在这里，或者稍后可能会更新它以使其更好。话虽如此，该现象最可能的原因已在接受的答案中确定，并且我确认消除类型转换解决了问题，因此尽管基准存在缺陷，但上述观察结果似乎不仅仅是这些的副作用。

Answer 1

我认为您看到的很多差异都归结于您进行基准测试的方式。我没有看到您尝试处理 JVM 预热效果或隔离 GC 和内存分配效果的迹象。甚至内存缓存大小的影响。

但我想我知道无论如何都会发生什么。

两者的区别

  while (iter.hasNext()) {
      iter.next();
  }

和

  A a = null;
  while (iter.hasNext()) {
      a = iter.next();
  }

是（显然！）作业。但是这个赋值还有一个隐藏的类型转换来检查 next() 返回的值是否真的是一个 A。（提示：泛型擦除...）

但是类型转换怎么会花那么多时间呢？

嗯，我的理论是，这是类型转换本身的成本和内存缓存/局部效应的组合。

在第一个例子中，迭代是从一个大数组中顺序读取引用。这是一个相对缓存友好的事情......因为数组将是内存中的单个连续块，并且硬件很容易在单个操作中将多个字提取到缓存中。（事实上，JIT 可能甚至发出缓存预取指令......以避免管道停顿。（这是一个猜测......））

在第二个例子中，在读取每个引用之间，CPU 也将进行类型转换。类型转换涉及从每个 A 实例的 header 中检索一个 class 标识符，然后测试它是否正确。

从 object header 中检索标识符是每次从内存的不同部分获取内存。 objects 可能在内存中开始时是连续的，但即便如此，间距也可能会分开多个单词。缓存的效率将大大降低。甚至数组和 object 都通过同一个缓存这一事实也很重要。
测试class标识符可能是non-trivial。如果 A 是 class 不是接口并且它没有 subclasses，那么运行时应该能够做等同于 == 测试。否则，测试会更复杂，更昂贵。

第二种可能的解释与代码内联有关。如果 Iterator::next() 调用足够小可以内联，那么 JIT 编译器的 peep-hole 优化器可能能够推断出部分或全部 next 代码在 assignment-less 版本的代码。但是，我怀疑它是否可以推断 next() 由于并发修改检查而完全多余。消除这些检查会改变边缘情况下的代码行为，并且将是无效的优化。

简而言之，不难看出添加赋值和关联的隐藏类型会对性能产生重大影响，尤其是在大型数据结构上。

在 Java 中分配迭代器的 return 值对高性能有影响吗？

High performance impact of assigning an iterator's return value in Java?

java

performance

variable-assignment