高效遍历Java List

Question

以下列表来自于2008年Google I/O大会上的"Dalvik虚拟机内部"演讲，它列出了按照效率从高到低循环遍历一组对象的方式:

(1) for (int i = initializer; i >=0; i--) //hard to loop backwards
(2) int limit = calculate_limit(); for (int i= 0; i< limit; i++)
(3) Type[] array = get_array(); for (Type obj : array)
(4) for (int i =0; i< array.length; i++) //gets array.length everytime
(5) for (int i=0; i < this.var; i++) //has to calculate what this.var is
(6) for (int i=0; i < obj.size(); i++) //even worse calls function  each time
(7) Iterable list = get_list(); for (Type obj : list) //generic object based iterators slow!

前三个都在效率方面处于同一领域，如果可能的话，请避免第七个。这主要是为了帮助电池寿命，但也可能有助于Java SE代码。

我的问题是：为什么(7)很慢，而(3)很好？我认为这可能是(3)和(7)之间的数组和列表的区别。此外，正如Dan提到的那样，(7)创建了大量需要进行垃圾回收的小临时对象，我对Java现在有点生疏，有人能解释一下为什么吗？在他的talk video中的0:41:10处有一分钟的解释。

- user1147800

---

请注意，这仅适用于ArrayList（如果有任何List）。根据索引迭代LinkedList非常昂贵。 （7）仅会创建单个临时对象，并且我真的怀疑差异可以测量。在大多数程序中，时间都花费在对列表中每个对象执行某些操作上，而不是迭代机制本身。 - Mathias Schwarz

Answer 1

这个列表已经有点过时了，对于今天来说可能没有太大用处。

在几年前，安卓设备速度缓慢且资源非常有限，此时这个列表是一个很好的参考。Dalvik虚拟机的实现也缺乏很多现在可用的优化。

在这样的设备上，一个简单的垃圾回收需要花费1或2秒的时间（相比之下，现在大多数设备只需花费约20毫秒）。在进行垃圾回收时，设备会停滞不前，因此开发人员必须非常关注内存消耗。

虽然现在你不必太担心这个问题，但如果你真的关心性能，以下是一些细节：

(1) for (int i = initializer; i >= 0; i--) //hard to loop backwards
(2) int limit = calculate_limit(); for (int i=0; i < limit; i++)
(3) Type[] array = get_array(); for (Type obj : array)

这些内容很容易理解。 i >= 0 比 i < limit 更快评估，因为它在进行比较之前不会读取变量的值。它直接使用整数字面量，因此更快。

我不知道为什么（3）应该比（2）慢。编译器应该生成与（2）相同的循环，但也许 Dalvik VM 在此时没有正确地优化它。

(4) for (int i=0; i < array.length; i++) //gets array.length everytime
(5) for (int i=0; i < this.var; i++) //has to calculate what this.var is
(6) for (int i=0; i < obj.size(); i++) //even worse calls function  each time

这些已经在注释中解释过了。

(7) Iterable list = get_list(); for (Type obj : list)

Iterables很慢，因为它们需要分配内存、进行一些错误处理、在内部调用多个方法等等。所有这些都比(6)慢得多，因为(6)每次迭代只调用一个函数。

- Dalmas

---

非常感谢您的回答，能否再详细解释一下为什么“迭代器分配内存”？谢谢。 - user1147800

我只知道这是一种设计选择，旨在减少Iterator.remove()的内部复杂性（也许加快速度）。 - Dalmas

正在阅读这个 [java-temporary-iterators-are-slowing-my-android-game] (https://dev59.com/Zmgu5IYBdhLWcg3wOUgk)。 - user1147800

Answer 2

我感觉我的第一个答案并不令人满意，没有很好地解释问题；我已经发布了this site的链接并稍作阐述，涵盖了一些基本用例，但没有涉及问题的细节。所以，我开始进行了一些实际研究。

我运行了两个分开的代码：

    // Code 1
    int i = 0;
    Integer[] array = { 1, 2, 3, 4, 5 };
    for (Integer obj : array) {
        i += obj;
    }
    System.out.println(i);

    // Code 2
    int i = 0;
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (Integer obj : list) {
        i += obj;
    }
    System.out.println(i);

当然，两者都打印出“15”，并且都使用了一个整数数组（没有int）。

接下来，我使用javap对它们进行反汇编并查看字节码。（我忽略了初始化；在for循环之前的所有内容都被注释掉了。）由于这些代码非常冗长，所以我把它们发布到了PasteBin here。

现在，虽然代码1的字节码实际上更长，但它更少的运算强度。它只使用一次invokevirtual（除了println），不需要其他调用。在代码1中，它似乎将迭代优化为基本循环；检查数组长度并加载到我们的变量中，然后加到i中。这似乎被优化为完全像for (int i = 0; i < array.length; i++) { ... }一样的行为。

现在，在代码2中，字节码变得更加密集。除了每个必要的调用之外，它还必须进行2个invokeinterface调用（都是针对Iterator）。此外，代码2必须调用checkcast, 因为它是一个通用的Iterator（正如我上面提到的那样，这是不被优化的）。现在，尽管对load和store操作的调用较少，但是上述调用涉及的开销要多得多。

正如他在视频中所说的，如果你发现自己需要做很多这样的事情，你可能会遇到问题。例如，在Activity的开头运行一个，可能不是太大的问题。只需注意不要创建太多这样的对象，特别是在onDraw中进行迭代。

- Cat

Answer 3

我猜编译器将(3)优化为以下内容（这是我猜测的部分）：

for (int i =0; i < array.length; ++i)
{
    Type obj = array[i];

}

而且（7）无法进行优化，因为编译器不知道它是什么类型的Iterable。这意味着它必须在堆上创建一个新的迭代器。分配内存是昂贵的。每次请求下一个对象时，都会经过一些调用。

简单概述一下编译（7）时发生的情况：

Iterable<Type> iterable = get_iterable();
Iterator<Type> it = iterable.iterator(); // new object on the heap
while (it.hasNext()) // method call, some pushing and popping to the stack
{
    Type obj = it.next(); // method call, again pushing and popping


}

- Martijn Courteaux

---

JVM是一种堆栈机，那么为什么内存分配如此昂贵？JVM只需向前移动堆栈指针即可。 - gkuzmin

JVM 也有堆...你使用的每个 new 都是在堆上创建的。想一想：所有的 new 都在栈上创建是不可能的。 - Martijn Courteaux

Dalvik是基于寄存器而不是基于堆栈的。 - user1147800

所以它没有堆栈，但它有一个堆。 - user1147800

Iterator<Type> it = iterable.iterator(); 为什么这个会放在堆上？如果是的话，如果我理解正确，它只会分配一次迭代器对象（而不是每个项目都分配一次）？ - user1147800

但是据我所知，JVM堆非常接近于栈。当堆中没有足够的空间来放置一个对象时，JVM不会分析RAM以寻找足够的空间来进行对象分配。JVM只会执行GC。然后GC收集取消引用的对象并将每个幸存者移动到内存段的开头。这是一个简化的模型，但它表明Java堆看起来很像栈（除了GC过程）。因此，分配过程应该非常快速。 - gkuzmin

Answer 4

对于Android来说，这是2015年Google开发者的视频。

索引还是迭代？（Android性能模式第2季第6集） https://www.youtube.com/watch?v=MZOf3pOAM6A

他们在DALVIK运行时环境下进行了10次测试，使用4.4.4版本的构建，并得到了平均结果。 结果显示，“使用索引”是最好的选择。

int size = list.size();
for (int index = 0; index < size; index++) {
    Object object = list.get(index);
    ...
}

他们还建议在视频结束时自己在您的平台上进行类似的测试。

- Jack Fan

Answer 5

我猜你需要将对象编组成基于迭代器的“链表”，然后支持一个API，而不是一个内存块和指针（数组）。

- srini.venigalla

Answer 6

第三个变量比7更快，因为数组是具体化类型，JVM只需将指针分配给正确的值。但是，当您遍历集合时，编译器可能会执行额外的强制转换，因为擦除。实际上，编译器将这些强制转换插入到通用代码中，以尽快确定某些肮脏的黑客，例如使用已弃用的原始类型。

P.S. 这只是一个猜测。实际上，我认为编译器和JIT编译器可以执行任何优化（JIT甚至在运行时），结果可能取决于特定的细节，如JVM版本和供应商。

- gkuzmin