Drools 6.0 comes with the new Phreak algorithm (enabled by default), which is a drop-in replacement for the ReteOO algorithm (which you can still use instead too). The usage hasn't changed: it still executes the same DRL syntax. But it does open many doors for future optimizations, such as exploiting multi-core machines more efficiently (see Mark's article), etc.
That's all fine and dandy, but let's get to the point: How fast is the Phreak algorithm today? :)
Important note: Phreak is only at the beginning of its potential. The initial implementation was designed for correctness and with future multi-core exploitation in mind. For example many aspects have syncs added, ready for when multi-threading is added in the future. Nor has any profiling been done yet. After our first implementation, designed for correctness, our main hope was that no performance use cases would be slower than ReteOO. Which we seem to have achieved and more, now the fun begins with profiling and adding multi-thread support. Also other larger examples, or poorly written rule bases, should benefit further from the lazy algorithm; which should be more forgiving.
Feel free to rerun these benchmarks yourself (such as this one). Or run any of the other use cases I haven't had time to run.
Full report
That's all fine and dandy, but let's get to the point: How fast is the Phreak algorithm today? :)
Important note: Phreak is only at the beginning of its potential. The initial implementation was designed for correctness and with future multi-core exploitation in mind. For example many aspects have syncs added, ready for when multi-threading is added in the future. Nor has any profiling been done yet. After our first implementation, designed for correctness, our main hope was that no performance use cases would be slower than ReteOO. Which we seem to have achieved and more, now the fun begins with profiling and adding multi-thread support. Also other larger examples, or poorly written rule bases, should benefit further from the lazy algorithm; which should be more forgiving.
Methodology
I ran 4 use cases of OptaPlanner benchmarks over a total of 39 datasets. All of them use a stateful Drools session and run over 5 minutes each. Both variants use Drools 6.0 and use the exact same code and configuration. The only difference between the Phreak and the ReteOO variants is the RuleEngineOption flag (kieBaseConfiguration.setOption(RuleEngineOption.PHREAK/RETEOO).Feel free to rerun these benchmarks yourself (such as this one). Or run any of the other use cases I haven't had time to run.
Executive summary
Average per use case (over all datasets per use case):- Course scheduling: Phreak is 20% faster than ReteOO
- Exam scheduling: Phreak is 21% faster than ReteOO
- Hospital bed planning: Phreak is 4% slower than ReteOO (*)
- Nurse rostering: Phreak is 20% faster than ReteOO
Detailed summary
Course scheduling
Full reportExam scheduling
Full reportHospital bed planning
Full report
Nurse rostering
Full reportConclusion
Phreak is already faster and more scalable than ReteOO. And it's going to get even better. (And we need to take a deeper look at the hospital bed planning example.)
We had similar results with short ReteOO vs PHREAK algorithm test.
ReplyDeleteTest is executed using program that validates insurance agreements.
Test data: 85000 agreements. Total data amount in text format: 1.1GB. Total number of rules in use: 1102
Test environment: 2x Intel(R) Xeon(R) CPU X5550 @ 2.67GHz with 8GB of memory.
Validation times:
Drools 5.5.0-FINAL (ReteOO)
Three test runs, average time: 2h 53min 08s
Drools 6.1.0-SNAPSHOT (24.1.2014) (PHREAK)
Three test runs, average time: 2h 22min 31s
Phreak algorithm was on average 30min 37s faster than ReteOO.
In percentages PHREAK is 17% faster than ReteOO in this test.
Hello.
ReplyDeleteSince this is great post and I want to spread this out to Japanese users, I translated it into Japanese. This is the link for the translated article.
Japanese Translation(日本語訳)
http://playintegration.blogspot.jp/2014/01/reteoo-phreak.html
Please let me know if this is not allowed. Thx for the great post.
Best,
Hisao (@hfuruichi)
Thanks Hisao! :)
ReplyDeleteYour blog is awfully appealing. I am contented with your post. I regularly read your blog and its very helpful. If you are looking for the best Algorithm Interview Questions, then visit TutorialCup. Thanks! I enjoyed this blog post.
ReplyDelete