不明原因的 10%+ 性能提升只是简单地添加一个方法参数（更精简的 jit 代码）

Question

（注意：正确答案必须超越复制）。

经过数百万次调用后，quicksort1 肯定比 quicksort2 快，除了这 1 个额外的 arg 之外，它们具有相同的代码。

代码在post的末尾。剧透：我还发现 jit 代码变胖了 224 字节，即使它实际上应该更简单（如字节代码大小所示；请参阅下面的最新更新）。

即使尝试使用一些微基准测试工具 (JMH) 排除这种影响，性能差异仍然存在。

我在问：为什么生成的本机代码有如此大的差异，它在做什么？

通过向方法添加参数，可以使其更快...！我知道 gc/jit/warmup/etc 效果。您可以运行按原样编码，或使用 larger/smaller 迭代计数。实际上，您甚至应该在不同的 jvm 实例中分别注释掉一个性能测试和运行，以证明它们之间不是相互干扰。

字节码没有太大区别，除了 sleft/sright 的明显 getstatic，还有一个 st运行ge '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:PrintSafepointStatisticsCount=1
-XX:+UnlockDiagnosticVMOptions  -XX:+LogCompilation -XX:+PrintInlining

对于 quicksort1 和 quicksort2，jitwatch 中没有明显的 "suggestions"，只是规则太大而无法内联或太深。

一个重要的发现是字节码和本地代码的区别：

使用额外的方法参数（quicksort1）：字节码 = 187 字节本机代码 = 1872 字节

没有额外的方法参数（quicksort2）：字节码 = 178 字节 （减少 9 字节） 本机代码 = 2096 字节 （大 224 字节！！！）

这是jit代码在quicksort2中更胖更慢的有力证据。

所以问题仍然存在：C2 jit 编译器在想什么？当我添加方法参数和 2 个静态引用以加载和传递时，什么规则使它创建更快的本机代码？

我终于掌握了汇编代码，但正如我所料，几乎不可能区分和理解正在发生的事情。我遵循了从 . I have 7MB xml log file (compressed to 675kB) you can get it and see for 7 days (expire ~may 4th 2018) at https://wetransfer.com/downloads/65fe0e94ab409d57cba1b95459064dd420180427150905/612dc9 中找到的最新说明，以防您理解它（当然是在 jitwatch 中！）。

添加的字符串参数导致更紧凑的汇编代码。问题（仍然没有答案）是为什么？汇编代码有什么不同？较慢的代码中未使用的规则或优化是什么？

Answer 1

复制与分析

我能够重现您的结果。机器数据：

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

结果如"expected"（越小的字节码越快）：

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

这意味着方法在调用之前被强制阻塞编译但时间保持不变：

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.

Answer 2

我想我在汇编代码中观察到了一些奇怪的东西。

首先，我添加了空行，使 quicksort1 从第 100 行开始，quicksort2 从第 200 行开始。排列汇编代码要简单得多。

我也把string arg改成了int arg，只是为了测试证明类型不是问题。

在 excel 中排列 asm 代码的繁琐任务之后，这里是 xls 文件： https://wetransfer.com/downloads/e56fd98fe248cef98f5a242b2db64f6920180430130753/7b8f2b （可使用 7 天）。（对不起，如果我的颜色不一致，我受够了...）

我看到的模式是有更多的 mov 操作来准备 quicksort2。如果我理解正确的话，本机代码的内联会更长，并且由于递归，它退化了几个级别但足以导致速度下降。我对 ops 的理解不够深入，无法猜测。

换句话说，当递归的最后一个快速排序栈帧 return 向上指向可能有 3 或 5 个级别（很难说）可以被内联时，然后它求助于跳转。然而，这些 quicksort2 的字节码帧由于不明原因使用了更多本机代码，加起来多达数百个额外的操作。

至此，我对答案的理解程度已达到 50%。 C2 创建的代码稍胖，但由于递归尾帧的内联而膨胀。

我想我要向 oracle 提交错误...这是一个相当大的挑战，但最终，令人非常失望的是未使用的 java 代码会带来更好的性能！

不明原因的 10%+ 性能提升只是简单地添加一个方法参数（更精简的 jit 代码）

unexplained 10%+ performance boost from simply adding a method argument (slimmer jit code)

java

jit

bytecode

jvm-hotspot

hotspot

原因