The*_*ack 24 java math performance max min
编辑:maaartinus给出了我正在寻找的答案,而tmyklebu关于这个问题的数据帮助了很多,所以谢谢两者!:)
我已经阅读了一些关于HotSpot如何在代码中注入一些"内在函数"的内容,特别是对于Java标准Math libs(来自这里)
所以我决定尝试一下,看看HotSpot可以直接做出多大的反对(特别是因为我听说min/max可以编译成无分支的asm).
public static final int max ( final int a, final int b )
{
if ( a > b )
{
return a;
}
return b;
}
这是我的实施.从另一个SO问题我已经读过,使用三元运算符使用额外的寄存器,我没有发现在执行if块和使用三元运算符之间存在显着差异(即返回(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'被添加到基准块之外的列表中并稍后打印,以避免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()(即回报(A> = B)A:B)我仍然取得更好的成绩!这没有道理.
眼镜:
CPU: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之间的差异相同.
maa*_*nus 11
很难说为什么Math.max慢于a Ops.max,但很容易说出为什么这个基准强烈支持分支到条件移动:在第n-6次迭代时,概率为
Math.max( array[i], max );
不等于是比所有先前元素更大max的概率array[n-1].显然,随着增长n和给定,这种可能性越来越低
final int[] array = new int[(8*1024*1024)/4];
在大多数情况下它可以忽略不计.条件移动指令对分支概率不敏感,它总是花费相同的时间来执行.如果分支很难预测,则条件移动指令比分支预测快.另一方面,如果可以高概率地预测分支,则分支预测更快.目前,我不确定条件移动的速度与分支的最佳和最差情况相比.1
在你的情况下,除了前几个分支以外的所有分支都是可预测 从大约n == 10开始,使用条件移动是没有意义的,因为分支可以保证正确预测并且可以与其他指令并行执行(我猜你每次迭代只需要一个循环).
这似乎发生在计算最小值/最大值或进行一些低效排序的算法上(良好的分支可预测性意味着每步的低熵).
1条件移动和预测分支都需要一个周期.前者的问题是它需要两个操作数,这需要额外的指令.最后,当分支单元空闲时,关键路径可能变得更长和/或ALU饱和.通常,但并非总是如此,在实际应用中可以很好地预测分支; 这就是分支预测首先发明的原因.
至于时序条件移动与分支预测最佳和最差情况的血腥细节,请参阅下面的评论中的讨论.我的我自己的基准表明,有条件的举动是在分支预测遇到的最坏情况比分支预测显著快,但我不能忽视矛盾的结果.我们需要一些解释才能确切地发挥作用.一些更多的基准和/或分析可能会有所帮助.