2009/4/29 Tim Ellison :
> Ian Rogers wrote:
>> with recent discussion of performance an area that hits our [1]
>> performance is in sorting arrays of floats. The current Harmony code
>> that does this uses similar logic to Float.compareTo/compare. The
>> Harmony code first always explicitly tests for the uncommon NaN cases,
>> uses none raw bit conversion to an integer and what looks like an
>> expensive way to test for NaN, and that the raw integer values of -0.0
>> and 0.0 are ordered. Perhaps someone could optimize this code or tell
>> me if I would be able to submit a patch (having already looked at and
>> submitted a similar patch to GNU Classpath) ?
>
> While we could look for a way to make the code contribution work,
> perhaps you can describe the change first, and if it is easy enough for
> somebody to implement it in Harmony then that would remove any
> paper-shuffling nonsense.
>
> Regards,
> Tim
Ok, I wasn't sure if there was enough above to figure it out :-) The
methods that need changing are the Float and Double compare and
compareTo, and Arrays.lessThan for floats and doubles. The description
below is for Float.compare.
The 1st thing is that comparing floats for less-than or greater-than
won't return true if one of the values is NaN, so it's easy to
dispatch those most common cases first (and also avoid any float to
int conversions which are painful as you need to shuffle float
registers to integer ones and do NaN tests). Next doing a comparison
of raw int bits (avoiding a NaN test if using floatToIntBits) will
cover the case of equality without returning true for -0.0 and 0.0.
Following these 2 cases we either have values that are NaN or
0.0/-0.0. Float/Double isNaN has a fast test for NaN that uses a
single floating point compare, so both parameters need testing to see
if they are NaN and if they are a result created (the javadoc
specifies this). Finally we can recycle the raw int bit representation
and realize that we either have 0x80000000 or 0x00000000 for -0.0 and
0.0 (add more 0s for doubles). Therefore an integer comparison will
return their ordering (the current code in Float.compare uses this
trick).
Compared to the current code (in Float) and counting comparisons
(where the conversion of floatToIntBits requires an additional
floating-point comparison to detect NaN):
- If the 2 parameters are regular (ie not NaN) non-equal floating
point values - upto 2 floating point comparisons are necessary, the
current code needs 2 integer and 4 floating point comparisons
- If the 2 parameters are equal but not 0.0 and -0.0 - 2 floating
point comparisons and 1 integer comparison are necessary, the current
code needs 3 integer and 3 floating point comparisons
- If 1 or both of the parameters are NaN then - 4 floating point
comparisons and 1 integer comparison are necessary, the current code
needs 2 integer and 2 floating point comparisons (the current code is
probably faster but this case is unlikely)
- If the parameters are 0.0 and -0.0 then - 4 floating point
comparisons and 2 integer comparison are necessary, the current code
needs 3 integer and 4 floating point comparisons
The main thing is the common case where 2 integer and 2 floating point
comparisons are saved (and this is frequently executed code if sorting
an array). For equality then 1 floating point compare and 2 integer
compares are saved, or in the case of 0.0 and -0.0 (or vice versa) 1
integer comparison is saved. The code is probably slower when there
are NaNs, but I believe this case is uncommon.
Hope this helps,
Ian