Details
-
Type:
Improvement
-
Status:
Closed
-
Priority:
Minor
-
Resolution: Fixed
-
Affects Version/s: None
-
Fix Version/s: 2.9.1
-
Component/s: Runtime: Class Library
-
Labels:None
-
Environment:All
-
Number of attachments :
Description
In Arrays.qsort the methods Float.compare and Double.compare are used depending on the values in the array. The compare operations perform the following (copied from GNU Classpath):
if (isNaN
)
return isNaN
? 0 : 1;
if (isNaN)
return -1;
// recall that 0.0 == -0.0, so we convert to infinites and try again
if (x == 0 && y == 0)
return (int) (1 / x - 1 / y);
if (x == y)
return 0;
return x > y ? 1 : -1;
In the normal case we're going to hit 6 floating point compares. The case of 0, 0 is common due to using qsort on branch profiles, and this results in 2 divides and 1 subtract. Given we're just comparing to values we should be able to do this substantially cheaper in a VM specific/magic version.
A partial fix to this issue is to use floatToIntBits to inspect the sign bit of the float. By dismissing the case where the two values have identical bit patterns and NaNs, we can do a cheap test of whether the sign bits differ where it doesn't matter whether x and y are 0.0 or not (in the following code this is ix_sign - iy_sign). This code removes one compare from the normal path as well as making 2 of the compares int rather than float comparisons:
public static int compare(float x, float y)
;
;
) return 1;
) return -1;
{ return x > y ? 1 : -1; }{
int ix = floatToIntBits
int iy = floatToIntBits
if (ix == iy) return 0;
if (isNaN
if (isNaN
int ix_sign = ix>>31;
int iy_sign = iy>>31;
if (ix_sign == iy_sign)
else
{ return ix_sign - iy_sign; }}
this code speeds up an optimizing compiler build on IA32 by a little under 8%. It slows a baseline compiler build because of the method call overhead. I will make and submit a Classpath patch for this and for the Double case. We're still not fully exploiting the fact that a comparison of x and y would give us NaN information on both of them. NaN's are the uncommon case but they take precedence here in order to maintain correct semantics