Java for循环性能问题

Question

考虑以下示例：

public static void main(final String[] args) {
    final List<String> myList = Arrays.asList("A", "B", "C", "D");
    final long start = System.currentTimeMillis();
    for (int i = 1000000; i > myList.size(); i--) {
        System.out.println("Hello");
    }
    final long stop = System.currentTimeMillis();
    System.out.println("Finish: " + (stop - start));
}

与

public static void main(final String[] args) {
    final List<String> myList = Arrays.asList("A", "B", "C", "D");
    final long start = System.currentTimeMillis();
    final int size = myList.size();
    for (int i = 1000000; i > size; i--) {
        System.out.println("Hello");
    }
    final long stop = System.currentTimeMillis();
    System.out.println("Finish: " + (stop - start));
}

这样做会有什么区别吗？在我的机器上第二个似乎执行得更快，但我不知道它是否真的准确。编译器会优化这段代码吗？如果循环条件是一个不可变对象（例如字符串数组），我可以想象他会这样做。

- kukudas

---

如果你想要测量经过的时间（并且希望它准确），你应该使用System.nanoTime()。顺便说一句。 - Pascal Thivent

会记住这个好点。 - kukudas

Answer 1

如果你想测试类似这样的东西，你真的必须优化你的微基准测试来测量你关心的内容。

首先，使循环廉价却不可能跳过。通常计算总和就能做到这一点。

其次，比较这两个时间。

以下是执行上述操作的代码：

import java.util.*;

public class Test {

public static long run1() {
  final List<String> myList = Arrays.asList("A", "B", "C", "D");
  final long start = System.nanoTime();
  int sum = 0;
  for (int i = 1000000000; i > myList.size(); i--) sum += i;
  final long stop = System.nanoTime();
  System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum);
  return stop-start;
}

public static long run2() {
  final List<String> myList = Arrays.asList("A", "B", "C", "D");
  final long start = System.nanoTime();
  int sum = 0;
  int limit = myList.size();
  for (int i = 1000000000; i > limit; i--) sum += i;
  final long stop = System.nanoTime();
  System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum);
  return stop-start;
}

public static void main(String[] args) {
  for (int i=0 ; i<5 ; i++) {
    long t1 = run1();
    long t2 = run2();
    System.out.println("  Speedup = " + (t1-t2)*1e-9 + " ns/op\n");
  }
}

}

如果我们运行它，在我的系统上会得到：

Finish: 0.481741256 ns/op; sum = -243309322
Finish: 0.40228402 ns/op; sum = -243309322
  Speedup = 0.079457236 ns/op

Finish: 0.450627151 ns/op; sum = -243309322
Finish: 0.43534661700000005 ns/op; sum = -243309322
  Speedup = 0.015280534 ns/op

Finish: 0.47738474700000005 ns/op; sum = -243309322
Finish: 0.403698331 ns/op; sum = -243309322
  Speedup = 0.073686416 ns/op

Finish: 0.47729349600000004 ns/op; sum = -243309322
Finish: 0.405540508 ns/op; sum = -243309322
  Speedup = 0.071752988 ns/op

Finish: 0.478979617 ns/op; sum = -243309322
Finish: 0.36067492700000003 ns/op; sum = -243309322
  Speedup = 0.11830469 ns/op

这意味着方法调用的开销约为0.1纳秒。如果您的循环执行的操作不超过1-2纳秒，那么您应该关注这一点。否则就不用管它。

- Rex Kerr

Answer 2

就我个人而言，我认为你不能从这样一个人为制造的例子中得出任何有意义的结论。

但如果你真的想知道，为什么不使用javap反编译代码并查看有什么不同呢？为什么要猜测编译器在做什么，当你可以亲眼看到而无需在这里询问呢？

第一种情况的字节码：

public class Stackoverflow extends java.lang.Object{
public Stackoverflow();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_4
   1:   anewarray       #2; //class java/lang/String
   4:   dup
   5:   iconst_0
   6:   ldc     #3; //String A
   8:   aastore
   9:   dup
   10:  iconst_1
   11:  ldc     #4; //String B
   13:  aastore
   14:  dup
   15:  iconst_2
   16:  ldc     #5; //String C
   18:  aastore
   19:  dup
   20:  iconst_3
   21:  ldc     #6; //String D
   23:  aastore
   24:  invokestatic    #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List
   27:  astore_1
   28:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   31:  lstore_2
   32:  ldc     #9; //int 1000000
   34:  istore  4
   36:  iload   4
   38:  aload_1
   39:  invokeinterface #10,  1; //InterfaceMethod java/util/List.size:()I
   44:  if_icmple       61
   47:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   50:  ldc     #12; //String Hello
   52:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   55:  iinc    4, -1
   58:  goto    36
   61:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   64:  lstore  4
   66:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   69:  new     #14; //class java/lang/StringBuilder
   72:  dup
   73:  invokespecial   #15; //Method java/lang/StringBuilder."<init>":()V
   76:  ldc     #16; //String Finish:
   78:  invokevirtual   #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/la
   81:  lload   4
   83:  lload_2
   84:  lsub
   85:  invokevirtual   #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
   88:  invokevirtual   #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   91:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   94:  return
}

第二种情况的字节码：

public class Stackoverflow extends java.lang.Object{
public Stackoverflow();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_4
   1:   anewarray       #2; //class java/lang/String
   4:   dup
   5:   iconst_0
   6:   ldc     #3; //String A
   8:   aastore
   9:   dup
   10:  iconst_1
   11:  ldc     #4; //String B
   13:  aastore
   14:  dup
   15:  iconst_2
   16:  ldc     #5; //String C
   18:  aastore
   19:  dup
   20:  iconst_3
   21:  ldc     #6; //String D
   23:  aastore
   24:  invokestatic    #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List;
   27:  astore_1
   28:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   31:  lstore_2
   32:  aload_1
   33:  invokeinterface #9,  1; //InterfaceMethod java/util/List.size:()I
   38:  istore  4
   40:  ldc     #10; //int 1000000
   42:  istore  5
   44:  iload   5
   46:  iload   4
   48:  if_icmple       65
   51:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   54:  ldc     #12; //String Hello
   56:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   59:  iinc    5, -1
   62:  goto    44
   65:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   68:  lstore  5
   70:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   73:  new     #14; //class java/lang/StringBuilder
   76:  dup
   77:  invokespecial   #15; //Method java/lang/StringBuilder."<init>":()V
   80:  ldc     #16; //String Finish:
   82:  invokevirtual   #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   85:  lload   5
   87:  lload_2
   88:  lsub
   89:  invokevirtual   #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
   92:  invokevirtual   #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   95:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   98:  return
}

虽然有一些区别，但我不能确定它们对性能的影响。

我会编写第二个选项，因为这意味着（表面上）每个循环迭代只需一个方法调用，而不是每次都需要。我不知道编译器是否可以将其优化掉，但我肯定可以很容易地实现它。所以，无论它对墙时有什么影响，我都会这样做。

- duffymo

Answer 3

我曾在一个项目上工作，我的第一项任务是找出一些极其缓慢的代码（这是在一台全新的 486 电脑上执行的，需要大约 20 分钟才能完成）:

for(size_t i = 0; i < strlen(data); i++)
{
    // do something with data[i]
}

解决方案是（将其简化到两分钟或更短的时间）：

size_t length = strlen(data);

for(int i = 0; i < length; i++)
{
    // do something with data[i]
}

问题在于“data”的长度超过了1百万个字符，而strlen需要一直计算每个字符的数量。

对于Java来说，“size()”方法可能返回一个变量，因此VM会将其内联。在像Android上的VM上可能不会这样做，所以答案是“取决于情况”。

我个人的偏好是如果一个方法应该每次返回相同的结果，就永远不要调用它超过一次。这样，如果方法确实涉及计算，则只执行一次计算，然后就不再是问题了。

- TofuBeer

---

好的观点，但我要指出strlen的情况有些不同，因为它实际上必须遍历数据以找出其长度。 因此，在线性化不能节省时间。在这种情况下，您绝对需要保存结果。 但是，正如您所说，如果您始终保存该值，则可以保证优化。 - Jonathan M Davis

错误，这是Java，并且字符串长度被缓存在对象中。 - Dean Povey

我知道这是Java...在我展示代码的时候，Java还没有公开。故事的重点是，如果一个方法（或函数）每次都应该返回相同的值，那么反复调用它就没有意义...实际上可能是“有害的”，因为每次调用它都可能涉及昂贵的计算。在这种情况下（正如我在帖子中所说！），很可能只是一个变量返回（事实上，我无法想象不是这种情况的情况），但即使在一些VMs（例如Andoid使用的VM）中，调用也可能不会被内联。 - TofuBeer

Answer 4

请注意，javac编译器与优化几乎没有任何关系，真正重要的编译器是嵌入在JVM中的JIT编译器。

在您的示例中，在最常见情况下，myList.size()是一个简单的方法派发，它返回实例中的一个字段的内容。与System.out.println("Hello")所涉及的工作相比这可以忽略不计（至少需要一个系统调用，因此需要数百个时钟周期，而方法派发最多只需十多个时钟周期）。我非常怀疑你的代码能够显示出有意义的速度差异。

从更普遍的角度来看，JIT编译器应该将此对size() 的调用识别为对已知实例的调用，以便它可以使用直接函数调用（更快），甚至内联size()方法调用，将调用缩小为简单的实例字段访问。

- Thomas Pornin

---

大家都认同 System.out.println() 调用是最耗费资源的。我想知道如果你使用 StringBuilder 将这些 Hello 字符串连接起来，然后在循环外使用单个 System.out.println() 调用打印它们，会有什么不同。 - Tomas Andrle

@Thomas Pornin：然而，javac编译器确实会进行一些优化，例如当cond是一个被设置为false的final布尔值时，会删除if (cond) {...}调用。因此，说javac与优化毫无关系也不完全正确。 - cocotwo

@cocotwo：删除if (false) {...}是Java规范的一部分（在已生成的.class文件中，已删除括号内的代码不得产生对其他类的符号引用），因此我不确定它是否可以称为“优化”：这不是编译器可以随意执行或不执行的事情。 - Thomas Pornin

Answer 5

它无法进行优化，因为在循环执行期间mylist.size()可能会发生变化。即使它是final的，这只意味着引用是final的（意味着您不能将myList重新分配给其他对象），但myList上的方法，例如remove()和add()仍然可用。Final并不使对象不可变。

- sidereal

---

好观点！但这取决于情况。提供的示例，就像duffymo回答的那样，太模糊了。 - Pindatjuh

Answer 6

Java编译器本应进行优化，但由于条件判断语句出现了错误，它并没有这样做。如果您将代码编写为以下形式，将不会出现任何问题。

for (int i = myList.size(); i < 1000000; i--) {
    System.out.println("Hello");
}

- fastcodejava

---

你应该写 i >= 0 和 i--，我猜。 - Pindatjuh

我猜你想要倒数到0。 - Carl Manaster

Answer 7

第二个应该更快，因为不需要在每次执行循环时调用 .size()。只需一次计算1+2=3比多次计算要快得多。

- Jonathan Czitkovics

---

@TofuBeer 这怎么可能呢？编译器怎么知道列表的大小是否会改变？你能提供一个参考吗？ - Christopher Oezbek

看看代码，它不能被更改。此外，内联并不意味着这个，它意味着用直接变量访问替换方法调用。 - TofuBeer

即使列表是最终的，其大小仍然可以更改。 - kukudas

Answer 8

第二种实现更快是有道理的，因为您存储了一个单一、最终的本地变量副本。编译器必须弄清楚循环内部大小不会改变，以使性能大致相等。

一个问题是 - 这种微观优化真的很重要吗？如果是这样，请选择在测试中运行更快且不依赖于编译器优化的选项。

- wsorenson

Answer 9

几乎可以确定你在这里看到的是HotSpot内联的差异。对于一个更简单的循环，它更有可能进行内联，从而消除所有冗余的垃圾。它可能会进行相同的内联，但是会更早地或者更轻松地完成。通常，在Java微基准测试中，您应该多次运行代码，从中可以计算出启动时间、平均时间和偏差。

- Tom Hawtin - tackline

Answer 10

在编译器优化的情况下，最好使用for-each循环：

for(final String x : myList) { ... }

这使编译器能够提供最快的实现。

编辑：

您的代码示例之间的区别在于for循环的第二个参数。在第一个示例中，VM将执行方法调用（更昂贵），因此速度较慢（仅在有大量迭代时才显着）。在您的第二个示例中，VM将执行堆栈弹出（较不昂贵，并且本地变量位于堆栈上），因此速度更快（仅在有大量迭代时才显着：对于仅进行一次迭代的情况，第一个示例在内存使用方面更快）。

另外：“过早优化是万恶之源。”唐纳德·克努斯（Donald Knuth）的臭名昭著的定律。

- Pindatjuh

---

在这种情况下，他并没有迭代数组。 - Pool

这并不相关，因为 OP 实际上没有在集合或数组上进行迭代。 - cletus

但我猜这就是问题的意图；否则为什么发问者使用Array.asList呢？另一方面，for-each语法也可以用于数组。 - Pindatjuh

Pindatjuh发布的代码在这个例子中可以工作，因为我们使用数组的大小作为循环次数。 - Brendan Long

+1 for "过早优化是万恶之源"。首先要使代码易于阅读，然后进行测量；只有在测量表明它太慢时才进行优化。这在大多数程序员的经验中几乎从不发生。 - Carl Manaster