A closer look at Ruleby and Ms Manners
I've spent some time trying to understand the inner workings of Ruleby and in particular what happens when Ms Manners is run. On the Benchmarks page, they've written:
For Ruleby, this benchmark ran well for 16 guests. However, as the number of guests increases to 32 and 64, the relative performance of the benchmark drops off. This is due to a hack/bug in the implementation of the Rete algorithm. This problem is described on the Open Issues page under the heading ‘Iterating over Working Memory.’
But, I can't really understand the issue described on the Open Issues page. And I'm not sure that it's related to why Ms Manners' performance degrades when adding more guests. I have skimmed the code previously and I noticed that the match method is recursive and I'm guessing that's most likely where the problem is.
If we open up engine.rb and look at the Engine class' match method it looks like this. The comments are mine.
| def match(agenda=@root.match, used_agenda=[], activation_counter=0)Also, if you look at the memory usage during execution you'll notice that it climbs steadily until the program exits. All those Activations are kept in memory until the method exits, even though they'll never be used and most of them are duplicates anyway.
| agenda = @conflict_resolver.resolve agenda
| if(agenda && agenda.length > 0)
| activation = agenda.pop
| used_agenda.push activation
| activation.fire self
|
| new_agenda = @root.match # <-- Conflict Set?!
|
| # HACK the following is a workaround. This problem would best be
| # solved by working this into the nodes themselves.
| new_agenda.each do |a|
| used = false
| used_agenda.each do |used_activation|
| used = true if used_activation.object_id == a.object_id
| end
|
| # BUG we are comparing against the current agenda, but we may need to
| # compare against all activations that have existed...
| if (agenda.index(a) == nil) && (!used)
| a.counter = activation_counter+1
| agenda.push a
| end
| end
| agenda.delete_if {|a| new_agenda.index(a) == nil}
|
| match(agenda, used_agenda, activation_counter+1) # <-- This is what
| # slows it down!
| end
| end
Unfortunately I have no patch to submit for this issue but I'm sure Joe and Matt won't find it too hard to fix. But it will probably require some re-thinking of the current engine.match design.
[2007-05-10] Update: It turns out I was as wrong as I could be. Joe rewrote the engine.match method in a non-recursive way and it made NO difference at all. Bummer! But, only slightly annoyed I'm going to continue looking for why Manners behaves as it does. Even though I'm probably not the best man for the job I doubt I'll ever get a better opportunity to finally learn some Ruby.
Labels:
Rete Algorithm,
Rule Engine,
Ruleby
3 kommentarer:
If it really is doing matching recursively, that would be incorrect and not RETE. By doing it recursively, the engine would have to do far more work and therefore negate the benefit of the discrimination network. think of it this way.
normal RETE execution, the facts propogate down the network until it fails to match a condition. At that point, it stops propogating. By matching recursively, it essentially becomes sequential evaluation. It's an easy mistake to make, especially if someone is implementing RETE for the first time.
I don't think they're actually performing the Fact/Rule matching recursively.
The Engine.match method is called after all Facts have passed through the Rete Network. The call to @root.match creates a Conflict Set (new_agenda) and that is done by visiting all Terminal nodes and aggregating all Activations in an array. So all Fact/Rule-matching has already been done at that point.
But they are doing the bulk of the "run" method recursively.
When "run" is called they select 1 Activation, fire it and store it in an array called used_agenda. Then they call @root.match again and compare the result (new_agenda) to the used_agenda. If an Activation exists in both it is removed from the Conflict Set. Once they've gone through all Activations in the new_agenda, removing all that have already been triggered they (and here's the problem!) call the Engine.match method *recursively* using the filtered Conflict Set (new_agenda) as the new Agenda.
I believe that they're getting such poor results because the deeper they go into the recursion, the more "junk" the Ruby interpreter has to hold on to. There's an agenda, a new_agenda and a used_agenda for each call!
If they can rewrite it non-recursively it will probably become significantly faster but it will require a new design of their "Execution engine".
that seems quite a few extra cycles. makes me wonder why they chose that design. when I looked at the code, I couldn't tell if they are doing joins arbitrarily, or in the sequence the conditional elements are defined in the rule. another potential reason for the drop in performance is arbitrary joins, but i couldn't tell from the code.
Skicka en kommentar