Environment: Drools 6.5.0.Final
When testing drools performance comparing PHREAK vs ReteOO, I found that PHREAK Unlinking plays an important part.
First of all, it’s already explained in drools docs.
https://docs.jboss.org/drools/release/6.5.0.Final/drools-docs/html/ch05.html#PHREAK
But… I really can’t understand how things actually work. I need to test with actual examples.
https://github.com/tkobayas/phreak-unlinking
Firstly, I test this DRL:
https://github.com/tkobayas/phreak-unlinking/blob/master/src/main/resources/accumulate-all-link.drl
rule "Rule1" when $f1 : MyFact1() $f2 : MyFact2(id == $f1.id, value1 == $f1.value1, value2 == $f1.value2, value3 == $f1.value3, value4 == $f1.value4, value5 == $f1.value5) $f3 : MyFact3(id == $f2.id, value1 == $f2.value1, value2 == $f2.value2, value3 == $f2.value3, value4 == $f2.value4, value5 == $f2.value5) $f4 : MyFact4(id == $f3.id, value1 == $f3.value1, value2 == $f3.value2, value3 == $f3.value3, value4 == $f3.value4, value5 == $f3.value5) $var0 : Long(this != 0) from accumulate($a0 : MyFact5(id == $f4.id, value1 == $f4.value1), count( $a0 )) then end ...
with this client code. This inserts facts and only “Rule1” will be fired.
ReteDumper dumps Rete nodes so that we can understand how Nodes are connected.
Also make sure to enable TRACE logging for SegmentMemory and PathMemory.
https://github.com/tkobayas/phreak-unlinking/blob/master/src/main/resources/logback.xml#L11-L12
When I run SimpleMain1, the output is like this (omitting rete dump):
[SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=0 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5], [RuleMem Rule6], [RuleMem Rule7], [RuleMem Rule8], [RuleMem Rule9] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=0 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5], [RuleMem Rule6], [RuleMem Rule7], [RuleMem Rule8], [RuleMem Rule9] [PathMemory] LinkSegment smask=1 rmask=1 name=Rule1 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule2 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule3 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule4 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule5 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule6 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule7 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule8 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule9 [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule1 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule2 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule3 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule4 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule5 [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule6] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule7] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule8] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule9] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule1] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule1 [PathMemory] LinkRule name=Rule1 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule1, act#=0, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule2] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule2 [PathMemory] LinkRule name=Rule2 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule2, act#=1, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule3] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule3 [PathMemory] LinkRule name=Rule3 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule3, act#=2, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule4] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule4 [PathMemory] LinkRule name=Rule4 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule4, act#=3, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule5] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule5 [PathMemory] LinkRule name=Rule5 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule5, act#=4, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=1 rules=[RuleMem Rule6] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule6 [PathMemory] LinkRule name=Rule6 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule6, act#=5, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=1 rules=[RuleMem Rule7] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule7 [PathMemory] LinkRule name=Rule7 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule7, act#=6, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=1 rules=[RuleMem Rule8] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule8 [PathMemory] LinkRule name=Rule8 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule8, act#=7, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=1 rules=[RuleMem Rule9] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule9 [PathMemory] LinkRule name=Rule9 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule9, act#=8, salience=0, tuple=null] ... ---- number of fired rules = 1
I see all 9 rules are “Linked” even though only Rule1 is fired. Why?
When I set a breakpoint at SegmentMemory.linkNode(), I see that JoinNode calls linkNode() regardless of its constraints with other facts. AccumulateNode is also linked (explained in the docs). In other words, these kinds of rules don’t provide the information “this rule doesn’t need further evaluation” for PHREAK.
If I run benchmark (DroolsBenchmark1) with the rules, I get the result. (Make sure to disable the TRACE logging)
$ mvn clean install $ java -Xmx2G -jar target/drools-benchmarks.jar -wi 500 -i 500 -f 2 .... Benchmark (engine) Mode Cnt Score Error Units DroolsBenchmark1.test phreak ss 1000 25831.879 ± 441.840 us/op DroolsBenchmark1.test reteoo ss 1000 18049.810 ± 304.243 us/op
PHREAK was slower than ReteOO because PHREAK couldn’t get an advantage of unlinking (and it has some overhead).
Then I try another example.
https://github.com/tkobayas/phreak-unlinking/blob/master/src/main/resources/accumulate-unlink.drl
rule "Rule1" when $f1 : MyFact1() $f2 : MyFact2(id == $f1.id, value1 == "hoge1", value2 == $f1.value2, value3 == $f1.value3, value4 == $f1.value4, value5 == $f1.value5) $f3 : MyFact3(id == $f2.id, value1 == "hoge1", value2 == $f2.value2, value3 == $f2.value3, value4 == $f2.value4, value5 == $f2.value5) $f4 : MyFact4(id == $f3.id, value1 == "hoge1", value2 == $f3.value2, value3 == $f3.value3, value4 == $f3.value4, value5 == $f3.value5) $var0 : Long(this != 0) from accumulate($a0 : MyFact5(id == $f4.id, value1 == $f4.value1), count( $a0 )) then end ...
These rules use literal constraints (AlphaNode) for value1.
[SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=0 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5], [RuleMem Rule6], [RuleMem Rule7], [RuleMem Rule8], [RuleMem Rule9] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=0 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5], [RuleMem Rule6], [RuleMem Rule7], [RuleMem Rule8], [RuleMem Rule9] [PathMemory] LinkSegment smask=1 rmask=1 name=Rule1 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule2 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule3 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule4 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule5 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule6 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule7 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule8 [PathMemory] LinkSegment smask=1 rmask=1 name=Rule9 [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=1 rules=[RuleMem Rule1], [RuleMem Rule2], [RuleMem Rule3], [RuleMem Rule4], [RuleMem Rule5] [PathMemory] LinkSegment smask=2 rmask=3 name=Rule1 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule2 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule3 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule4 [PathMemory] LinkSegment smask=2 rmask=3 name=Rule5 [SegmentMemory] LinkNode notify=true nmask=1 smask=1 spos=2 rules=[RuleMem Rule1] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule1 [PathMemory] LinkRule name=Rule1 [PathMemory] Queue RuleAgendaItem [Activation rule=Rule1, act#=0, salience=0, tuple=null] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=1 rules=[RuleMem Rule6] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=1 rules=[RuleMem Rule7] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=1 rules=[RuleMem Rule8] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=1 rules=[RuleMem Rule9] [SegmentMemory] LinkNode notify=true nmask=2 smask=3 spos=2 rules=[RuleMem Rule1] [PathMemory] LinkSegment smask=4 rmask=7 name=Rule1 [PathMemory] LinkRule name=Rule1 [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=2 rules=[RuleMem Rule2] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=2 rules=[RuleMem Rule3] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=2 rules=[RuleMem Rule4] [SegmentMemory] LinkNode notify=true nmask=2 smask=2 spos=2 rules=[RuleMem Rule5] [SegmentMemory] LinkNode notify=true nmask=4 smask=6 spos=1 rules=[RuleMem Rule6] [SegmentMemory] LinkNode notify=true nmask=4 smask=6 spos=1 rules=[RuleMem Rule7] [SegmentMemory] LinkNode notify=true nmask=4 smask=6 spos=1 rules=[RuleMem Rule8] [SegmentMemory] LinkNode notify=true nmask=4 smask=6 spos=1 rules=[RuleMem Rule9] ---- number of fired rules = 1
Good! Only Rule1 is linked.
How about the performance?
Benchmark (engine) Mode Cnt Score Error Units DroolsBenchmark2.test phreak ss 1000 11104.462 ± 179.234 us/op DroolsBenchmark2.test reteoo ss 1000 15623.972 ± 274.120 us/op
Big improvement in PHREAK 🙂
Unlinking allows engine to avoid unnecessary evaluations. So the ratio <# of linked rules>/<# of total rules> is important. Smaller is better.
So next, I tested 100 rules with 1/100 ratio (= 1 rule is linked out of 100 rules).
Benchmark (engine) Mode Cnt Score Error Units DroolsBenchmark3.test phreak ss 1000 21900.129 ± 286.363 us/op DroolsBenchmark3.test reteoo ss 1000 51405.577 ± 471.153 us/op
The advantage gets larger.
Wrap-up:
The tested rules are more or less artificial. But in real business use cases, rules tend to use literal constraints and the number of rules are large. So generally it will get the advantage of unlinking. Rather, we have to be careful when we write small benchmark rules which miss the advantage of unlinking.
Learn from stack traces 
Thanks for sharing the information. It is very helpful.