Ian Rogers writes:
> Ian Rogers wrote:
> > public static int compare(float x, float y)
> > {
> > if (isNaN(x))
> > return isNaN(y) ? 0 : 1;
> > if (isNaN(y))
> > return -1;
> > // recall that 0.0 == -0.0, so we convert to infinities and try again
> > if (x == 0 && y == 0)
> > return (int) (1 / x - 1 / y);
> > if (x == y)
> > return 0;
> > return x > y ? 1 : -1;
> > }
> Below is a variant of the compare code and a comparison with the cost of
> the current compare code:
>
> public static int compare(float x, float y)
> {
> int ix = floatAsIntBits(x);
> int iy = floatAsIntBits(y);
> if (ix == iy) return 0;
> if (isNaN(x)) return 1;
> if (isNaN(y)) return -1;
> int ix_sign = ix>>31;
> int iy_sign = iy>>31;
> if (ix_sign == iy_sign) {
> return x > y ? 1 : -1;
> } else {
> return ix_sign - iy_sign;
> }
> }
>
> Case: x == y neither are NaN or 0.0
> New Cost: 2 float as ints, 1 int compare
> Old Cost: 5 float compares
>
> Case: x < y and different sign
> New Cost: 2 float as ints, 2 int compares, 2 float compares, 2 shifts,
> one subtract
> Old Cost: 6 float compares
>
> Case: x < y and same sign
> New Cost: 2 float as ints, 2 int compares, 3 float compares, 2 shifts
> Old Cost: 6 float compares
>
> Case: x is NaN
> New Cost: 2 float as ints, 1 int compare, 1 float compare
> Old Cost: 2 float compares
>
> Case: y is NaN
> New Cost: 2 float as ints, 1 int compare, 2 float compares
> Old Cost: 2 float compares
>
> Case: x == 0.0 and y == 0.0
> New Cost: either 2 float as ints, 1 int compare or 2 float as ints, 2
> int compares, 2 float compares, 2 shifts, one subtract
> Old Cost: 4 float compares, 2 float divides, 1 float subtract, 1 float
> to int
>
> The same code but for doubles would be:
>
> public static int compare(double x, double y)
> {
> long lx = doubleAsLongBits(x);
> long ly = doubleAsLongBits(y);
> if (lx == ly) return 0;
> if (isNaN(x)) return 1;
> if (isNaN(y)) return -1;
> int lx_sign = (int)(lx>>63);
> int ly_sign = (int)(ly>>63);
> if (lx_sign == ly_sign) {
> return x > y ? 1 : -1;
> } else {
> return lx_sign - ly_sign;
> }
> }
>
> So the case when y is a NaN is slower with the new code but I think all
> of the more common cases are similar or faster. Of course it depends on
> the speed of all the operations. If you cared about a CPU with no
> floating point, the new code is a lot faster. If you've got great
> floating point and a lot of cases of y being a NaN the old code will be
> better. My guess is that in the general case the new code wins out.
> There may be a bug I can't see in this code :-)
We know that any calculation involving NaN returns false, right? So,
simple cases can be done first without the (possibly expensive) move
out of the FPU:
if (x < y)
return -1;
if (x > y)
return 1;
then you can do the doubleToLongBits:
long lx = doubleAsLongBits(x);
long ly = doubleAsLongBits(y);
if (lx == ly)
return 0;
At this point we know they're unequal. Also, either one of them is
NaN, or one of them is -0 and the other +0. Java's doubleToLongBits
alwayse uses the canonical NaN, so we know that they can't both be
NaN.
if (lx < ly)
return -1;
return 1;
Andrew.
