Miss Manners and Benchmarking

Name: Miss Manners
Main class: org.drools.benchmark.manners.MannersBenchmark
Type: java application
Rules file: manners.drl
Objective: Advanced walkthrough on the Manners benchmark, covers Depth conflict resolution in depth.

Introduction

Miss Manners is throwing a party and being the good host she wants to arrange good seating. Her initial design arranges everyone in male female pairs, but then she worries about people have things to talk about; what is a good host to do? So she decides to note the hobby of each guest so she can then arrange guests in not only male and female pairs but also ensure that a guest has someone to talk about a common hobby, from either their left or right side.

Figure 8.22. Miss Manners' Guests

Miss Manners' Guests

BenchMarking

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

    • Uses a depth-first search approach to determine the seating arrangements of boy/girl and one common hobby for dinner guests

  • Waltz

    • line labeling for simple scenes by constraint propagation

  • WaltzDB

    • More general version of Walts to be able to adapt to a database of facts

  • ARP

    • Route planner for a robotic air vehicle using the A* search algorithm

  • Weavera

    • VLSI router for channels and boxes using a black-board technique

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

Miss Manners Execution Flow

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 8.23. Manners Activity Diagram

Manners Activity Diagram

The Data and Results

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 practice in a printed article. I found the notation of left and right preferable to the original OPS5 '1' and '2

(guest (name n1) (sex m) (hobby  h1)  )
(guest (name n2) (sex f) (hobby  h1)  )
(guest (name n2) (sex f) (hobby  h3)  )
(guest (name n3) (sex m) (hobby  h3)  )
(guest (name n4) (sex m) (hobby  h1)  )
(guest (name n4) (sex f) (hobby  h2)  )
(guest (name n4) (sex f) (hobby  h3)  )
(guest (name n5) (sex f) (hobby  h2)  )
(guest (name n5) (sex f) (hobby  h1)  )
(last_seat (seat 5)  )

The Results

[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4] 
[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3] 
[Seating id=4, pid=3, done=false, ls=3, rn=n3, rs=4, rn=n2] 
[Seating id=5, pid=4, done=false, ls=4, ln=n2, rs=5, rn=n1]

Indepth look

Cheating

Manners has been around a long time and is a contrived benchmark meant to exercise the cross product joins and agenda, many people not understanding this tweak the example to achieve better performance, making their use of the Manners benchmark pointless. Known cheats to Miss Manners are:

  • Using arrays for a guests hobbies, instead of asserting each one as a single fact. This massively reduces the cross products.

  • The altering of the sequence of data can also reducing the amount of matching increase execution speed

  • Changing NOT CE (conditional element) such that the test algorithm only uses the "first-best-match". Basically, changing the test algorithm to backward chaining. the results are only comparable to other backward chaining rule engines or ports of Manners.

  • Removing the context so the rule engine matches the guests and seats pre-maturely. A proper port will prevent facts from matching using the context start.

  • Any change which prevents the rule engine from performing combinatorial pattern matching

  • If no facts are retracted in the reasoning cycle, as a result of NOT CE, the port is incorrect.

Conflict Resolution

Manners benchmark was written for OPS5 which has two conflict resolution strategies, LEX and MEA; LEX is a chain of several strategies including Salience, Recency, Complexity. The Recency part of the strategy drives the depth first (LIFO) firing order. The Clips manual documents the recency strategy as:

 

Every fact and instance is marked internally with a "time tag" to indicate its relative recency with respect to every other fact and instance in the system. The pattern entities associated with each rule activation are sorted in descending order for determining placement. An activation with a more recent pattern entities is placed before activations with less recent pattern entities. To determine the placement order of two activations, compare the sorted time tags of the two activations one by one starting with the largest time tags. The comparison should continue until one activation’s time tag is greater than the other activation’s corresponding time tag. The activation with the greater time tag is placed before the other activation on the agenda. If one activation has more pattern entities than the other activation and the compared time tags are all identical, then the activation with more time tags is placed before the other activation on the agenda.

 
 --Clips Reference Manual

However Jess and Clips both use the Depth strategy, which is simpler and lighter, which Drools also adopted. The Clips manual documents the Depth strategy as:

 

Newly activated rules are placed above all rules of the same salience. For example, given that fact-a activates rule-1 and rule-2 and fact-b activates rule-3 and rule-4, then if fact-a is asserted before fact-b, rule-3 and rule-4 will be above rule-1 and rule-2 on the agenda. However, the position of rule-1 relative to rule-2 and rule-3 relative to rule-4 will be arbitrary.

 
 --Clips Reference Manual

The initial Drools implementation for the Depth strategy would not work for manners without the use of salience on the "make_path" rule, the Clips support team had this to say:

 

The default conflict resolution strategy for CLIPS, depth, is different than the default conflict resolution strategy used by OPS5. Therefore if you directly translate an OPS5 program to CLIPS, but use the default depth conflict resolution strategy, you're only likely to get the correct behavior by coincidence. The lex and mea conflict resolution strategies are provided in CLIPS to allow you to quickly convert and correctly run an OPS5 program in CLIPS

 
 --Clips Support Forum

Investigation into the Clips code reveals there is undocumented functionality in the Depth strategy. There is an accumulated time tag used in this strategy; it's not an extensively fact by fact comparison as in the recency strategy, it simply adds the total of all the time tags for each activation and compares.

Assign First Seat

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. The last asserted Guest would have a higher fact time tag and its Activation would fire, becuase it has the highest accumulated fact time tag. 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 Activation for "Assign Seat".

rule assignFirstSeat
    when
        context : Context( state == Context.START_UP )
        guest : Guest()
        count : Count()
    then
        String guestName = guest.getName();
        
        Seating seating =  new Seating( count.getValue(), 1, true, 1, guestName, 1, guestName);
        insert( seating );
        
        Path path = new Path( count.getValue(), 1, guestName );
        insert( path );
        
        modify( count ) { setValue ( count.getValue() + 1 )  }

		System.out.println( "assign first seat :  " + seating + " : " + path );

        modify( context ) {
            setState( Context.ASSIGN_SEATS )
        } 
end

Assign Seat

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 findSeating
   when 
       context : Context( state == Context.ASSIGN_SEATS )
       $s      : Seating( pathDone == true )
       $g1     : Guest( name == $s.rightGuestName )
       $g2     : Guest( sex != $g1.sex, hobby == $g1.hobby )

       count   : Count()

       not ( Path( id == $s.id, guestName == $g2.name) )
       not ( Chosen( id == $s.id, guestName == $g2.name, hobby == $g1.hobby) )
   then
       int rightSeat = $s.getRightSeat();
       int seatId = $s.getId();
       int countValue = count.getValue();
       
       Seating seating = new Seating( countValue, seatId, false, rightSeat, $s.getRightGuestName(), rightSeat + 1, $g2.getName() );
       insert( seating );     
                            
       Path path = new Path( countValue, rightSeat + 1, $g2.getName()  );
       insert( path );
       
       Chosen chosen = new Chosen( seatId, $g2.getName(), $g1.getHobby() );
       insert( chosen  );

	   System.err.println( "find seating : " + seating + " : " + path + " : " + chosen);

       modify( count ) {setValue(  countValue + 1 )}        
       modify( context ) {setState( Context.MAKE_PATH )} 
end

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, of the same time tag, 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:

=>[ActivationCreated(35): rule=findSeating 
[fid:19:33]:[Seating id=3, pid=2, done=true, ls=2, ln=n4, rs=3, rn=n3] 
[fid:4:4]:[Guest name=n3, sex=m, hobbies=h3] 
[fid:3:3]:[Guest name=n2, sex=f, hobbies=h3]

=>[ActivationCreated(35): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1] 
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1] 

=>[ActivationCreated(35): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1] 
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

The creation of all these redundant Activations might seem pointless, but it must be remembered that Manners is not about good rule design; it's purposefully designed as a bad ruleset to fully stress test the cross product matching process and the agenda, 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 the accumulated fact time tag ensures the Activation with the last asserted Seating fires.

Make Path and Path Done

"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( state == Context.MAKE_PATH )
        Seating( seatingId:id, seatingPid:pid, pathDone == false )
        Path( id == seatingPid, pathGuestName:guestName, pathSeat:seat )
        not Path( id == seatingId, guestName == pathGuestName )
    then
        insert( new Path( seatingId, pathSeat, pathGuestName ) );
end
rule pathDone
    when
        context : Context( state == Context.MAKE_PATH ) 
        seating : Seating( pathDone == false ) 
    then
        modify( seating ) {setPathDone( true )} 
        
		modify( context ) {setState( Context.CHECK_DONE)}
end

Figure 8.24. Rete Diagram

Rete Diagram

Both rules end up on the Agenda in conflict and with identical activation time tags, however the accumulate fact time tag is greater for "Make Path" so it gets priority.

Continue and Are We Done

"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
        modify( context ) {setState(Context.PRINT_RESULTS )}
end
rule continue
    when
        context : Context( state == Context.CHECK_DONE ) 
    then
        modify( context ) {setState( Context.ASSIGN_SEATS )}
end

Output Summary

Assign First seat
=>[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
=>[fid:14:14]:[Path id=1, seat=1, guest=n5]

==>[ActivationCreated(16): rule=findSeating
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

==>[ActivationCreated(16): rule=findSeating
[fid:13:13]:[Seating id=1 , pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]*

Assign Seating
=>[fid:15:17] :[Seating id=2 , pid=1 , done=false, ls=1, lg=n5, rs=2, rn=n4]
=>[fid:16:18]:[Path id=2, seat=2, guest=n4]
=>[fid:17:19]:[Chosen id=1, name=n4, hobbies=h1]

=>[ActivationCreated(21): rule=makePath 
[fid:15:17] : [Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4]
[fid:14:14] : [Path id=1, seat=1, guest=n5]*

==>[ActivationCreated(21): rule=pathDone
[Seating id=2, pid=1, done=false, ls=1, ln=n5, rs=2, rn=n4]*

Make Path
=>[fid:18:22:[Path id=2, seat=1, guest=n5]]

Path Done

Continue Process
=>[ActivationCreated(25): rule=findSeating
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4]
[fid:7:7]:[Guest name=n4, sex=f, hobbies=h3]
[fid:4:4] : [Guest name=n3, sex=m, hobbies=h3]*

=>[ActivationCreated(25): rule=findSeating
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4]
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1], [fid:12:20] : [Count value=3]

=>[ActivationCreated(25): rule=findSeating
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, lnn4, rs=3, rn=n3]]
=>[fid:20:27]:[Path id=3, seat=3, guest=n3]]
=>[fid:21:28]:[Chosen id=2, name=n3, hobbies=h3}]

=>[ActivationCreated(30): rule=makePath
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]
[fid:18:22]:[Path id=2, seat=1, guest=n5]*

=>[ActivationCreated(30): rule=makePath 
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]
[fid:16:18]:[Path id=2, seat=2, guest=n4]*

=>[ActivationCreated(30): rule=done 
[fid:19:26]:[Seating id=3, pid=2, done=false, ls=2, ln=n4, rs=3, rn=n3]*

Make Path
=>[fid:22:31]:[Path id=3, seat=1, guest=n5]

Make Path 
=>[fid:23:32] [Path id=3, seat=2, guest=n4]

Path Done

Continue Processing
=>[ActivationCreated(35): rule=findSeating
[fid:19:33]:[Seating id=3, pid=2, done=true, ls=2, ln=n4, rs=3, rn=n3]
[fid:4:4]:[Guest name=n3, sex=m, hobbies=h3]
[fid:3:3]:[Guest name=n2, sex=f, hobbies=h3], [fid:12:29]*

=>[ActivationCreated(35): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1]

=>[ActivationCreated(35): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5] 
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1], [fid:1:1] : [Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]]
=>[fid:25:37]:[Path id=4, seat=4, guest=n2]]
=>[fid:26:38]:[Chosen id=3, name=n2, hobbies=h3]

==>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]
[fid:23:32]:[Path id=3, seat=2, guest=n4]*

==>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2] 
[fid:20:27]:[Path id=3, seat=3, guest=n3]*

=>[ActivationCreated(40): rule=makePath 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]
[fid:22:31]:[Path id=3, seat=1, guest=n5]*

=>[ActivationCreated(40): rule=done 
[fid:24:36]:[Seating id=4, pid=3, done=false, ls=3, ln=n3, rs=4, rn=n2]*

Make Path 
=>fid:27:41:[Path id=4, seat=2, guest=n4]

Make Path
=>fid:28:42]:[Path id=4, seat=1, guest=n5]]

Make Path
=>fid:29:43]:[Path id=4, seat=3, guest=n3]]

Path Done

Continue  Processing
=>[ActivationCreated(46): rule=findSeating 
[fid:15:23]:[Seating id=2, pid=1, done=true, ls=1, ln=n5, rs=2, rn=n4] 
[fid:5:5]:[Guest name=n4, sex=m, hobbies=h1], [fid:2:2]
[Guest name=n2, sex=f, hobbies=h1]

=>[ActivationCreated(46): rule=findSeating 
[fid:24:44]:[Seating id=4, pid=3, done=true, ls=3, ln=n3, rs=4, rn=n2]
[fid:2:2]:[Guest name=n2, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]*

=>[ActivationCreated(46): rule=findSeating 
[fid:13:13]:[Seating id=1, pid=0, done=true, ls=1, ln=n5, rs=1, rn=n5]
[fid:9:9]:[Guest name=n5, sex=f, hobbies=h1]
[fid:1:1]:[Guest name=n1, sex=m, hobbies=h1]

Assign Seating
=>[fid:30:47]:[Seating id=5, pid=4, done=false, ls=4, ln=n2, rs=5, rn=n1]
=>[fid:31:48]:[Path id=5, seat=5, guest=n1]
=>[fid:32:49]:[Chosen id=4, name=n1, hobbies=h1]