嵌套循环的效率

Question

请参阅以下代码片段：

    Long first_begin = System.currentTimeMillis();

    // first nested loops
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 1000000; j++) {
            // do some stuff
        }
    }
    System.out.println(System.currentTimeMillis() - first_begin);
    // second nested loops
    Long seconde_begin = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 10; j++) {
            // do some stuff
        }
    }
    System.out.println(System.currentTimeMillis() - seconde_begin);

我想知道为什么第一个嵌套循环比第二个嵌套循环运行得慢？

问候！

重要提示！：很抱歉，在第一次提出这个问题时，我不小心将变量 j 设置为以 1 开头，我已进行更正。

更新：循环中没有任何具体的逻辑，我只是​​在做一些测试，实际上这是面试时提出的问题，面试官提示我改变循环的顺序以获得更好的性能。顺便说一句，我使用的是 JDK1.5。经过一些测试后，我现在更困惑了，因为程序的结果不一致——有时第一个循环运行得比第二个循环快，但大多数时候它运行得比第二个循环慢。

Answer 1

这个答案适用于更新的问题：

• 如果您正在访问二维数组，例如 int[][]，则内部循环中具有较大值的数组应该会更慢。虽然不是很多，但仍然如此。要稍微了解这个问题，请阅读 Joel 的一篇博客文章中有关街头画家 Shlemiel 的内容。
• 您获得不一致结果的原因是您没有执行任何 JVM 预热。 JVM 不断分析运行的字节码并对其进行优化，通常只有在 30 到 50 次迭代之后才以最佳速度运行。是的，这意味着您需要先运行代码几十次，然后根据另外几十次运行的平均值对其进行基准测试，因为垃圾收集器会减慢几次运行的速度。
• 一般注意，使用 Long 对象而不是 long 原语只是愚蠢的，JVM 很可能通过将其替换为原语来优化它，如果可以的话，如果不能的话，使用它肯定会出现一些（尽管非常轻微）持续的速度减慢。

Answer 2

编辑：原始答案如下。现在您已经修复了该示例，以便所有循环变量都从 0 开始，但我们又回到了没有足够信息的情况。看起来可能是缓存一致性/引用位置问题 - 但我们只是猜测。如果您可以提供一个简短但完整的程序来演示该问题，那将会有所帮助......就像告诉我们我们正在谈论哪种语言/平台一样！

---

第一个循环有 10 * 999999 = 9999990 次迭代。第二个循环有 1000000 * 9 = 9000000 次迭代。因此，我预计（所有其他条件相同）第一个循环需要更长的时间。

但是，您尚未表明您正在做什么工作或该工作在什么平台上进行。有很多因素可能会影响事情：

• 第二个循环可能会更好地命中缓存
• 如果您使用的是 JIT 编译平台，JIT 可能会选择更大力地优化第二个循环。
• 您正在执行的操作本身可能有缓存或类似的东西
• 如果您正在执行少量工作但它首先需要加载和初始化一堆类型，这可能会导致第一个循环变慢

Answer 3

问题转移了。这些不是您想要的机器人...

因为您在第一个示例中做了约 1000000 倍的工作。 ;-)

Answer 4

如果您查看生成的字节码，就会发现这两个循环几乎相同。除了当它执行 10 循环的 while 条件时，Java 从指令中获取 10 作为立即值，但是当它执行 1000000 循环的 while 条件时，Java 从变量加载 1000000。我没有任何关于执行每条指令需要多长时间的信息，但立即加载似乎比从变量加载更快。

请注意，在第一个循环中，必须与 1000000 进行比较 1000 万次，而在第二个循环中只需要进行 100 万次。当然，在第二个循环中与 10 进行比较的频率要高得多，但如果变量加载比立即加载慢得多，那就可以解释您所看到的结果。