views:

166

answers:

4

I recently profiled some code using JVisualVM, and found that one particular method was taking up a lot of execution time, both from being called often and from having a slow execution time. The method is made up of a large block of if statements, like so: (in the actual method there are about 30 of these)

    EcState c = candidate;

    if (waypoints.size() > 0)
    {
        EcState state = defaultDestination();
        for (EcState s : waypoints)
        {
            state.union(s);
        }
        state.union(this);
        return state.isSatisfied(candidate);
    }

    if (c.var1 < var1)
        return false;
    if (c.var2 < var2)
        return false;
    if (c.var3 < var3)
        return false;
    if (c.var4 < var4)
        return false;
    if ((!c.var5) & var5)
        return false;
    if ((!c.var6) & var6)
        return false;
    if ((!c.var7) & var7)
        return false;
    if ((!c.var8) & var8)
        return false;
    if ((!c.var9) & var9)
        return false;

    return true;

Is there a better way to write these if statements, or should I look elsewhere to improve efficiency?

EDIT: The program uses evolutionary science to develop paths to a given outcome. Specifically, build orders for Starcraft II. This method checks to see if a particular evolution satisfies the conditions of the given outcome.

+4  A: 

First, you are using & instead of &&, so you're not taking advantage of short circuit evaluation. That is, the & operator is going to require that both conditions of both sides of the & be evaluated. If you are truly doing a bitwise AND operation, then this wouldn't apply, but if not, see below.

Assuming you return true if the conditions aren't met, you could rewrite it like this (I changed & to &&).

return 
     !(c.var1 < var1 ||
       c.var2 < var2 ||
       c.var3 < var3 ||
       c.var4 < var4 ||
      ((!c.var5) && var5) ||
      ((!c.var6) && var6) ||
      ((!c.var7) && var7) ||
      ((!c.var8) && var8) ||
      ((!c.var9) && var9));

Secondly, you want to try to move the conditions that will most likely be true to the top of the expression chain, that way, it saves evaluating the remaining expressions. For example, if c1.var4 < var4 is likely to be true 99% of the time, you could move that to the top.

Short of that, it seems a bit odd that you'd be getting a major amount of time spent in this method, unless these conditions are hitting a database or something like that.

dcp
Not equivalent unless the next line in the original code was `return true`.
Thilo
@Thilo - Great point, I edited my answer.
dcp
`||` short circuits when the first condition is `true` not `false`. Thus, if you care, you should move the conditions most likely to be `true` to the top. Also, as a micro optimization, you generally shouldn't care.
ILMTitan
@ILMTitan - Fair enough, I changed my answer to use true instead of false.
dcp
+1  A: 

You aren't going to find too many ways to actually speed that up. The two main ones would be taking advantage of short-circuit evaluation, as has already been said, by switching & to &&, and also making sure that the order of the conditions is efficient. For example, if there's one condition that throws away 90% of the possibilities, put that one condition first in the method.

John Calsbeek
+2  A: 

First, try rewriting the sequence of if statements into one statement (per @dcp's answer).

If that doesn't make much difference, then the bottleneck might be the waypoints code. Some possibilities are:

  • You are using some collection type for which waypoints.size() is expensive.
  • waypoints.size() is a large number
  • defaultDestination() is expensive
  • state.union(...) is expensive
  • state.isSatisfied(...) is expensive

One quick-and-dirty way to investigate this is to move all of that code into a separate method and see if the profiler tells you it is a bottleneck.

If that's not the problem then your problem is intractable, and the only way around it would be to find some clever way to avoid having to do so many tests.

  • Rearranging the test order might help, if there is an order that is likely to return false more quickly.
  • If there is a significant chance that this and c are the same object, then an initial test of this == c may help.
  • If all of your EcState objects are compared repeatedly and they are immutable, then you could potentially implement hashCode to cache its return value, and use hashCode to speed up the equality testing. (This is a long shot ... lots of things have to be "right" for this to help.)
  • Maybe you could use hashCode equality as a proxy for equality ...
Stephen C
Thanks for the tips! It turns out the `waypoints` code was the expensive part of the method. I moved the `waypoints` code segment to after the `if` statements and was rewarded with about a 5% decrease in CPU time for the method.
DerekG
@DerekG: You understand that this moved changed the program logic, right? If, for instance, for a particular EcState, the waypoints logic would return true but the first if statement returned false, your change would now be returning false where it formerly returned true. It's faster - but is it right?
Carl Manaster
+2  A: 

As always, the best thing to do is measure it yourself. You can instrument this code with calls to System.nanotime() to get very fine-grained durations. Get the starting time, and then compute how long various big chunks of your method actually take. Take the chunk that's the slowest and then put more nanotime() calls in it. Let us know what you find, too, that will be helpful to other folks reading your question.

So here's my seat of the pants guess ...

Optimizing the if statements will have nearly no measurable effect: these comparisons are all quite fast.

So let's assume the problem is in here:

if (waypoints.size() > 0)
{
    EcState state = defaultDestination();
    for (EcState s : waypoints)
    {
        state.union(s);
    }
    state.union(this);
    return state.isSatisfied(candidate);
}

I'm guessing waypoints is a List and that you haven't overridden the size() method. In this case, List.size() is just accessing an instance variable. So don't worry about the if statement.

The for statement iterates over your List's elements quite quickly, so the for itself isn't it, though the problem could well be the code it executes. Assignments and returns take no time.

This leaves the following potential hot spots:

  • The one call to defaultDestination().
  • All the calls to EcState.union().
  • The one call to EcState.isSatisfied().

I'd be willing to bet your hotspot is in union(), especially since it's building up some sort of larger and larger collection of waypoints.

Measure with nanotime() first though.

Jim Ferrans