Critical loop containing many “if” whose output is constant : How to save on condition tests ? For Java ;)

Question

I just read this thread Critical loop containing many "if" whose output is constant : How to save on condition tests?

and this one Constant embedded for loop condition optimization in C++ with gcc which are exactly what I would like to do in Java.

I have some if conditions called many times, the conditions are composed of attributes define at initialization and which won't change.

Will the Javac optimize the bytecode by removing the unused branches of the conditions avoiding to spend time testing them? Do I have to define the attributes as final or is it useless?

Thanks for you help,

Aurélien

Andrew White · Answer 1 · 2011-04-05T14:47:18.090

2

Java compile time optimization is pretty lacking. If you can use a switch statement it can probably do some trivial optimizations. If the number of attributes is very large then a HashMap is going to be your best bet.

I'll close by saying that this sort of thing is very very rarely a bottleneck and trying to prematurely optimize it is counterproductive. If your code is, in fact, called a lot then the JIT optimizer will do its best to make your code run faster. Just say what you want to happen and only worry about the "how" when you find that's actually worth the time to optimize it.

edited Apr 05 '11 at 14:47

answered Apr 05 '11 at 14:35

Andrew White

52,720
19
113
137

3

@Andrew could you cite some sources on how the "Java compile time optimization is pretty lacking?" Even if it was (which it's not) I've run tests which outperform gcc compiled code thanks to the JIT. – corsiKa Apr 05 '11 at 14:39
Source is experience; I've worked a lot with Java's compiler and byte code output. This answer seems to agree with my finding (http://stackoverflow.com/questions/2391219/java-compiler-optimization/2391293#2391293) – Andrew White Apr 05 '11 at 14:44
Fair enough, but I'd say my experience has proven the opposite. The plural of "anecdote" isn't data, but I'd have to see the exact condition that was failing to say whether the output could be optimized or not, and how. – Joseph Ottinger Apr 05 '11 at 14:50
Hmm, I wish the downvoter would comment. Unless it was you, glowcoder, in which case I hope my reply explained my position. – Andrew White Apr 05 '11 at 14:51
@Joseph: you've seen javac do non trivial *compile* time optimizations? It would be interested know the context. Or I guess an interesting counter argument would be for someone to provide a source that states that javac *does* compile time optimizations. – Andrew White Apr 05 '11 at 14:54
Arrrrgh! You know, I'm an idiot - I've been looking at the runtime optimization, not the compile-time optimization. I corrected "javac" to "java" without even thinking about it, because at *runtime* the optimization is pretty darn good - compile-time is meh, because simpler code is easier to optimize at runtime. – Joseph Ottinger Apr 05 '11 at 15:10
@Andrew nope it wasn't me :) And it looks like whoever did removed it. (You'll note by my profile I'm not much of a downvoter :-)) For that matter, I agree with virtually all of your post. I'm simply curious as to how you arrived at the conclusion of a lacking compiler. – corsiKa Apr 05 '11 at 15:30

score 0 · Answer 2 · answered Apr 05 '11 at 14:36

In OO languages, the solution is to use delegation or the command pattern instead of if/else forests.

So your attributes need to implement a common interface like IAttribute which has a method run() (or make all attributes implement Runnable).

Now you can simply call the method without any decisions in the loop:

for(....) {
    attr.run();
}

It's a bit more complex if you can't add methods to your attributes. My solution in this case is using enums and an EnumMap which contains the runnables. Access to an EnumMap is almost like an array access (i.e. O(1)).

for(....) {
    map.get(attr).run();
}

score 0 · Answer 3 · answered Apr 05 '11 at 14:37

I don't know about Java specifics regarding this, but you might want to look into a technique called Memoization which would allow you to look up results for a function in a table instead of calling the function. Effectively, memoization makes your program "remember" results of a function for a given input.

score 0 · Answer 4 · answered Apr 05 '11 at 14:39

Try replacing the if with runtime polymorphism. No, that's not as strange as you think.

If, for example you have this:

for (int i=0; i < BIG_NUMBER; i++) {
  if (calculateSomeCondition()) {
    frobnicate(someValue);
  } else {
    defrobnicate(someValue);
  }
}

then replace it with this (Function taken from Guava, but can be replaced with any other fitting interface):

Function<X> f;
if (calculateSomeCondition()) {
  f = new Frobnicator();
else {
  f = new Defrobnicator();
}

for int (i=0; i < BIG_NUMBER; i++) {
  f.apply(someValue);
}

Method calls are pretty highly optimized on most modern JVMs even (or especially) if there are only a few possible call targets.

Critical loop containing many “if” whose output is constant : How to save on condition tests ? For Java ;)

4 Answers4