3

在下面的代码和结果中，我们可以看到“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

这意味着如果我们在里面放更长的interaction会有更好的性能。而且它似乎与缓存命中理论有一些冲突。

4

4 回答 4

2

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

例如：

  • 您的基准测试没有考虑“JVM 预热”效应，例如 JIT 编译器不会立即编译为本机代码这一事实。（这只会在代码执行一段时间后发生，并且 JVM 已经测量了一些使用次数以帮助优化。）处理这个问题的正确方法是将整个代码放在一个运行几次的循环中，然后丢弃任何看起来“奇怪”的初始时间集合......由于热身效应。

  • 理论上可以优化基准中的循环。JIT 编译器可能能够推断出它们不做任何影响程序输出的工作。

最后，我想提醒您，像这样的手动优化通常是一个坏主意……除非您有令人信服的证据表明手动优化是值得的，并且此代码确实是应用程序所在的位置花费大量时间。

于 2012-09-08T15:42:54.490 回答
1

首先，始终循环运行多次微基准测试。然后你会看到两个时间都是 0，因为数组大小太小了。要获得非零次，请将数组大小增加 100 倍。Traverse1 的时间约为 32 毫秒，Traverse2 的时间约为 250 毫秒。不同之处在于处理器使用高速缓存。访问顺序内存地址要快得多。

于 2012-09-08T15:41:52.997 回答
1

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

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 需要 1.5 倍于 Traverse2 的比较次数。

于 2012-09-08T16:56:18.173 回答
1

我的输出（与您的原始代码 100i/10j 与 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中的“数组数组”。因此，最右边的索引将显示一个连续区域。第一个版本更快。

2.将较长的交互放入较短的交互中会有更好的性能吗？

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

增加第一个索引会更慢，因为下一次迭代会消失千字节，因此您不能再使用缓存行。

绝对不！

于 2012-09-08T15:29:06.833 回答