use*_*577 15 java jit bytecode jvm-hotspot hotspot
(注意:正确答案必须超越复制).
在数百万次调用之后,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<N; i++) {
res = c.call();
}
Double d = 1e-6*(System.nanoTime() - t);
p(msg+": "+d+" ms (res="+res+")");
}
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
}
//============
public static void main(String[] args) throws Exception {
int N = 20000;
int n = 1000;
int bound = 10000;
Random r = new Random(1);
for(int i=0; i<5; i++) {
testperf(N, r, n, bound);
//System.gc();
}
}
static void testperf(int N, Random r, int n, int bound) throws Exception {
final int[] orig = r.ints(n, 0, bound).toArray();
final int[] a = orig.clone();
perf(N, "qs1", () -> {
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 < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort1(a, _from, j-1, sleft);
if(j+1 < _to)
quicksort1(a, j+1, _to, sright);
}
}
private static void quicksort2(int[] a, final int _from, final int _to) {
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 < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort2(a, _from, j-1);
if(j+1 < _to)
quicksort2(a, j+1, _to);
}
}
}
更新:
我做了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(i < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort1(a, _from, j-1, sleft);
if(j+1 < _to)
quicksort1(a, j+1, _to, sright);
}
}
private static void quicksort2(int[] a, final int _from, final int _to) {
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 < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort2(a, _from, j-1);
if(j+1 < _to)
quicksort2(a, j+1, _to);
}
}
}
更新:
此时,我运行并捕获了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/answers/1716699981/上的最新说明进行操作.我有7MB xml日志文件(压缩到675kB)你可以得到它,并在https://wetransfer.com/downloads/65fe0e94ab409d57cba1b95459064dd420180427150905/612dc9上查看7天(到期〜可能是2018年4月), 以防你理解它(在jitwatch当然!).
添加的字符串参数导致更紧凑的汇编代码.问题(仍然没有答案)是为什么？汇编代码有什么不同？在较慢的代码中没有使用的规则或优化是什么？
我能够重现你的结果.机器数据:
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 < data.length; iteration++) {
for (int testcase = 0; testcase < data[iteration].length; testcase++) {
data[iteration][testcase] = random.ints(numberCount, 0, bound).toArray();
}
}
FileOutputStream fos = new FileOutputStream("test_array.dat");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(data);
之后我运行了这个测试(热身,拆解运行):
{
FileInputStream fis = new FileInputStream(fileName);
ObjectInputStream iis = new ObjectInputStream(fis);
int[][][] data = (int[][][]) iis.readObject();
perf("qs2", () -> {
for (int iteration = 0; iteration < data.length; iteration++) {
for (int testCase = 0; testCase < data[iteration].length; testCase++) {
quicksort2(data[iteration][testCase], 0, data[iteration][testCase].length - 1);
}
}
return null;
});
}
{
FileInputStream fis = new FileInputStream(fileName);
ObjectInputStream iis = new ObjectInputStream(fis);
int[][][] data = (int[][][]) iis.readObject();
perf("qs1", () -> {
for (int iteration = 0; iteration < data.length; iteration++) {
for (int testCase = 0; testCase < data[iteration].length; testCase++) {
quicksort1(data[iteration][testCase], 0, data[iteration][testCase].length - 1, und);
}
}
return null;
});
}
如果我一起运行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)
我的结论是优化可能受额外参数对象类型的影响.对于对我来说有意义的原语,可能没有那么急切的优化,但我找不到该索赔的确切来源.
我想我在汇编代码中观察到了一些奇怪的东西。
首先，我添加了空行，以便快速排序 1 从第 100 行开始，快速排序 2 从第 200 行开始。排列汇编代码要简单得多。
我还将字符串 arg 更改为 int arg，只是为了测试并证明类型不是问题。
在Excel中排列asm代码的繁琐任务之后，这里是xls文件： https://wetransfer.com/downloads/e56fd98fe248cef98f5a242b2db64f6920180430130753/7b8f2b （可用7天）。（如果我的颜色不一致，我很抱歉，我厌倦了......）
我看到的模式是有更多的 mov 操作来准备快速排序2。如果我理解正确的话，本机代码的内联会更长，并且由于递归，它会退化一些级别，但足以导致速度变慢。我不太了解操作，无法猜测更多。
换句话说，当从递归返回点向上的最后一个快速排序堆栈帧可能可以内联 3 或 5 层（很难说）时，它就会诉诸跳转。然而，由于不清楚的原因，这些 Quicksort2 的字节码框架使用了更多的本机代码，增加了数百个额外的操作。
至此，我已经得到了 50% 的答案。C2 创建的代码稍显臃肿，但由于递归尾帧的内联而变得臃肿。
我想我要向 oracle 提交一个 bug...这是一个相当大的挑战，但最终，令人非常失望的是，未使用的 java 代码带来了更好的性能！