5

I have a situation where performance is extremely important. At the core of my algorithm there is a method that does some basic calculations with two double primitives. This method is called over ten million times per run of the algorithm.

The code looks something like this;

public int compare(double xA, double xB, double yA, double yB);

    double x = xA * xB;
    double y = yA * yB;

    double diff = x - y;

    return (diff < 0.0 ? -1 : (diff > 0.0 ? 1 : 0));

}

The parameters xA and yA take their values from a set. This set can be tweaked in the code. I am seeing huge (approximately double) performance differences depending on the values I put into the set. It seems that if the set contains a 0.1 or a 0.3, the performance takes a big hit. Keeping the set to just multiples of 0.5 gives the best performance.

Is the compiler optimising x * 0.5 as x >> 1 etc? Or is this because 0.1 cannot be defined in binary?

I'd like to understand this situation a bit better so that I can optimise this. I guess it might be quite a hard problem unless someone knows exactly how javac and the jvm (in our case hotspot) handles double multiplication.

Javier
  • 678
  • 5
  • 17
lynks
  • 5,599
  • 6
  • 23
  • 42
  • Are you sure the performance difference is directly in this routine and not a consequence of changing xA and yA causing different results to be returned, thus changing what is executed after this routine returns? – Eric Postpischil Aug 01 '12 at 18:54
  • You can eliminate the subtraction by deleting that line and replacing the return with `return xy ? 1 : 0;`. – Eric Postpischil Aug 01 '12 at 18:57
  • If the available tweaking extends to the point that values p and q for xA and yA can be replaced by p/q and 1, then a multiplication can be eliminated, leaving `double x = xA * xB; double y = yB;` (subject to the usual floating-point rounding issues). – Eric Postpischil Aug 01 '12 at 18:59
  • no problem. i have moved the system over to integers. the whole thing is a heuristic for comparing path costs in a graph, the original idea was to have 0.0 as 'no-distance' and 1.0 as 'infinite distance', but due to a need to cache sub-path lengths, we had to move over to a more simple, additive heuristic. hence the floating-point values were no longer necessary. the question still stands however. – lynks Aug 02 '12 at 09:44

1 Answers1

1

Just a couple few ideas:

  • If values are multiple of 0.5, then there will be few significant bits in the mantissa,so it seems feasible that multiplication takes fewer cicles. Actually significant bits for multiplication doesn't seem to be an issue, since modern processors will take just two cycles for double (as explained in Floating point division vs floating point multiplication).

    E.g. I figure that with 0.5 , 1 , 2, 4 , etc the mantissa will be all zeroes (first "1" is ommited for being implicit). For .75, 1.5, 3 etc, it will be a "1" in the m.s.b. followed by all zeroes. Whereas 0.1 would use all the significand precission to be represented, and even then have an small error.

  • About the result returned: Is there any problem with Math.signum()?. I mean, maybe this would do the same:

    return Math.signum(x-y);

  • If precission is not paramount, you might consider using single precission (float). (though if that means you are going to be converting back and forth from double, then it may not be worth it).

Community
  • 1
  • 1
Javier
  • 678
  • 5
  • 17
  • 1
    Yep signum would work, but would mean a cast to int for the return, for that reason I avoided it. – lynks Aug 01 '12 at 12:21