|
(注意:正确答案必须超越复制)。
在数百万次调用之后，quicksort1 肯定比 quicksort2 快，除了这 1 个额外的 arg 之外，它们具有相同的代码。
代码在帖子的最后。剧透:我还发现 jit 代码胖了 224 个字节，即使它实际上应该更简单(就像字节代码大小说明的那样；请参阅下面的最新更新)。
即使在尝试使用一些微基准测试工具 (JMH) 消除这种影响之后，性能差异仍然存在。
我在问:为什么生成的 native 代码有如此大的差异，它在做什么？
通过向方法添加参数，它会使其更快......!
我知道 gc/jit/warmup/etc 的影响。您可以按原样运行代码，也可以使用更大/更小的迭代计数。实际上，您甚至应该先注释掉一个然后另一个 perf 测试并在不同的 jvm 实例中运行每个测试，以证明它不是彼此之间的干扰。
除了 sleft/sright 明显的 getstatic 以及一个奇怪的“iload 4”而不是“iload_3”(和 istore 4/istore_3)之外，字节码没有显示出太大差异
到底他妈发生了什么？ iload_3/istore_3 真的比 iload 4/istore 4 慢吗？这么慢，即使添加了 getstatic 调用仍然没有使它变慢？我可以猜测静态字段未使用，因此 jit 可能会跳过它。
无论如何，我这边没有歧义，因为它总是可重现的，我正在寻找有关 javac/jit 为什么做了他们所做的事情以及为什么性能受到如此大的影响的解释。这些是具有相同数据、相同内存流失等的相同递归算法......如果我愿意，我无法进行更孤立的更改，以显示显着的可复制运行时差异。
环境:
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 rintSafepointStatisticsCount=1
-XX:+UnlockDiagnosticVMOptions -XX:+LogCompilation -XX:+PrintInlining
jitwatch 没有明显的“建议”，只是对于 quicksort1 和 quicksort2 来说，rgular 太大而不能内联或太深。
一个重要的发现是字节码和 native 代码的区别:
使用额外的方法参数(quicksort1):
字节码 = 187 字节
native 代码 = 1872 字节
没有额外的方法参数(quicksort2):
字节码 = 178 字节 (小 9 个字节)
native 代码 = 2096 字节 (大 224 字节!!!)
这是一个强有力的证据，证明 jit 代码在 quicksort2 中更胖和更慢。
所以问题仍然存在:C2 jit 编译器在想什么？当我添加一个方法参数和 2 个静态引用来加载和传递时，什么规则使它创建更快的 native 代码？
我终于掌握了汇编代码，但正如我所料，几乎不可能区分和理解发生了什么。我遵循了我能从 https://stackoverflow.com/a/24524285/2023577 中找到的最新说明。 .我有 7MB xml 日志文件(压缩为 675kB)，您可以在 https://wetransfer.com/downloads/65fe0e94ab409d57cba1b95459064dd420180427150905/612dc9 获取它并查看 7 天(到期~2018 年 5 月 4 日)以防万一你能理解它(当然是在 jitwatch 中!)。
添加的字符串参数导致更紧凑的汇编代码。问题(仍未回答)是为什么？汇编代码有什么不同？在较慢的代码中未使用的规则或优化是什么？
Best Answer-推荐答案
复制与分析
我能够重现你的结果。机器数据:
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 的数组结构并保存了它:
在那之后，我运行了这个测试(热身、拆卸运行):
如果我同时运行 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
其中 % 表示 on stack replacement (where the compiled code is running) 。根据此日志，带有额外 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
这意味着方法在调用之前被fored 阻塞编译，但时间保持不变:
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)
我的结论是优化可能会受到额外参数对象类型的影响。对于对我来说有意义的原语，可能没有那么急切的优化，但我找不到该声明的确切来源。
An additional interesting read.
关于java - 通过简单地添加方法参数(更精简的 jit 代码)，无法解释的 10% 以上的性能提升，我们在Stack Overflow上找到一个类似的问题：
https://stackoverflow.com/questions/49754232/
| 
客服电话
APP下载
官方微信
