Java中多维数组的遍历性能

Question

在下面的代码和结果中，我们可以看到“Traverse2”比“Traverse1”快得多，实际上它们只遍历了相同数量的元素。

1.这种差异是如何发生的？

2.将更长的迭代放在更短的迭代中会有更好的性能吗？

public class TraverseTest {

    public static void main(String[] args)
    {
        int a[][] = new int[100][10];
        System.out.println(System.currentTimeMillis());

        //Traverse1
        for(int i = 0; i < 100; i++)
        {
            for(int j = 0; j < 10; j++)
                a[i][j] = 1;
        }

        System.out.println(System.currentTimeMillis());

        //Traverse2
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 100; j++)
                a[j][i] = 2;
        }

        System.out.println(System.currentTimeMillis());
    }
}

结果：

1347116569345

1347116569360

1347116569360

如果我改变它

System.out.println(System.nanoTime());

结果将是：

4888285195629

4888285846760

4888285914219

这意味着，如果我们在内部进行更长的迭代，性能会更好。而且似乎与缓存命中理论存在一些冲突。

- Jingjing Zhong

---

可能是为什么循环的顺序会影响在迭代2D数组时的性能？的重复问题。 - user406009

2D数组=数组的数组 - huseyin tugrul buyukisik

Answer 1

我怀疑你在这个微基准测试中看到的任何奇怪结果都是由于基准测试本身存在缺陷所导致的。

例如:

- 你的基准测试没有考虑"JVM热身"效应，即JIT编译器不会立即将代码编译为本机代码(这只会在代码执行一段时间后发生，并且JVM测量了一些使用数字来帮助优化)。正确的处理方式是将整个测试放在运行数次的循环内，并丢弃任何看起来有问题的初始计时，因为存在JVM热身效应。 - 在理论上，你基准测试中的循环可以被优化掉。JIT编译器可能能够推断出这些循环不会对程序输出产生任何影响。

最后，我想提醒你手动优化通常是一个坏主意...除非你有令人信服的证据表明它值得手动优化，并且该代码确实是应用程序花费大量时间的地方。

- Stephen C

Answer 2

首先，始终在循环中运行微基准测试多次。然后，您将看到两个时间都为0，因为数组大小太小。要获得非零时间，请将数组大小增加100倍。我的时间大约为32毫秒的Traverse1和250的Traverse2。差异是因为处理器使用缓存内存。访问连续的内存地址要快得多。

- Alexei Kaigorodov

Answer 3

我的输出（使用您的原始代码 100i/10j vs 10i/100j）：

1347118083906
1347118083906
1347118083906

你在进行非常快速的计算时，使用了非常糟糕的时间分辨率。

我将i和j的限制都改为了1000。

    int a[][] = new int[1000][1000];
    System.out.println(System.currentTimeMillis());

    //Traverse1
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[i][j] = 1;
    }

    System.out.println(System.currentTimeMillis());

    //Traverse2
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[j][i] = 2;
    }

    System.out.println(System.currentTimeMillis());

输出：

1347118210671
1347118210687 //difference is 16 ms
1347118210703 //difference is 16 ms again -_-

有两种可能：

• Java热点将第二个循环改为第一类型或通过交换i和j进行优化。
• 时间分辨率仍然不够。

所以我将输出更改为System.nanoTime()。

    int a[][] = new int[1000][1000];
    System.out.println(System.nanoTime());

    //Traverse1
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[i][j] = 1;
    }

    System.out.println(System.nanoTime());

    //Traverse2
    for(int i = 0; i < 1000; i++)
    {
        for(int j = 0; j < 1000; j++)
            a[j][i] = 2;
    }

    System.out.println(System.nanoTime());

输出：

16151040043078
16151047859993 //difference is 7800000 nanoseconds
16151061346623 //difference is 13500000 nanoseconds --->this is half speed

1. 这种差异是如何发生的？

请注意，即使省略了您，您也使用了错误的时间分辨率，并对不相等的情况进行了错误的比较。第一个是连续访问，而第二个则不是。

假设第一个嵌套循环只是为第二个嵌套循环做热身准备，那么你的“第二个更快”的假设就更加错误了。

不要忘记，在Java中，2D数组是“数组的数组”。因此，最右侧的索引将显示一个连续的区域。对于第一个版本来说更快。

2. 将更长的迭代放在更短的迭代中会有更好的性能吗？

for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 100; j++)
            a[j][i] = 2;
    }

增加第一个索引会变慢，因为下一次迭代会距离kbytes很远，所以您不能再使用缓存行。

绝对不是这样的！

- huseyin tugrul buyukisik

---

在你的代码中，外部迭代与内部迭代是相同的，因此时间也是相同的。我想知道如果它们不同，比如1000与10，是什么导致了两种不同迭代方式的性能差异。 - Jingjing Zhong

我认为你没有理解我的描述。我强调外部迭代次数比内部迭代次数更多似乎具有较低的性能。 - Jingjing Zhong

1. 这种差异是如何发生的？答案在结尾处。
2. 在较短的迭代中放置更长的迭代会有更好的性能吗？绝对不会。

- huseyin tugrul buyukisik

Answer 4

在我看来，数组的大小也会影响结果。例如：

public class TraverseTest {

    public static void main(String[] args)
    {
        int a[][] = new int[10000][2];
        System.out.println(System.currentTimeMillis());

        //Traverse1
        for(int i = 0; i < 10000; i++)
        {
            for(int j = 0; j < 2; j++)
                a[i][j] = 1;
        }

        System.out.println(System.currentTimeMillis());

        //Traverse2
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 10000; j++)
                a[j][i] = 2;
        }

        System.out.println(System.currentTimeMillis());
    }
}

Traverse1需要10000*3+1 = 30001次比较来决定是否退出迭代，然而Traverse2只需要2*10001+1 = 20003次比较。

Traverse1需要的比较次数是Traverse2的1.5倍。

- chouchou

---

当迭代次数不多且内部与外部差异较大时，这似乎是一个因素。 - Jingjing Zhong