Chapter 10. Papers - JBoss RULES 4.0.0.11754MR2 manual 英文版使用指南文档

5 benchmarks were established in the 1991 paper "Effects of Database Size on Rule System Performance: Five Case Studies" by Brant, Timothy Grose, Bernie Lofaso, & Daniel P. Miranker.

Manners has become the de facto rule engine benchmark; however it's behaviour is now well known and many engines optimise for this thus negating its usefulness as a benchmark which is why Waltz is becoming more favourable. These 5 benchmarks are also published at the University of Texas http://www.cs.utexas.edu/ftp/pub/ops5-benchmark-suite/.

After the first Seating arrangement has been assigned a depth-first recursion occurs which repeatedly assigns correct Seating arrangements until the last seat is assigned. Manners uses a Context instance to control execution flow; the activity diagram is partitioned to show the relation of the rule execution to the current Context state.

Figure 10.2. Manners Activity Diagram

Before going deeper into the rules lets first take a look at the asserted data and the resulting Seating arrangement. The data is a simple set of 5 guests who should be arranged in male/female pairs with common hobbies.

The Data

Each line of the results list is printed per execution of the “Assign Seat” rule. They key bit to notice is that each line has pid one greater than the last, the significance of this will be explained in t he “Assign Seating” rule description. The 'l' and the 'r' refer to the left and right, 's' is sean and 'n' is the guest name. In my actual implementation I used longer notation, 'leftGuestName', but this is not practicle in a printed article. I found the notation of left and right preferable to the original OPS5 '1' and '2

The Results

As the introduction states, manners is a depth-first or LIFO example. Depth-first refers to the Conflict Resolution strategy used to solve the problem. OPS5 had two strategies, LEX and MEA, LEX is a chain of several stratagies including Salience, Recency, Complexity:

Clips is able to specify the LEX and MEA strategies as well as others, however the default is a Depth strategy which is implemented from the LEX Recency strategy:

Jess only has two strategies, Depth and Breadth, which are documented the same as the Clips ones. When Miss Manners was first implemented in Drools 3.0 using the Depth strategy it was not producing the correct result, which meant it ran forever. This paper discusses the behaviour of Miss Manners with two Rule engines, Clips and Jess, and how they make it work and how it was made to work in Drools.

Once the context is changed to START_UP Activations are created for all asserted Guests; because all Activations are created as the result of a single Working Memory action, they all have the same Activation time tag. Using the Depth, or Breadth, Conflict Resolution strategy the Activations would be fired arbitrary. With LEX's Recency the last asserted Guest would have a higher time tag and its Activation would fire. The execution order in this rule has little importance, but has a big impact in the rule "Assign Seat". The Activation fires and asserts the first Seating arrangement, a Path and then sets the Context's state to create Activatiosn for "Assign Seat".

rule assignFirstSeat() {
  when {
    context : Context( state == Context.START_UP )
    guest : Guest()
    count : Count()
  } then {
    String guestName = guest.getName();
    drools.assert( new Seating( count.getValue(), 1, true, 1, guestName, 1, guestName) );
    drools.assert( new Path( count.getValue(), 1, guestName ) );
    count.setCount(  count.getValue() + 1 );
    context.setPath( Context.ASSIGN_SEATS );
  }
} 

This rule determines each of the Seating arrangements. The Rule creates cross product solutions for ALL asserted Seating arrangements against ALL the asserted guests; accept against itself or any already assigned Chosen solutions.

rule assignSeat() {  
  when {
    context : Context( state == Context.ASSIGN_SEATS )
    Seating( seatingId:id, seatingPid:pid, pathDone == true 
    seatingRightSeat:rightSeat seatingRightGuestName:rightGuestName )
    Guest( name == seatingRightGuestName, rightGuestSex:sex, rightGuestHobby:hobby )
    Guest( leftGuestName:name , sex != rightGuestSex, hobby == rightGuestHobby )
    count : Count()
    not ( Path( id == seatingId, guestName == leftGuestName) )
    not ( Chosen( id == seatingId, guestName == leftGuestName, hobby == rightGuestHobby) )
  } then {
    int newSeat = rightSeat + 1;
    drools.assert( new Seating( countValue, id, false, coung.getValue(), rightSeat, rightSeatName, newSeat, leftGuestName);
    drools.assert( new Path( countValue, leftGuestName, newSeat );
    drools.assert( new Chosen( id, leftGuestName, rightGuestHobby ) );
    count.setCount(  countValue + 1 );
    context.setPath( Context.MAKE_PATH );
  }
} 

However, as can be seen from the printed results shown earlier, it is essential that only the Seating with the highest pid cross product be chosen – yet how can this be possible if we have Activations for nearly all existing Seating and Guests. For example on the third iteration of "Assing Seat" these are the produced Activations, remember this is from a very small data set and with larger data sets there would be many more possible Activated Seating solutions, with multiple solutions per pid:

The creation of all these redundant Activations might seem pointless, but it must be remembered that Manners is not about good rule design; its purposefully designed as a bad rule to full stress test the cross product matching process, which this clearly does. Notice that each Activation has the same time tag of 35, as they were all activated by the change in Context to ASSIGN_SEATS. With OPS5 and LEX it would correctly fire the Activation with the last asserted Seating. With Depth strategy the execution is arbitrary yet Manners does correctly execute for Jess and Clips using the Depth strategy. Clips support, via the public fourms, have said that Manners was

Early Drools 3.0 implementations, implementing Depth, would not work as all the Activations had the same priority and the reliance on arbitrary execution meant that Seatings with lower pids where firing. A LEX style recency strategy was implemented and the benchmark worked correctly. This leaves the question how does Jess and Clips work, even if it is by coincidence. While I haven’t looked at Jess or Clips code Peter Lin has confirmed that Clips uses LinkedLists for the memory, as shown by the next* property from the PartialMatch Clips struct:

struct partialMatch
  {
   unsigned int betaMemory  : 1;
   unsigned int busy        : 1;
   unsigned int activationf : 1;
   unsigned int dependentsf : 1;
   unsigned int notOriginf  : 1;
   unsigned int counterf    : 1;
   unsigned int bcount      : 9;
   struct partialMatch *next;
   struct genericMatch binds[1];
  };

This suggests the joins remember and attempt joins based on the fact assertion order into the node; thus Activation firing would follow fact assertion order. When Manners is executed in Clips with the Breadth strategy other than executing forever, explained in the next section, it also does not fire the Activation with the highest pid for Seating instances and thus solutions are never found. This indicates that the order the Activations with the same time tag are placed on the Agenda are still executed in LIFO/FIFO order. Later versions of Drools have moved away from HashMaps for BetaNode memory and reliance on LEX style recency and instead use LinkedLists relying on assertion order to control LIFO - in much the same manner as Clips. So in Drools Manners works, but it works by coincidence, this level of behaviour should not be expected by the user. It is still unknown how Jess deals with this situation, Peter Lin believes that Jess may have some simple and undocumented fact recency solution.

Make Path must always fires before Path Done. A Path is asserted for each Seating arrangement up to the last asserted Seating. Notice that Path Done is a subset of Make Path, so how do we ensure that Make Path fires first?

rule makePath() {
  when {
    context : Context( state == Context.MAKE_PATH )
    Seating( seatingId:id, seatingPid:pid, pathDone == false )
    Path( id == seatingPid, pathGuestName:guest, pathSeat:seat )
    (not Path( id == seatingId, guestName == pathGuestName )
  } else {
    drools.assert( new Path( seatingId, pathSeat, pathGuestName ) );  
  }
}

rule pathDone() { 
  when { 
    context : Context( state == Context.MAKE_PATH ) 
    seating : Seating( pathDone == false ) 
  } then { 
    seating.setPathDone( true ); 
    context.setName( Context.CHECK_DONE ); 
  } 
}

Figure 10.3. Rete Diagram

With OPS5 LEX the recency strategy says that if all compared facts have the same time tag then the activation with more facts wins; which would make sure that "Make Path" always fires before "Path Done". Clips succesfully completes manners, no matter what the defined order of the rules are in the rule file. If a system is not relying on recency and the rule definition order does not impact execution then the Rete build process must attach joins in such a way that propagation ensures that most complex rules activate last - a kind of inbuilt compexity strategy, however this is not documented; thus with LIFO the first created Activation will fire last. When manners is executed in CLIPS with breadth strategy, it may result in an infinite loop if path_done is fired before make_path activations. This is because path_done modifies the context and removes the activations for make_path rule. For proper execution of manners, the activations for make_path have to fire before path_done. This again illustrates that the arbitrary execution for activations placed on the Agenda obey the set LIFO/FIFO strategy.

"Are We Done" only activates when the last seat is assigned, at which point both rules will be activated. For the same reason that "Make Path" always wins over "Path Done" "Are We Done" will take priority over "Continue".

 rule areWeDone() { 
  when { 
    context : Context( state == Context.CHECK_DONE ) 
    LastSeat( lastSeat: seat )
    Seating( rightSeat == lastSeat ) 
  } then { 
    context.setState(Context.PRINT_RESULTS ); 
  } 
}

rule continue() { 
  Context context; 
  when { 
    context : Context( state == Context.CHECK_DONE ) 
  } then { 
    context.setState( Context.ASSIGN_SEATS ); 
  } 
}