Ruleby's matching algorithm
I've been looking at Ruleby these last few days and especially how the Miss Manners benchmark executes.
I find Ruleby particularly interesting because Ruby and Python are somewhat similar and I'm hoping to get some good ideas for my pyRete implementation. I haven't got pyRete into the state where it's ready to run Miss Manners yet and I'm trying to figure out how much more I need to do. I'm really hoping that this little detour into Ruby-land will prove fruitful.
Anyway, the matching in Ruleby seems to e working a bit differently than I expected. I'm hoping that Joe or Matt can explain what's happening. Below is part of a call trace of Miss Manners with 4 guests:
--#RootNode:01.assert_fact [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]I've rewritten the Object References from the trace in order to distinguish them easier.
--#ObjectNode:02.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:02.build_results
--#ObjectNode:02.resolve #MatchResult(f)(24308940)()#MatchResult(24308870)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:02.propagate_assert #MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )[Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#JoinNode:02.assert #ObjectNode:02#MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )[Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#JoinNode:02.filter_match_results #MatchResult(24308610)(guest=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#RootNode:01.check_references #ObjectNode:02
--#ObjectNode:07.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:07.build_results
--#ObjectNode:07.resolve #MatchResult(f)(24306540)()#MatchResult(24306470)(rg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:08.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:08.build_results
--#ObjectNode:08.resolve #MatchResult(f)(24305450)()#MatchResult(24305380)(lg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )
--#ObjectNode:08.build_results
--#ObjectNode:08.resolve #MatchResult(24305120)(lg=[Guest name=n4, sex=m, hobbies=h1]/24355540, )#MatchResult(24305190)(leftGuestName=n4/24355540, )
--#RootNode:01.assert_fact [Fact |9|[LastSeat seat=4]]
--#ObjectNode:15.assert [Fact |9|[LastSeat seat=4]]
--#ObjectNode:15.build_results
--#ObjectNode:15.resolve #MatchResult(f)(24303590)()#MatchResult(24303520)(ls=[LastSeat seat=4]/24355530, )
--#ObjectNode:15.build_results
--#ObjectNode:15.resolve #MatchResult(24303260)(ls=[LastSeat seat=4]/24355530, )#MatchResult(24303330)(lastSeat=4/24355530, )
--#ObjectNode:15.propagate_assert #MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )[Fact |9|[LastSeat seat=4]]
--#JoinNode:14.assert #ObjectNode:15#MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )[Fact |9|[LastSeat seat=4]]
--#JoinNode:14.filter_match_results #MatchResult(24302480)(ls=[LastSeat seat=4]/24355530, lastSeat=4/24355530, )
--#RootNode:01.check_references #ObjectNode:15
--#RootNode:01.compare_node_to_wm #ObjectNode:16
--#ObjectNode:16.assert [Fact |0|[Guest name=n1, sex=f, hobbies=h3]]
--#ObjectNode:16.assert [Fact |1|[Guest name=n1, sex=f, hobbies=h1]]
--#ObjectNode:16.assert [Fact |2|[Guest name=n1, sex=f, hobbies=h2]]
--#ObjectNode:16.assert [Fact |3|[Guest name=n2, sex=f, hobbies=h3]]
--#ObjectNode:16.assert [Fact |4|[Guest name=n2, sex=f, hobbies=h2]]
--#ObjectNode:16.assert [Fact |5|[Guest name=n3, sex=m, hobbies=h1]]
--#ObjectNode:16.assert [Fact |6|[Guest name=n3, sex=m, hobbies=h3]]
--#ObjectNode:16.assert [Fact |7|[Guest name=n4, sex=m, hobbies=h2]]
--#ObjectNode:16.assert [Fact |8|[Guest name=n4, sex=m, hobbies=h1]]
--#ObjectNode:16.assert [Fact |9|[LastSeat seat=4]]
The blue line is where the last guest data is asserted. It propagates into three different ObjectNodes so there's probably no sharing between rules. But why is the same fact asserted again (into ObjectNode:16) when the LastSeat fact is asserted?
It seems Peter was right about the matching and this might well be the reason Ruleby gets such weird performance on Miss Manners. Unfortunately I don't know enough Ruby to re-write the implementation but I really hope that Joe and/or Matt will be able to.
I'll stop this dissecting of their engine now and start working on pyRete again.
Labels:
Rete Algorithm,
Rule Engine,
Ruleby
3 kommentarer:
that definitely looks odd. something in their implementation isn't right, for that to happen.
Yes, apparently they "pull" in Facts as needed instead of "pushing" them into each Node when asserted. I'm sure there's a reason for this but since I'm not as familiar with Ruleby as I'd like to be I cannot value or verify the decision.
I'm hoping they can fix the Miss Manners problem though. I'd like to prototype an application using Ruleby on JRuby.
ok, that makes sense then. they're on their way to re-inventing LEAPS. All they have to do is remove the agenda, order the rules by the number of conditions and get their node memories correct.
using a pull approach, they have to execute the rules in the correct order, otherwise it ends up being horribly inefficient. That's one of the major downside of leaps. if the rules aren't ordered correctly, it ends up being an order of magnitude slower. or if the application needs to calculate cross product like a trading system, leaps ends up being much much slower.
Skicka en kommentar