Plain old Java score calculation in Planner

Posted on 2012-04-09 09:37:00.0 by Geoffrey De Smet [ View original post ]

In Drools Planner 5.4.0.CR1, you can now define your score calculation in plain old Java too. In fact, it supports 3 alternative score calculations:

• Simple Java score calculator (new in 5.4)
• Incremental Java score calculator (new in 5.4)
• Drools DRL score calculator (the traditional way)

Unfortunately, each of these have advantages and disadvantages. Let's take a look at each of them.

Simple Java score calculator

This score calculator is very easy to implement. Just implement one method :
For example for NQueens:
It's that easy.

• Advantages
• No learning curve: it's plain old Java
• Can delegate score calculation to an existing codebase
• This is especially interesting when you're migrating from a legacy system and want to avoid a big bang conversion.
• Disadvantages
• Slow and less scalable, because it does not do incremental score calculation.

Incremental Java score calculator

This score calculator is very fast and scalable, but also very hard to implement, because you have to implement incremental score calculation yourself. You need to implement a bunch of methods on IncrementalScoreCalculator to make this happen. Here's a part of one NQueens implementation:
The implementation above isn't that good. Do you see how to optimize it? There's a much faster way to implement the NQueens score calculator, using Maps to avoid having to iterate through the insertedQueenList, but it makes the code even harder to understand.

• Advantages
• Very fast and scalable
• Currently the fastest if implemented correctly (see benchmarks below)
• Disadvantages
• Incremental (AKA delta) calculation is hard to write and to maintain
• You have to design and write all the performance optimizations yourself.

Drools DRL score calculation

This is the traditional and recommended way to implement score constraints, as Drools rules in DRL:
Notice the absence of incremental code, because Drools Expert does that for you automatically.

• Advantages
• Incremental score calculation without the boilerplate code for it
• Flexibility for your score rules:
• Define them in a decision table (XLS or Guvnor WebUI)
• Store your rules in the Guvor repository
• Translate them to natural language with DSL
• Explain the score of a solution:
• Just iterate over the ConstraintOccurrence instances to explain to the user why that score was the result.
• In every major and minor release, Drools Expert becomes faster. There are several notable features on the Drools Expert roadmap that will make the Drools Score Calculator much faster:
• More JITting
• Undo then
• Set based propagation
• Disadvantages:
• You need to learn and use DRL

Benchmark results

Because the score of a solution is always the same, no matter how it's calculated, the only notable measurement is the calculation speed relative to the problem size.

All benchmarks have be done with a warmup (to avoid JIT and DRL complication delays).

NQueens score calculation 

The results for 32, 64 and 256 queens:



Notice how the simple Java score calculator (red) does not scale at all. It starts out OK, but as the problem size gets bigger, it becomes very slow.

The drools calculator (in yellow - sorry that it's not very visible) starts slow on a trivial problem size, but scales up well. If we increase the number of queens even further, it will easily by-pass the basic incremental Java implementation. There's an well-known lesson to learn there: Don't let the performance results fool you into ignoring the scalability trend.

Notice the speed of the advanced incremental java score calculator (green), but don't forget that it's hard to write and to maintain the code behind it.

CloudBalance score calculation

This shows the results on 300, 600, 1200 and 2400 processes. The incremental Java score calculator also uses Maps extensively.

Notice that as the problem scales out, the Drools score calculator comes closer and closer to the hand-crafted incremental Java calculator.

Real problems

Both NQueens and CloudBalance are one of 4 toy examples, with only a few constraints. The 9 real examples have far more constraints (leaving more room for inter constraint optimization), so I suspect the benchmark results might be different there.

---