Sunday, October 26, 2008

Symmetrical and Asymmetrical Rete

In my endeavours to understand Clips I realised that it's Rete implementation was different to the more classical approach, as used by Drools 4. I haven't read anything in the past that attempted to give this difference a name, so I adopted the terminology of symmetrical Rete and asymmetrical Rete. It was really nice to see this decision validated by Gary Riley, the author of Clips, who used the terminology in his presentation on Rete enhancements in Clips at the Rules Fest in Texas.

Here is a quick explanation of the difference, without getting into the details on merit, in Drools 4 we use the classical approach of the retract being the same work as assert, except on the assert data is added to the memory on retract data is removed. By this I mean that the fact propagates through the network, for each join node the constraints are evaluated to determine the joins, the join is made and the fact plus the new join fact are propagated, each propagation into a new join node is added to the join node's memory. The retract is exactly the same, the constraints are re-evaluated to determine the previous joins so that the join and propagation can be remade, this time the facthandle and it's joined data are removed from the join node memory. With the work done for the attract and assert being the same I dubbed this symmetrical Rete.

In Drools 5 we adopted the Clips algorithm. Here the assert uses a lot of linked reference so that the propagation creates a chain of tokens. The retract can now iterate this chain of references removing data from the node memories, the joins do not need to be recalculated to determine which facts we joined against, we already know this as we have the references. As the work done for the retract is now different to the assert I dubbed this assymetrical Rete.

11 comments:

  1. Hi Mark.

    So, does this mean that Drools 5 has similar scalability performance as CLIPS 6.3 on, for example, the Ms Manners benchmark (see http://stage.illation.com.au/benchmarks/manners.2.html).

    ReplyDelete
  2. While the main matching algorithm is the same, Clips is still substantially faster and uses less memory. After talking to Gary at the conference, there are still some more tweaks I can make but it's minor. The rest of the code is due to Java really - cost of Objects and GC and lack of pointers. We might be able to improve further if we remove some of the OO approaches we make, not sure. I think the next main gain for us will be to compile the network down to bytecode methods, so it's no longer interpreted. I have a POC for this for alpha nodes, just need to get it working and also do beta nodes too. The bytecode stuff will be collapsed into a few methods with little indirection, so it'll show about as fast as we can get on Java, so we'll get a better idea of the cost. But Clips has Tuple/Token/PartialMatch (name depends on which system you use) recycling and very simple pointer referencing which I believe gives it a huge boost, plus it's Tuples are structs with stack allocation.

    Long story short, no :)

    ReplyDelete
  3. Hi again.

    I'm sorry I was so unclear. I understand that there's still a difference in speed. I was actually more wondering about the "shape" of the line in the diagram. Would Drools 5 still get the same "slope" between 64 and 128 guests or has that improved due to the algorithm changes?

    ReplyDelete
  4. Doh! We should have thought to ask Dr. Forgy how he would have named it. He mentioned in his talk that the rete algorithm had been designed with parallelism in mind, so perhaps there's a benefit to passing tokens for deletion in this regard. Ditto with what I've referred to as lazy computation of the not CE.

    ReplyDelete
  5. Johan: really don't know, will have to investigate another day, as we have to get 5.0 out for the moment.

    Gary: heh, good point. I'll send Charles an email to see if he approves, or has more suitable terminology he would like us to use.

    ReplyDelete
  6. Ok. I'll wait for the Illation guys to include Drools 5 in their benchmarks ;-)

    ReplyDelete
  7. I highly recommend Gary's and dr. forgy's presentation. Congrats to gary and CLIPS on the excellent performance.

    Correct me if I'm wrong, but drools 5 asymmetric was done independently of CLIPS 6.3. This is mostly an academic question, but isn't the design and implementation of asymmetric in drools 5 totally different than clips 6.3?

    Since CLIPS uses linked list to begin with, doing asymmetric retract "should" a minor change. Is that correct gary?

    ReplyDelete
  8. "done independently of CLIPS 6.3".

    Drools 3, the first full Rete Drools implementation, had a form of asymmetrical Rete which was written independently, as at the time I was not able to understand the Clips code. However I wasn't happy with the memory consumption so reverted Drools 4 to classical symmetrical Rete. Drools 5, with Gary's help, I was able to copy identically (at least I believe I did) how Clips manages it's data structures for the pattern matching process. Clips provided the missing technique that enabled me to do what I was trying to do with Drools 3.

    However I'm sure there is plenty here for you to draw your normal baseless and twisted conclusions with some fabricated information from the depths of your twisted mind and attack myself and the drools team - enjoy.

    ReplyDelete
  9. thanks for clarifying that. Gary mentioned he was playing around with ways to improve joins for 6.3. He is a generous person as well as a great guy in general. you deserve credit for getting that work in drools 5.

    ReplyDelete
  10. In CLIPS, retract prior to 6.3 was asymmetric in that join tests did not have to be performed, but the partial matches in the beta memories did need to be searched in order to find the ones referencing the partial match from the alpha memory currently being deleted. In 6.3, the partial matches have links to their children so it is no longer necessary to search the beta memories for the associated partial matches.

    ReplyDelete
  11. thanks for giving a great description of how it works in 6.3. My memory of RETE/UL paper is a bit foggy, but it sounds similar to what you have in 6.3.

    ReplyDelete