(注意:正确答案必须超越复制).
在数百万次调用之后,quicksort1肯定比quicksort2更快,除了这个额外的arg之外,它们具有相同的代码.
代码在帖子的末尾.Spoiler:我还发现jit代码比224字节更胖,即使它实际上应该更简单(如字节代码大小告诉;请参阅下面的最后更新).
即使试图用一些微基准线束(JMH)来解决这种影响,性能差异仍然存在.
我在问:为什么生成的本机代码存在这样的差异,它在做什么?
通过向方法添加参数,它使它更快......!我知道gc/jit/warmup/etc效果.您可以按原样运行代码,也可以使用更大/更小的迭代计数.实际上,你甚至应该注释掉一个然后另一个性能测试并在不同的jvm实例中运行它们,只是为了证明它不是彼此之间的干扰.
字节码没有显示出太大的区别,除了明显的getstatic为sleft/sright,还有一个奇怪的'iload 4'而不是"iload_3"(和istore 4/istore_3)
到底他妈发生了什么?iload_3/istore_3真的比iload 4/istore 4慢吗?即使添加的getstatic调用仍然没有让它变慢,那要慢得多?我猜测静态字段是未使用的,因此jit可能只是跳过它.
无论如何,我的方面没有任何歧义,因为它总是可重复的,我正在寻找解释为什么javac/jit做了他们所做的,以及为什么性能受到如此大的影响.这些是相同的递归算法,具有相同的数据,相同的内存流失等等...如果我愿意,我无法进行更加孤立的更改,以显示可重复的运行时差异.
ENV:
java version "1.8.0_161" Java(TM) SE Runtime Environment (build 1.8.0_161-b12) Java HotSpot(TM) 64-Bit Server VM (build 25.161-b12, mixed mode) (also tried and reproduced on java9) on a 4 core i5 laptop 8GB ram. windows 10 with the meltdown/specter patch.
使用-verbose:gc -XX:+ PrintCompilation,没有gc和jit编译在C2(第4层)中已经稳定.
n = 20000时:
main]: qs1: 1561.3336199999999 ms (res=null) main]: qs2: 1749.748416 ms (res=null) main]: qs1: 1422.0767509999998 ms (res=null) main]: qs2: 1700.4858689999999 ms (res=null) main]: qs1: 1519.5280269999998 ms (res=null) main]: qs2: 1786.2206899999999 ms (res=null) main]: qs1: 1450.0802979999999 ms (res=null) main]: qs2: 1675.223256 ms (res=null) main]: qs1: 1452.373318 ms (res=null) main]: qs2: 1634.581156 ms (res=null)
顺便说一句,美丽的java9似乎使两者更快但仍然相互10-15%的折扣:
[0.039s][info][gc] Using G1 main]: qs1: 1287.062819 ms (res=null) main]: qs2: 1451.041391 ms (res=null) main]: qs1: 1240.800305 ms (res=null) main]: qs2: 1391.2404299999998 ms (res=null) main]: qs1: 1257.1707159999999 ms (res=null) main]: qs2: 1433.84716 ms (res=null) main]: qs1: 1233.7582109999998 ms (res=null) main]: qs2: 1394.7195849999998 ms (res=null) main]: qs1: 1250.885867 ms (res=null) main]: qs2: 1413.88437 ms (res=null) main]: qs1: 1261.5805739999998 ms (res=null) main]: qs2: 1458.974334 ms (res=null) main]: qs1: 1237.039902 ms (res=null) main]: qs2: 1394.823751 ms (res=null) main]: qs1: 1255.14672 ms (res=null) main]: qs2: 1400.693295 ms (res=null) main]: qs1: 1293.009808 ms (res=null) main]: qs2: 1432.430952 ms (res=null) main]: qs1: 1262.839628 ms (res=null) main]: qs2: 1421.376644 ms (res=null)
代码(包括测试):
(请不要注意这个快速排序有多糟糕;它不在问题旁边).
import java.util.Random; import java.util.concurrent.Callable; public class QuicksortTrimmed { static void p(Object msg) { System.out.println(Thread.currentThread().getName()+"]: "+msg); } static void perf(int N, String msg, Callable c) throws Exception { Object res = null; long t = System.nanoTime(); for(int i=0; i{ System.arraycopy(orig, 0, a, 0, orig.length); quicksort1(a, 0, a.length-1, und); return null; }); perf(N, "qs2", () -> { System.arraycopy(orig, 0, a, 0, orig.length); quicksort2(a, 0, a.length-1); return null; }); System.out.println(); } private static void quicksort1(int[] a, final int _from, final int _to, String mode) { int len = _to - _from + 1; if(len==2) { if(a[_from] > a[_to]) { int tmp = a[_from]; a[_from] = a[_to]; a[_to] = tmp; } } else { //len>2 int mid = _from+len/2; final int pivot = a[mid]; a[mid] = a[_to]; a[_to] = pivot; //the pivot value is the 1st high value int i = _from; int j = _to; while(i a[_to]) { int tmp = a[_from]; a[_from] = a[_to]; a[_to] = tmp; } } else { //len>2 int mid = _from+len/2; final int pivot = a[mid]; a[mid] = a[_to]; a[_to] = pivot; //the pivot value is the 1st high value int i = _from; int j = _to; while(i 更新:
我做了JMH测试,它仍然证明quicksort1比quicksort2更快.
# Run complete. Total time: 00:13:38 Benchmark Mode Cnt Score Error Units MyBenchmark.testQuickSort1 thrpt 200 14861.437 ± 86.707 ops/s MyBenchmark.testQuickSort2 thrpt 200 13097.209 ± 46.178 ops/s这是JMH基准:
package org.sample; import java.util.Random; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.Level; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.Setup; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.infra.Blackhole; public class MyBenchmark { static String und = "__________";//10 static { und += und;//20 und += und;//40 und += und;//80 und += und;//160 } static String sleft = "//////////";//10 static { sleft += sleft;//20 sleft += sleft;//40 sleft += sleft;//80 sleft += sleft;//160 } static String sright= "\\\\\\\\\\\\\\\\\\\\";//10 static { sright += sright;//20 sright += sright;//40 sright += sright;//80 sright += sright;//160 } static final int n = 1000; static final int bound = 10000; static Random r = new Random(1); static final int[] orig = r.ints(n, 0, bound).toArray(); @State(Scope.Thread) public static class ThrState { int[] a; @Setup(Level.Invocation) public void setup() { a = orig.clone(); } } //============ @Benchmark public void testQuickSort1(Blackhole bh, ThrState state) { int[] a = state.a; quicksort1(a, 0, a.length-1, und); bh.consume(a); } @Benchmark public void testQuickSort2(Blackhole bh, ThrState state) { int[] a = state.a; quicksort2(a, 0, a.length-1); bh.consume(a); } private static void quicksort1(int[] a, final int _from, final int _to, String mode) { int len = _to - _from + 1; if(len==2) { if(a[_from] > a[_to]) { int tmp = a[_from]; a[_from] = a[_to]; a[_to] = tmp; } } else { //len>2 int mid = _from+len/2; final int pivot = a[mid]; a[mid] = a[_to]; a[_to] = pivot; //the pivot value is the 1st high value int i = _from; int j = _to; while(ia[_to]) { int tmp = a[_from]; a[_from] = a[_to]; a[_to] = tmp; } } else { //len>2 int mid = _from+len/2; final int pivot = a[mid]; a[mid] = a[_to]; a[_to] = pivot; //the pivot value is the 1st high value int i = _from; int j = _to; while(i 更新:
此时,我运行并捕获了jitwatch的jit日志(我使用了1.3.0标记,并且是从https://github.com/AdoptOpenJDK/jitwatch/tree/1.3.0构建的)
-verbose:gc -XX:+PrintGCDateStamps -XX:+PrintGCDetails -Xloggc:"./gc.log" -XX:+UseGCLogFileRotation -XX:NumberOfGCLogFiles=10 -XX:GCLogFileSize=1M -XX:+PrintGCApplicationStoppedTime -XX:+PrintCompilation -XX:+PrintSafepointStatistics -XX:PrintSafepointStatisticsCount=1 -XX:+UnlockDiagnosticVMOptions -XX:+LogCompilation -XX:+PrintInlining无论如何,对于quicksort1和quicksort2来说,jitwatch没有明显的"建议",只有rigular对于内联或太深而言太大了.
一个重要的发现是字节码和本机代码差异:
使用额外的方法参数(quicksort1):字节代码= 187字节本机代码= 1872字节
没有额外的方法参数(quicksort2):字节代码= 178字节(小于9字节) 本机代码= 2096字节(大224字节!!!)
这是一个强有力的证据,表明jit代码在quicksort2中更胖更慢.
所以问题仍然存在:C2 jit编译器的想法是什么?当我添加一个方法参数和2个静态引用加载并传递时,什么规则使它创建更快的本机代码?
我终于得到了汇编代码,但正如我所料,几乎不可能分辨并理解正在发生的事情.我按照/sf/ask/17360801/上的最新说明进行操作.我有7MB xml日志文件(压缩到675kB)你可以得到它,并在https://wetransfer.com/downloads/65fe0e94ab409d57cba1b95459064dd420180427150905/612dc9上查看7天(到期〜可能是2018年4月), 以防你理解它(在jitwatch当然!).
添加的字符串参数导致更紧凑的汇编代码.问题(仍然没有答案)是为什么?汇编代码有什么不同?在较慢的代码中没有使用的规则或优化是什么?
1> Hash..:
复制和Analisys我能够重现你的结果.机器数据:
Linux #143-Ubuntu x86_64 GNU/Linux java version "1.8.0_171" Java(TM) SE Runtime Environment (build 1.8.0_171-b11) Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)我重写了一下你的代码,我做了一些额外的测试.您的考试时间包括
System.arraycopy()
电话.我创建了一个400Mb的阵列结构并保存了它:int[][][] data = new int[iterations][testCases][]; for (int iteration = 0; iteration
之后我运行了这个测试(热身,拆解运行):
{ FileInputStream fis = new FileInputStream(fileName); ObjectInputStream iis = new ObjectInputStream(fis); int[][][] data = (int[][][]) iis.readObject(); perf("qs2", () -> { for (int iteration = 0; iteration
{ for (int iteration = 0; iteration 如果我一起运行qs1和qs2:
main]: qs1: 6646.219874 ms (res=null) main]: qs2: 7418.376646 ms (res=null)结果不依赖于执行顺序:
main]: qs2: 7526.215395 ms (res=null) main]: qs1: 6624.261529 ms (res=null)我也在新的JVM实例中运行代码:
实例一:
main]: qs1: 6592.699738 ms (res=null)实例二:
main]: qs2: 7456.326028 ms (res=null)如果你在没有JIT的情况下尝试它:
-Djava.compiler=NONE结果是"预期的"(较小的字节码更快):
main]: qs1: 56547.589942 ms (res=null) main]: qs2: 53585.909246 ms (res=null)为了更好的分析,我将代码提取到两个不同的类.
我使用jclasslib进行字节码检查.方法长度适合我:
Q1: 505 Q2: 480这对没有JIT的执行有意义:
53585.909246×505÷480 = 56376.842019229这是非常接近56547.589942.
原因对我来说,在编译输出(使用
-XX:+PrintCompilation
)中,我有这些行1940 257 2 QS1::sort (185 bytes) 1953 258 % 4 QS1::sort @ 73 (185 bytes) 1980 259 4 QS1::sort (185 bytes) 1991 257 2 QS1::sort (185 bytes) made not entrant 9640 271 3 QS2::sort (178 bytes) 9641 272 4 QS2::sort (178 bytes) 9654 271 3 QS2::sort (178 bytes) made not entrant其中%表示堆栈替换(编译代码正在运行).根据此日志,带有额外String参数的调用将得到优化,而第二个则不会.我正在考虑更好的分支预测,但这不应该是这种情况(尝试添加randomli生成的字符串作为参数).样本大小(400Mb)主要排除缓存.我想到了优化阈值,但是当我使用这些选项时
-Xcomp -XX:+PrintCompilation -Xbatch
,输出如下:6408 3254 b 3 QS1::sort (185 bytes) 6409 3255 b 4 QS1::sort (185 bytes) 6413 3254 3 QS1::sort (185 bytes) made not entrant 14580 3269 b 3 QS2::sort (178 bytes) 14580 3270 b 4 QS2::sort (178 bytes) 14584 3269 3 QS2::sort (178 bytes) made not entrant这意味着metods在被调用之前被编译阻塞,但时间保持不变:
main]: qs1: 6982.721328 ms (res=null) main]: qs2: 7606.077812 ms (res=null)我认为关键是
String
.如果我将额外(未使用)参数更改为int
它,则一直处理稍慢(使用先前的优化参数运行):main]: qs1: 7925.472909 ms (res=null) main]: qs2: 7727.628422 ms (res=null)我的结论是优化可能受额外参数对象类型的影响.对于对我来说有意义的原语,可能没有那么急切的优化,但我找不到该索赔的确切来源.
另一个有趣的读物.