通过Java List进行高效循环

下面的列表来自于2008年的谷歌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! 

前3个是在同一领域的效率,如果可能的话避免7。 这主要是帮助电池寿命的build议,但也可能有助于Java SE的代码。

我的问题是:为什么(7)慢,为什么(3)好? 我认为这可能是(3)和(7)的数组和列表之间的区别。 另外,正如Dan所说(7)创build了一些必须被GCed的小临时对象,现在我对Java有点生疏了,有人能解释一下为什么吗? 在0:41:10他的演讲video中有一分钟。

Solutions Collecting From Web of "通过Java List进行高效循环"

这个清单有点过时了,今天不应该有用。

几年前,Android设备很慢,资源非常有限,这是一个很好的参考。 Dalvik虚拟机的实现也缺less很多可用的优化。

在这样的设备上,一个简单的垃圾收集很容易花费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 >= 0i < limit更快,因为在比较之前,它不会读取variables的值。 它直接与整数文字,这是更快。

我不知道为什么(3)应该比(2)慢。 编译器应该产生与(2)相同的循环,但是目前Dalvik虚拟机可能没有正确地优化它。

 (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是缓慢的,因为它们分配内存,做一些error handling,在内部调用多个方法,…所有这些比在每次迭代中只调用一次函数的(6)慢得多。

我觉得我的第一个回答并不令人满意,真的没有帮助解释这个问题。 我已经发布了这个网站的链接并做了一些阐述,其中包括一些基本的使用案例,但不是问题的实质。 所以,我继续做了一些小小的实践研究。

我跑了两个单独的代码:

  // 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 ,都使用Integer数组(无int )。

接下来,我使用javap来反汇编这些并查看字节码。 (我忽略了初始化; for循环之前的所有东西都被注释掉了。)由于这些都是相当长的,所以我把它们贴在了PasteBin 这里 。

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

现在,在代码2中,字节码变得更encryption集。 除了上面需要的每个其他调用之外,它还必须进行两次invokeinterface调用(都是Iterator )。 另外,代码2必须调用checkcast因为它是一个通用的Iterator (没有被优化,如上所述)。 现在,尽pipeloadstore操作的呼叫较less,但这些上述调用涉及大量的开销。

正如他在video中所说,如果你发现自己需要做很多这些,你可能会遇到问题。 例如,在一个Activity开始时运行一个可能不是太大的事情。 只要小心创build其中的很多,特别是在onDraw迭代,例如。

我想编译器优化(3)到这(这是我猜测的部分):

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

(7)不能优化,因为编译器不知道它是什么样的Iterable。 这意味着它真的需要在堆上创build一个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 } 

我猜你必须将这些对象编组到一个基于Iterator的“链表”中,然后支持一个API,而不是一块内存和一个指针(数组)

第三个变体比7更快,因为数组是指定types,JVM应该只指定一个指向正确值的指针。 但是当你遍历一个集合时,编译器可以执行额外的转换,因为擦除。 实际上编译器插入这个转换为通用的代码,以确定一些肮脏的黑客,如尽可能使用不赞成的原始types。

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

以Android为例,这是2015年Google Developers的video。

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

他们在DALVIK运行时做了testing,4.4.4构build了10次,得到了平均结果。 结果显示“For index”是最好的。

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