Java 7排序“优化”

在Java6中，对于基元和对象数组分别使用快速排序和合并排序Arrays#sort。在Java7中，这两个都发生了变化，分别为DualPivotQuicksort和Timsort。Java 7排序“优化”

在源为新的快速排序，下面的注释出现在几个地方（如线354）：

/* 
    * Here and below we use "a[i] = b; i++;" instead 
    * of "a[i++] = b;" due to performance issue. 
    */

如何，这是一个性能问题？编译器不会将这些减少到相同的东西吗？

更广泛地说，自己调查这件事的好策略是什么？我可以运行基准测试，但我更愿意分析编译代码中的任何差异。但是，我不知道使用什么工具等。

来源

2011-07-13 Matthew Gilliard

无论是热点编译器做了什么错误（不太可能）或写了microbenchmark的人搞砸了......我打赌后者。（有一些代码看起来好于另一个代码的原因有很多，比如内存页面，环境大小和什么不是） – bestsss

@bestsss当然总是可能的，但是编写这些代码（以及随后的注释）的人*知道*如何编写基准。毕竟，Java quicksort的实现已经基准化并被微调为死亡。 –

仅供参考，本课程的归属@authors是Josh Bloch，Jon Bentley（编程珍珠的作者）和Vladimir Yaroslavskiy –

这只是一般问题的答案。

您可以查看字节码并尝试了解其差异。即你可以写一个简单的例子，使用a[i] = b; i++;和a[i++] = b;，看看有什么区别。

最简单的显示字节码的方法是javap程序（应包含在您的JDK中）。使用javac SomeFile.java编译代码，并在代码上运行javap：javap -c SomeFile（-c开关告诉javap输出文件中每个方法的字节码）。

如果你使用的是Eclipse，你也可以尝试this one。

来源

2011-07-13 09:36:12

谢谢 - 这个插件确实显示生成的字节码不一样。现在阅读如何阅读字节码！ –

我不确定在字节码中是多么明确。毕竟，大多数优化都发生在JIT中。我会更进一步：在这种情况下字节码是完全不相关的，这个答案是误导性的。 –

得益于HotSpot的许多优化，仅查看字节码不会获得关于jitting之后的预期性能的很多线索。 –

有一种方法可以让您看到processor instructions generated by the hotspot engine。

来源

2011-07-13 10:15:54

我很想听听那个工具的名字 - 这非常有用，或者至少是有趣的。 – Voo

@Voo，它不是一个，它是一个热点选项。 http://wikis.sun.com/display/HotSpotInternals/PrintAssembly，但检查它的最好方法就是附加gdb。 – bestsss

@bestsss - 谢谢，那就是我一直在寻找的！我已经更新了我的答案。 –

我写了2种方法test1的和TEST2并添加编译后的字节码（Java 1.6的雪豹）的主要部分为注释：

/* 
    *  14 iload_1 [b]  -> load value from address 1 to sack 
    *  15 iastore   -> store value from stack into int array 
    *  16 iinc 3 1 [i]  -> int increment value of address 3 
    *  19 iinc 3 1 [i]  -> int increment value of address 3 
    */ 
    public void test1() { 
     int b = 0; 
     int a[] = new int[10]; 
     for (int i=0; i<10; i++) { 
      a[i] = b; 
      i++; 
     } 
    } 

    /* 
    *  14 iinc 3 1 [i]  -> increment value of address 3 
    *  17 iload_1 [b]  -> load value from address 1 to stack 
    *  18 iastore   -> store value from stack into int array 
    *  19 iinc 3 1 [i]  -> increment value of address 3 
    */ 
    public void test2() { 
     int b = 0; 
     int a[] = new int[10]; 
     for (int i=0; i<10; i++) { 
      a[i++] = b; 
     } 
    }

的inc OPS的顺序是不同的。但是两种方法test1和test2的运算总和是相等的！所以字节码的性能也应该是一样的。

来源

2011-07-13 10:16:01 timaschew

可以想象，优化器可能会优化两个连续inc调用为一个添加$ reg，2调用（我认为应该更快至少在x86上？），这对于第二个变体来说更难 - 仍然可行，但也许可以热点当前优化不？ – Voo

Java 7排序“优化”

回答

相关问题