2009/4/29 Tim Ellison <t.p.elli...@gmail.com>: > 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
