Java Math.min / max性能

Question

编辑：maaartinus给出了我一直在寻找的答案，而tmyklebu的关于该问题的数据帮助很大，所以都谢谢！:)

我已经阅读了一些有关HotSpot如何在代码中注入一些“本能”的信息，特别是针对Java标准Math库的（从此处开始）

因此，我决定尝试一下，看看HotSpot与直接进行比较有何不同（特别是因为我听说过min / max可以编译为无分支的asm）。

    public static final int max ( final int a, final int b )
{
    if ( a > b )
    {
        return a;
    }

    return b;
}

那是我的实现。从另一个SO问题中，我读到使用三元运算符会使用一个额外的寄存器，但在执行if块和使用三元运算符之间，我并没有发现明显的区别（即return（a>
b）？a：b）。

分配一个8Mb int数组（即200万个值）并将其随机化，我进行以下测试：

try ( final Benchmark bench = new Benchmark( "millis to max" ) )
    {
        int max = Integer.MIN_VALUE;

        for ( int i = 0; i < array.length; ++i )
        {
            max = OpsMath.max( max, array[i] );
            // max = Math.max( max, array[i] );
        }
    }

我在try-with-
resources块中使用Benchmark对象。完成后，它将在对象上调用close（）并打印该块完成所需的时间。通过注释/隐藏上面代码中的max调用，分别进行测试。

“ max”被添加到基准块之外的列表中，并在以后打印，以免JVM将整个块优化掉。

每次测试运行时，将对阵列进行随机化。

运行测试6次，结果如下：

Java标准数学：

millis to max 9.242167 
millis to max 2.1566199999999998
millis to max 2.046396 
millis to max 2.048616  
millis to max 2.035761
millis to max 2.001044

这样，在第一次运行后就相当稳定，然后再次运行测试会得到相似的结果。

OpsMath：

millis to max 8.65418 
millis to max 1.161559  
millis to max 0.955851 
millis to max 0.946642 
millis to max 0.994543 
millis to max 0.9469069999999999

同样，第一次运行后结果非常稳定。

问题是： 为什么？ 那是一个很大的区别。而且我不知道为什么。即使我 完全 像Math.max（）一样实现max（）方法（即return（a>
= b）？a：b），我仍然可以获得更好的结果！这个不成立。

眼镜：

处理器：Intel i5 2500，3,3Ghz。Java版本：JDK 8（3月18日公开发行），x64。Debian Jessie（测试版）x64。

我尚未尝试使用32位JVM。

编辑：按要求进行的自包含测试。添加了一行以强制JVM预加载Math和OpsMath类。这样就消除了OpsMath测试第一次迭代所需的18ms成本。

// Constant nano to millis.
final double TO_MILLIS = 1.0d / 1000000.0d;
// 8Mb alloc.
final int[] array = new int[(8*1024*1024)/4];
// Result and time array.
final ArrayList<Integer> results = new ArrayList<>();
final ArrayList<Double> times = new ArrayList<>();
// Number of tests.
final int itcount = 6;
// Call both Math and OpsMath method so JVM initializes the classes.
System.out.println("initialize classes " + 
OpsMath.max( Math.max( 20.0f, array.length ), array.length / 2.0f ));

final Random r = new Random();
for ( int it = 0; it < itcount; ++it )
{
    int max = Integer.MIN_VALUE;

    // Randomize the array.
    for ( int i = 0; i < array.length; ++i )
    {
        array[i] = r.nextInt();
    }

    final long start = System.nanoTime();
    for ( int i = 0; i < array.length; ++i )
    {
        max = Math.max( array[i], max );
            // OpsMath.max() method implemented as described.
        // max = OpsMath.max( array[i], max );
    }
    // Calc time.
    final double end = (System.nanoTime() - start);
    // Store results.
    times.add( Double.valueOf( end ) );
    results.add( Integer.valueOf(  max ) );
}
// Print everything.
for ( int i = 0; i < itcount; ++i )
{
    System.out.println( "IT" + i + " result: " + results.get( i ) );
    System.out.println( "IT" + i + " millis: " + times.get( i ) * TO_MILLIS );
}

Java Math.max结果：

IT0 result: 2147477409
IT0 millis: 9.636998
IT1 result: 2147483098
IT1 millis: 1.901314
IT2 result: 2147482877
IT2 millis: 2.095551
IT3 result: 2147483286
IT3 millis: 1.9232859999999998
IT4 result: 2147482828
IT4 millis: 1.9455179999999999
IT5 result: 2147482475
IT5 millis: 1.882047

OpsMath.max结果：

IT0 result: 2147482689
IT0 millis: 9.003616
IT1 result: 2147483480
IT1 millis: 0.882421
IT2 result: 2147483186
IT2 millis: 1.079143
IT3 result: 2147478560
IT3 millis: 0.8861169999999999
IT4 result: 2147477851
IT4 millis: 0.916383
IT5 result: 2147481983
IT5 millis: 0.873984

总体结果还是一样。我试过只对数组进行一次随机化，然后在同一数组上重复测试，总体上可以获得更快的结果，但是Java
Math.max和OpsMath.max的差异是2倍。

Answer 1

很难说出为什么Math.max比a慢Ops.max，但是很容易说出为什么该基准测试强烈支持分支到条件移动：在n-th迭代中，

Math.max( array[i], max );

不等于是大于所有先前元素max的概率array[n-1]。显然，这种可能性变得更低，并降低增长n并给予

final int[] array = new int[(8*1024*1024)/4];

在大多数情况下，它几乎可以忽略不计。条件移动指令对分支概率不​​敏感，它总是花费相同的时间来执行。 如果 分支很难预测， 则
条件移动指令比分支预测快。另一方面，如果可以高概率很好地预测分支，则分支预测会更快。目前，我不确定条件转移的速度与分支的最佳和最差情况相比。1个

在您的情况下，除了前几个分支外，所有分支都是可以预测的。从大约n == 10开始，使用条件移动是没有意义的，因为可以肯定地保证了分支的正确预测，并且可以与其他指令并行执行（我猜您每次迭代只需要一个周期）。

这似乎发生在算法计算最小值/最大值或进行一些低效率的排序时（好的分支可预测性意味着每步熵低）。

1条件移动和预测分支都需要一个周期。前者的问题在于它需要两个操作数，这需要额外的指令。最后，当分支单元空闲时，关键路径可能会变长和/或ALU饱和。通常，但并非总是如此，在实际应用中可以很好地预测分支。这就是为什么首先创建分支预测的原因。

至于定时条件移动与分支预测最佳和最差情况的详细信息，请参见下面的评论讨论。我的我自己的基准表明，有条件的举动是显著比分支预测时更快分支预测遇到的最糟糕的情况，但我不能忽视矛盾的结果。我们需要一些解释到底是什么与众不同。一些其他基准和/或分析可能会有所帮助。