9

请参阅以下代码段：

    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。经过一些测试，我现在更加困惑，因为程序的结果并不一致——有时第一个循环运行得比第二个快，但大多数时候它的运行速度比第二个慢。

4

4 回答 4

6

编辑：原始答案如下。现在您已经修复了示例，使所有循环变量都从 0 开始，我们又回到了没有足够信息的状态。这似乎是一个缓存一致性/参考局部性问题——但我们只是在猜测。如果您可以提供一个简短但完整的程序来演示该问题，那将有所帮助……就像告诉我们要从哪种语言/平台开始一样！

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

但是，您还没有说明您正在做什么工作或这是在哪个平台上。有很多事情可能会影响事情：

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

此答案适用于更新后的问题：

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

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

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

于 2010-03-31T06:07:41.623 回答
2

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

请注意，在第一个循环中，与 1000000 的比较必须进行 1000 万次，而在第二个循环中只进行 100 万次。当然，与 10 的比较在第二个循环中更频繁地进行，但如果可变负载比直接负载慢得多，那就可以解释您所看到的结果。

于 2010-03-31T07:36:18.283 回答