Optimisation: Eliminate long if()-else() chains where possible

Description

Having been working through the core code a bit recently, I've noticed that there is quite a bit of it that uses long chains of simple if-else statements. Here is an example from org.compiere.util.DisplayType:

This would be much more efficient if implemented using a switch() statement, eg:

Not only is the latter a bit more readable and less verbose, it also yields a performance improvement because the selection is O( 1 ) instead of O( n ) (n being the number of conditions being tested). In a core class like DisplayType, which is called often, this could yield a performance boost.

The potential performance boost is even greater if one considers selections based on string values. From Java 7, strings can be used in a switch() statement (see Oracle specs) . The Java compiler can generally optimise these more efficiently using something like a hashtable implementation or a trie, which turns the O( mn ) (m = length of strings, n = number of conditions) into something closer to an O( m ) operation. If we need Java 6 compatibility (though surely it's time to move on?), we could achieve a similar result using a static HashMap<String,Runnable> (though it is still less readable):

A further advantage of the hashmap implementation is that you can use it with any type of object that correctly implements the hashCode() and equals() methods.

This kind of optimisation could potentially have a large payoff in code like DisplayType, which is called frequently.

Making this change through the entire codebase would be a time consuming exercise, so I propose something like the following:

  • Try to look for this in any new code/change proposals for trunk and get the contributors to fix them before merging.

  • Identify any frequently-called core classes like DisplayType where this pattern appears, and prioritise optimising those cases first. Probably worthwhile ensuring that they have unit tests first so as not to inadvertantly break anything while making the change.

  • Fix any remaining instances as the opportunity arises.

Thoughts?

Environment

None

Activity

Show:

Carlos Ruiz May 10, 2018 at 9:10 AM

Hi ,

Adapted the QuickTest to getDescription, same results, the if version is faster than the switch version. This time the difference is even bigger.

Jeremy Krieg May 10, 2018 at 8:42 AM

Hi @Carlos Ruiz,

You're right - I picked a bad example that uses a single if with a long chained OR, instead of a long chained if-else. DisplayText.getDescription() would have been a better example:

I suspect that this might benefit from optimisation. getSQLDataType() is another candidate.

Carlos Ruiz May 10, 2018 at 8:27 AM

Hi ,

We don't need compatibility with java6 - the actual compatibility requirement is with java8. That code is old from Compiere times, java5 or earlier I think.

I read an interesting explanation about what you proposed:
https://stackoverflow.com/questions/6705955/why-switch-is-faster-than-if

However I got curious with the second answer there:

A switch statement is not always faster than an if statement. It scales better than a long list of if-else statements as switch can perform a lookup based on all the values. However, for a short condition it won't be any faster and could be slower

In the case of DisplayType.isText, there is not a chained if-then-else conditions, but chained OR conditions - from what I read also the JVM optimizer does a good work on those OR chains trying to order first the most used values.

So, to solve doubts I made a QuickTest.java program (attached).
The QuickTest calls the isText method 9 billion times (1M times an array with the first 9.000 values of the ad_column.ad_reference_id).
In my tests the chained OR version was faster than the switch version consistently.

Cannot Reproduce

Details

Assignee

Reporter

Original estimate

Time tracking

No time logged1w remaining

Components

Affects versions

Priority

Created May 10, 2018 at 6:44 AM
Updated July 2, 2018 at 11:41 AM
Resolved May 15, 2018 at 10:00 AM