Friday, May 31, 2013

Stress testing the Phreak algorithm

Some time ago, Mark blogged about his new rule engine algorithm. This new algorithm, an alternative to RETE, has been named Phreak. It's a drop-in replacement deep inside Drools, so from a user's perspective, nothing changes in your Drools related code.

Such a new algorithm is a big change, so regression testing is critical. Luckily we have a battery of tests.

Drools's tests

First up were the 3305 tests in Drools itself. A large portion of these tests are small DRL integration tests which insert/modify/remove a few facts and call fireAllRules() a few times.

Mark's initial Phreak implementation passed all these tests a few weeks ago. Given the test coverage size and the complexity of some of these tests, one would think this enough to label Phreak as production ready. Luckily, we test more.

OptaPlanner's stress tests

Next up, are OptaPlanner's stress tests. These tests solve an OptaPlanner example, while continuously modifying a fact and calling fireAllRules() on a single stateful Drools session. They also continuously assert the incremental results of the stateful Drools session with a fresh Drools session. Any bug in the fast incremental delta's of a stateful session quickly distorts the results slightly and fails the assertions.

Each test of the most notorious of these tests - named the TurtleTests - call fireAllRules() about 5000 times per second for a duration of 10 minutes on a dataset of thousands of facts. There are 153 TurtleTests, each using a separate dataset, across 11 realistic use cases. This results in pounding the Drools rule engine for over 25 hours by calling over 459 million times fireAllRules().

Yes, we did find issues :) About 20 of them... and they were infamously complex too. But Mario, Mark and I have isolated and fixed each one for 6.0.0.Beta3. Except one exotic bug, which will be fixed for 6.0.0.Beta4.

Try Phreak yourself

To use Phreak instead of RETE for yourself in 6.0.0.Beta3, enable it like this in Drools:

KieBaseConfiguration conf
    = KnowledgeBaseFactory.newKnowledgeBaseConfiguration();
KieBase kieBase = kieContainer.newKieBase(conf);

In OptaPlanner 6.0.0.Beta3, configure it in the *SolverConfig.xml like this instead:




Phreak is considerably faster than RETE. Stay tuned for the benchmark reports...