16

以下列表来自 2008 年名为“Dalvik Virtual Machine Internals”的谷歌 I/O 演讲,它列出了按效率从高到低依次循环一组对象的方法:

(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!

前 3 个在同一效率范围内,如果可能,请避免 7 个。这主要是帮助延长电池寿命的建议,但也可能有助于 Java SE 代码。

我的问题是:为什么(7)很慢,为什么(3)很好?我认为这可能是(3)和(7)的数组和列表之间的区别。此外,正如 Dan 提到的 (7) 创建了大量必须进行 GC 处理的小型临时对象,我现在对 Java 有点生疏了,有人可以解释为什么吗?这是他在 0:41:10 的谈话视频中的一分钟。

4

6 回答 6

7

这个列表有点过时了,今天不应该真的有用。

几年前这是一个很好的参考,当时 Android 设备运行缓慢且资源非常有限。Dalvik VM 实现也缺乏当今可用的许多优化。

在这样的设备上,一个简单的垃圾收集很容易花费1 或 2 秒(相比之下,今天大多数设备大约需要 20 毫秒)。在 GC 期间,设备刚刚冻结,因此开发人员必须非常小心内存消耗。

今天你不必太担心,但如果你真的关心性能,这里有一些细节:

(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) 慢得多,后者在每次迭代中只调用一个函数。

于 2012-08-02T21:26:20.143 回答
4

我觉得我的第一个答案并不令人满意,真的无助于解释这个问题;我已经发布了该站点的链接并进行了详细说明,其中涵盖了一些基本用例,但没有涉及问题的本质。因此,我继续进行了一些动手研究。

我运行了两个单独的代码:

    // 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);

当然,两者都 print out 15,并且都使用Integer数组(没有ints)。

接下来,我曾经javap将这些反汇编并查看字节码。(我忽略了初始化;for循环之前的所有内容都被注释掉了。)由于这些内容很长,我将它们发布在 PasteBin此处

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

现在,在代码 2 中,字节码变得更加密集。除了上面需要的所有其他调用之外,它还必须进行 2 次invokeinterface调用(都到)。Iterator此外,代码 2 必须调用checkcast,因为它是通用的Iterator(如我上面提到的,它没有经过优化)。现在,尽管对loadstore操作的调用减少了,但上述这些调用涉及大量更多的开销。

正如他在视频中所说,如果你发现自己需要做很多这些,你可能会遇到问题。例如,在 . 开头运行一个Activity可能没什么大不了的。请注意创建其中的许多,onDraw例如,尤其是在 中进行迭代。

于 2012-08-02T21:01:27.350 回答
1

我猜编译器对此进行了优化(3)(这是我猜测的部分):

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

}

并且 (7) 无法优化,因为编译器不知道它是哪种 Iterable。这意味着它确实必须new Iterator在堆上创建一个。分配内存是昂贵的。每次你请求下一个对象时,它都会通过一些调用。

粗略描述编译 (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


}
于 2012-08-02T20:21:17.893 回答
0

第三种变体比 7 更快,因为数组是具体类型,JVM 应该只分配一个指向正确值的指针。但是当你迭代一个集合时,编译器可以因为擦除而执行额外的强制转换。实际上,编译器将此强制转换插入到通用代码中以确定一些肮脏的技巧,例如尽快使用已弃用的原始类型。

PS这只是一个猜测。事实上,我认为编译器和 JIT 编译器可以执行任何优化(即使在运行时也是 JIT),结果可能取决于特定的细节,如 JVM 版本和供应商。

于 2012-08-02T20:21:09.813 回答
0

我想您必须将对象编组为基于“链表”的迭代器,然后支持 API,而不是一大块内存和指针(数组)

于 2012-08-02T20:17:54.660 回答
0

对于 Android,这是 2015 年 Google Developers 的视频。

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

他们在 DALVIK 运行时(4.4.4 版本)上进行了 10 次测试,以获得平均结果。结果显示“For index”是最好的。

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

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

于 2016-04-07T01:15:45.590 回答