嵌套循环的效率

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

编辑:原始答案如下.现在您已经修复了示例以便所有循环变量从0开始,我们又回到了没有足够的信息.这似乎很可能,它的职权问题,高速缓存一致性/地区-但我们只是猜测.如果你能提供一个简短但完整的程序来证明这个问题,那将会有所帮助......就像告诉我们我们正在谈论的语言/平台一样!

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

但是,您没有说明您正在做什么工作或者这是什么平台.有很多事情可能影响事物:

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

Answer 2

这个答案是针对更新的问题：

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