Geeks With Blogs

News
Charles Young

In May 2004, Microsoft published a whitepaper entitled ‘Microsoft BizTalk Server 2004 Performance Characteristics’ (MBTS-PC04)[1]. On pages 70-73 of this paper, Microsoft included the results from tests conducted on the Microsoft Business Rule Engine (MS-BRE). The first two test results are provided to indicate the scalability characteristics of the engine for large rulesets containing between 1,000 and 10,000 rules. The first result is for facts asserted as .NET objects. The second is for facts asserted as XML DOM documents.

In both cases, the graphs show a simple linear correspondence between the ruleset size and the time taken to complete the tests. This result has been publicly challenged by Peter Lin who suggested that they indicate either that Microsoft has not implemented the Rete algorithm, or that they have implemented it incorrectly. Scott Woodgate, a programme manager working on the Microsoft BizTalk Server product team, confirmed in early 2005 that the Microsoft Business Rule Framework (MS-BRF) product team had implemented the Rete algorithm in the MS-BRE. The Rete algorithm is the best-known and most widely used matching algorithm in modern forward-chaining inferencing rules engines. Peter’s responses can be read at the following locations.

http://www.theserverside.net/news/thread.tss?thread_id=30449

http://www.theserverside.net/tss?service=direct/0/PostNewsReply/postReply&sp=l36112&sp=F&sp=l184119

A brief quote will summarise Peter’s position:

“...I think Microsoft is making claims that are clearly untrue. If the biztalk (sic) rule engine really implemented RETE algorithm as Dr. Forgy described in his two papers, the performance characteristics would not show a dramatic decrease in performance as the number of rules increase…RETE when implemented correctly will not show a 2x decrease in performance as the rule count increases 2x…None of the existing RETE engines I know of show such poor performance with respect to ruleset size.”

Here is the graph for the .NET object results, as published in MBTS-PC04. They indeed show the engine taking twice as long to complete execution of a policy (an executable ruleset) each time the number of rules are doubled.

While this graph appears to show a classic linear scaling result, Peter is entirely correct in saying that the Rete algorithm is capable, in most true-life scenarios, of providing a much better performance characteristic as the rule set size is scaled. There are, however, several factors to consider when predicting the performance of Rete. The algorithm uses approaches such as node sharing and partial match retention to optimize performance, and these, in turn, depend on the details of the rules contained in a rule set.

The Microsoft Test
Microsoft does not provide a full description of the test they carried out, but there is enough information to adequately re-construct its main details. Here is their description of the test:

The policy used in this test contains rules like the following:
      If ( ClassN.Attribute >= constant )
           Then {Do something}

Note   Different .NET classes were used for the rules in the policy.
The application used to run the test executes the policy from four different threads.

The first point to note is that the rules are very simple. They contain a single condition which tests a value against a constant. Because the rule is so simple, it does not exploit all the features of the Rete. Specifically, a rule set which contains only rules which follow the above pattern will result in the Rete containing a collection of ‘alpha’ (1-input) nodes, but no beta (2-input) nodes. Hence, the partial match retention optimizations (associated with beta nodes) of the Rete will not apply.

Microsoft does not inform us of the action they take in the action list. Given the obvious simplicity of the rule pattern, it is reasonable to speculate that the rules are not performing any assertions, retractions or updates. If this is correct, there is no forward-chaining, and hence alpha-memory optimizations of the Rete are not exploited.

Microsoft provides some other relevant pieces of information about their test. They tell us that “different .NET classes were used for the rules in the policy” which probably means that they asserted facts of more than one type. This appears to be supported by a careful study of the example code provided on page 70 showing how the policy was executed.

The Policy object model was used in all test scenarios in this section. The policy execution was initiated from multiple threads, each thread using a unique Policy object instance; for example:

Thread n
Policy PolObj = new Policy(REFacts);
for (int i=0; i < NIterations; i++)
PolObj.Execute (REFacts);
PolObj.Dispose();

This example code was clearly not copied from the real test code as it contains obvious errors. The identifier ‘REFacts’, which presumably is the list of facts asserted initially to the engine, is used incorrectly to represent the name of policy in the Policy constructor, and again, correctly, as the argument to the Execute method. The Execute method can take either a single object or an array of objects representing one or more initial facts. Microsoft has used a plural form in the identifier (‘REFacts’) which may indicate that they asserted an array of multiple facts, presumably of different types, to the engine.

The code contains a ‘for’ statement with no body. It is likely that Microsoft meant to indicate that they executed the same policy a number of times as part of the test run. In MS-BRE, the Policy class represents an executable rule set where the rules have been translated into a run-time representation (in this case, a Rete (network of in-memory ‘nodes’). The Policy object caches this state. You can then execute the same policy as many times as you wish, asserting a new set of initial facts each time. In this case, the Rete is maintained, but the working memory is automatically re-initialised for each iteration of the Execute method.

One other point to note is that the test was run in a multi-threaded fashion. It appears that each thread maintained its own Rete via a thread-specific instance of the Policy object.

Explaining the results
As has been noted, and given that the assumptions about the test are broadly correct, the extreme simplicity of the rules used by Microsoft meant that their test appears to have made little or no use of the various optimizations offered by the Rete algorithm. Because no joins are performed, the Rete does not contain beta nodes and therefore does not retain partial matches at join nodes. Assuming that no assertions, retractions or updates were performed by any rule, the benefits of alpha memory in a forward-chaining scenario were not exploited. We cannot tell if there was any node sharing amongst the alpha nodes, but it is quite reasonable to speculate that Microsoft used a different constant value in each rule, in which case the Rete would have contain one alpha node for each rule. In this situation, the algorithm would perform in exactly the fashion described in Microsoft’s results.

Testing in other engines
In order to show that the performance results published by Microsoft are to be expected, it is necessary to perform similar tests against other Rete-based rules engines. Two such engines have been selected. Both engines are Java-based. One (Jess) is generally accepted as implementing the Rete algorithm correctly. The other (Drools) implements an algorithm called Rete-OO which is based on Rete. Peter Lin has claimed elsewhere that Drools does not implement the Rete algorithm entirely correctly. Specifically, I understand that its implementation of alpha memory is deemed incorrect, and that Peter has donated an alternative implementation to the Drools project which is currently being integrated into the engine. However, because Microsoft’s test does not exploit optimisation benefits of alpha memory, it is reasonable to speculate that an equivalent test conducted using Drools is likely to provide similar scalability characteristics to the other engines.

Further information on all three rules engines can be found at the following sites:

http://www.drools.org/

http://herzberg.ca.sandia.gov/jess/index.shtml

http://msdn.microsoft.com/biztalk/

The approach taken was to emulate the Microsoft test in its main details, in according to the above description and assumptions. The original test was emulated in all aspects except the multiple-threaded nature of the Microsoft test. My main justification for not implementing a multi-threaded approach is that it is entirely reasonable to expect the use of threading, as described by Microsoft, to possibly decrease the overall elapsed time of the test, but not in any way to change the scaling characteristics as the number of rules is increased. I am not interested in performing any kind of general speed comparison between the engines, and, in any case, there are far too many unknowns in the Microsoft test to allow this kind of comparison. We do not know how many facts were asserted, how many fact types were used or how many matches were achieved. We are not told how many iterations of the policy execution were undertaken. We don’t know if the results are the total elapsed time over these iterations or average elapsed time. We do not know what action each rule undertook and, lastly, we do not know if Microsoft optimized the engine settings in any way.

Each engine provides an API for executing rule sets. Microsoft provides very similar functionality at the API level to the other engines, but also provides an additional higher-level abstraction based on the concept of business ‘policies’. A policy is an executable rule set, and contains an instance of a rule engine. In addition, the Policy class is designed to work with the Ruleset Update service which is part of Microsoft’s Business Rules framework, and which decouples engines (‘executors’) from rule repositories whilst managing the publication and updating of rule sets. Microsoft’s original tests appear to have used this higher-level abstraction. In order to ensure the closest correspondence between the use of each engine, the Microsoft BRE test described here used the RuleEngine class directly. However, in order to emulate the original Microsoft tests reasonably closely, an ‘execute’ method was written for each engine, and implemented to assert the initial facts, execute the algorithm over those facts and then clear the working memory. Elapsed times were calculated within the ‘execute’ methods. The inclusion of elapsed time for fact assertions is vital to the test, as it is at this point that the facts are evaluated via the Rete. The inclusion within the elapsed time of the code that resets the working memory is more controversial, and is done simply to emulate the original Microsoft test more closely (the Policy class does this internally, although it uses Retract() rather than .Clear()). I conducted additional checks to ensure that including the resetting of working memory did not significantly distort or alter the scalability results for any of the engines. Here are the three ‘execute’ methods.

  • Jess (Java)

public void execute( ) throws JessException
{
  // Start measuring elasped time
  long start = System.currentTimeMillis( );

  // Assert the initial facts
  for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( );
  {
    rete.assertFact( (Fact)i.next() );
  }

  // Run the test
  rete.run();

  // Retract facts from working memory
  for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( );)
  {
    rete.retract( (Fact)i.next() );
  }

  // Stop measuring elapsed time
  timeTotal += (System.currentTimeMillis( ) - start);
}

  • Drools (Java)

public void execute( ) throws FactException
{
  List factHandles = new ArrayList();

  // Start measuring elasped time
  long start = System.currentTimeMillis( );

  // Assert the initial facts
  for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( );
  {
    factHandles.add ( this.workingMemory.assertObject( i.next( ) ) );
  }

  // Run the test
  this.workingMemory.fireAllRules( );

  // Retract facts from working memory
  for ( Iterator i = factHandles.iterator( ); i.hasNext( ); )
  {
    this.workingMemory.retractObject( (FactHandle)i.next( ) );
  }

  // Stop measuring elapsed time
  timeTotal += (System.currentTimeMillis( ) - start);
}

  • Microsoft BRE (C#)

public void Execute( )
{
  // Start measuring elasped time
  long start = DateTime.Now.Ticks;

  // Assert the initial facts
  foreach ( object fact in this.inputObjects)
  {
    ruleEngine.Assert( fact );
  }

  // Run the test
  ruleEngine.Execute();

  // Retract the facts from working memory
  foreach ( object fact in this.inputObjects)
  {
    ruleEngine.Retract( fact );
  }

  // Stop measuring elapsed time
  long end = DateTime.Now.Ticks;

  // Convert ticks to milliseconds
  timeTotal += Convert.ToInt64(
             new System.TimeSpan(end).TotalMilliseconds
           - new System.TimeSpan(start).TotalMilliseconds);
}

Note that the Microsoft BRE code contains additional logic to convert ‘ticks’ (100-nanosecond intervals) into milliseconds (yes, I know I could have simply divided by 10,000, but this is the ‘approved’ approach).

For any Microsoft Rule Engine users reading this, it may be worth recording that the approach taken here proved about 15% more optimal than using the Execute method of the Policy class.

Each test run for each engine tested a rule set of a given size. The code performed an initial four executions in order to ensure the engine was ‘warmed up’. This was probably unnecessary, but is generally good practice in this kind of testing. Thereafter, a further ten executions were performed against the single rule set, and the average elapsed time was measured and recorded. This was repeated for 10 different rule sets ranging from 1,000 to 10,000 rules. The entire test was then repeated ten times, and the average result for each rule set was calculated to provide the final result. Hence, each rule set was executed a total of 100 times

Rules and Facts

The rule sets were generated to contain a given number of simple tests. Each rule followed the same pattern, as follows:

  • Jess

(defrule rule0
    (theFact1 ( value 0))
    =>
    (call solidsoft.jess.example.simplerule.TestFact1 logResult 0)
)

  • Drools

<rule name='is0'>
    <parameter identifier='theFact1'><class>TestFact1</class></parameter>
    <java:condition>theFact1.getValue() == 0</java:condition>
    <java:consequence>
        theFact1.logResult( 0 );
    </java:consequence>
</rule>

  • Microsoft BRE

<rule name="rule0" priority="0" active="true">
  <if>
    <compare operator="equal">
      <lhs>
        <function>
          <classmember classref="theFact1" member="get_Value" 
                       sideeffects="false" />
        </function>
      </lhs>
      <rhs>
        <constant>
          <int>0</int>
        </constant>
      </rhs>
    </compare>
  </if>
  <then>
    <function>
      <classmember classref="theFact1" member="LogResult" 
                   sideeffects="true">
        <argument>
          <constant>
            <int>0</int>
          </constant>
        </argument>
      </classmember>
    </function>
  </then>
</rule>

The rule shown above can be expressed as follows:

If ( theFact1.getValue == 0 ) Then theFact1.logResult( 0 );

…where theFact1 is an instance of TestFact1

The constant value used in the condition was incremented by one for each generated rule.

Note that for the Microsoft BRE, the sideeffects flag as been set to ‘false’ within the condition. This was done in order to ensure that the three tests more closely corresponded. The side effects feature has been the subject of some discussion between Peter Lin and myself, and Peter makes some good points with regards to its lack of safety. Interestingly, switching side effects off for facts expressed as .NET objects proved to be a significant optimisation.

Five fact classes were created (TestFact1, TestFact2, etc). The generated rule set selected one of the five classes in each rule, with each class used in a round-robin fashion across the rule set (i.e., rule 0 used TestFact1, rule 1 used TestFact2, etc, with rule 5 using TestFact1 and starting a new ‘round’).

The logResult() method did nothing. Originally it logged a message to a text file. This additional work made no difference to the overall scalability comparisons, but constituted additional work which I removed in order to simplify the test as much as I could.

A .dat file was created to define 100 facts for initial assertion to the engine. An extract is shown below

(make theFact1 ^value 0)
(make theFact2 ^value 101)
(make theFact3 ^value 202)
(make theFact4 ^value 303)
(make theFact5 ^value 404)
(make theFact1 ^value 505)
(make theFact2 ^value 606)
(make theFact3 ^value 707)
(make theFact4 ^value 808)
(make theFact5 ^value 909)

The same .dat file was used for each test. The values were deliberately set in order to maximize the number of match ‘hits’. Note that although the same identifier (e.g., ‘theFact1’) appears many times in the .dat file, this is not problem. The code creates and asserts multiple instances of the same class (e.g., TestFact1).

Results
The results of the test are shown below. Note that I took the liberty of adjusting the figures in order to show ‘time units’ in the y-axis, rather than actual milliseconds. This is because the purpose of this test is not to compare raw performance between the three engines, but to investigate the scaling characteristics of each engine when performing a similar test to the one described by Microsoft in their whitepaper. In order to emphasis this, I used the simple approach of calculating the average time increment for each engine as the rule set was increased in size by 1,000 rules, and then dividing the millisecond value by this average. The results allow the scaling characteristics to be more directly compared. Note that I have included the true millisecond values in appendix E, together with some brief comments on performance.

It can be seen immediately that the graph lines for each of the engines exhibit the same linear correspondence as seen in Microsoft’s results. The graph provides direct and compelling evidence that Rete-based engines, including engines known to implement the algorithm correctly, will exhibit the results Microsoft published when used to evaluate the extremely simple rules used within Microsoft’s test.

I hope, with the greatest respect to Peter, that these results will be accepted as compelling evidence that his assertions with regards to Microsoft’s test results are groundless. It is important to note that these figures in no way prove the correctness of Microsoft’s implementation of the Rete algorithm. They do, however, show that Microsoft’s published results provide no evidence whatsoever of an incorrect implementation of the algorithm.

Further Evidence
MBTS-PC04 provides some evidence to support the assertion that the Rete algorithm is being used with the MS-BRE. On pages 72 and 73, Microsoft reports the result of one of their tests under the title “Increasing the Number of Conditions”. This specific test is one of a series of tests investigating performance in relation to the use of facts asserted as ADO.NET datasets where a connection to the underlying data source is exploited. Microsoft explains the test as follows:

This test used a policy that contained 100 rules, and changed the number of unique conditions in the rules.

Rule N

If (Table1.Column1 = (N Mod NumberofUniqueConditions)
Then Class1.Property1 = Table1.Column1

The purpose of the test was to show how the data connection binding becomes much more efficient when the rule set uses shared conditions/queries. The following graph shows the results of the test.

This graph shows a very significant increase in performance as the number of ‘unique queries’ contained in the conditions of the rules is reduced to 1. This is clear evidence to support the claim that the engine is using node sharing optimisations. Whilst this result does not prove a correct implementation of the Rete algorithm, it is what would be expected if Rete is correctly implemented.

Conclusion
In contrast to Peter’s assertions, the performance results published by Microsoft do not provide any evidence that their implementation of the Rete algorithm is incorrect, but do provide evidence to support the assertion that features such as node sharing are working as expected. It is, perhaps, to be regretted that Microsoft’s published figures do not provide better evidence of the benefits of using the Rete algorithm in the match phase of the match-resolve-act cycle.


Appendix A

Source code - Jess

The TestSimpleRulePerformance class performs the test. Pass the name of the .CLP file as the first command line parameter. You can also create rule sets of a given size by providing an integer as the first command line parameter.

/**
* A simple example of using 'store' and 'fetch'
*/

package solidsoft.jess.example.simplerule;
import jess.*;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StringWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class TestSimpleRulePerformance
{
  /**
  * The DAT file defines the facts that will be initially asserted to the engine
  */
  private static final String DAT_FILE = "TestSimpleRulePerformance_100.dat";

  /**
  * The LOG file captures the average elapsed times durign a test run.
  */
  private static final String LOG_FILE = "TestSimpleRulePerformance.log";

  /**
  * The DRL file contains the ruleset. Set to the default ruleset.
  */
  private static String CLP_FILE = "TestSimpleRulePerformance.clp";

  /**
  * List of SolidSoft.jess.example.simplerule.* objects
  * read from the provided *.dat data file and to be asserted into the
  * WorkingMemory.
  */
  private List inputObjects;

  /**
  * The total elapsed time
  */
  private static long timeTotal = 0;

  /**
  * Executes the built Rete network
  */
  private static Rete rete = null;

  /**
  * Holdes the size of the current ruleset
  */
  static long ruleSetSize = 0;

  public static void main(String[] args)
      throws IOException,
      JessException
  {
    String datFile = DAT_FILE;
    int ruleCount = 1000;
    boolean doCreateRules = false;

    if ( args.length > 0 )
    {
      try
      {
        ruleCount = Integer.parseInt( args[0] );
        doCreateRules = true;
      }
      catch(Exception ex)
      {
        // not an integer, so we assume it is the name of the .clp file;
        CLP_FILE = args[0];
        ruleSetSize = Integer.parseInt( args[1] );
      }
    }

    if (doCreateRules)
    {
      createRules(ruleCount);
    }
    else
    {
      TestSimpleRulePerformance testPerf = new TestSimpleRulePerformance( datFile );

      // Warm up - execute the ruleset a few times
      for (int wuIdx = 0; wuIdx < 4; wuIdx++)
      {
        testPerf.execute( );
      }

      // Execute the ruleset several times more and take the average time
      int exCount = 10;

      timeTotal = 0;

      for (int exIdx = 0; exIdx < exCount; exIdx++)
      {
        testPerf.execute( );
      }

      String elapsedTimeMsg = "" + ( timeTotal / exCount );
      System.out.println( elapsedTimeMsg );

      String commaSep = ", ";
      File logFile = new File( LOG_FILE );
      FileOutputStream fsOut = new FileOutputStream( logFile, true );
      fsOut.write( elapsedTimeMsg.getBytes( ) );
      if (ruleSetSize == 10000)
      {
        fsOut.write( System.getProperty( "line.separator" ).getBytes( ) );
      }
      else
      {
        fsOut.write( commaSep.getBytes( ) );
      }
      fsOut.close();
    }
  }

  /**
  * Read the CLP and DAT files
  *
  * @param datFile the input data file
  */
  public TestSimpleRulePerformance( String datFile )
        throws IOException,
        JessException
  {
    System.out.println( "Loading CLP: " + CLP_FILE + "..." );

    rete = new Rete();

    // Read in the rules
    rete.executeCommand("(batch " + CLP_FILE + ")");
    rete.executeCommand("(reset)");

    System.out.println( "Reading DAT: " + datFile + "..." );
    this.inputObjects = getInputObjects( this.getClass( ).getResourceAsStream( datFile ) );

  }

  /**
  * Attempts to closely mimic Microsoft's Execute method on an MS-BRE Policy object by
  * 'reseting' the working memory, and then asserting the initial objects and firing
  * all rules.
  */
  public void execute( )
  throws JessException
  {
    // Start measuring elasped time
    long start = System.currentTimeMillis( );

    // Assert the initial facts
    for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( );)
    {
      rete.assertFact( (Fact)i.next() );
    }

    // Run the test
    rete.run();

    // Retract facts from working memory
    for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( );)
    {
      rete.retract( (Fact)i.next() );
    }

    // Stop measuring elapsed time
    timeTotal += (System.currentTimeMillis( ) - start);
  }

  /**
  * Creates a rule set with a given number of simple rules
  */
  private static void createRules(int ruleCount)
        throws FileNotFoundException,
        IOException
  {
    final String LINE_SEPARATOR = System.getProperty( "line.separator" );

    StringWriter writer = new StringWriter( );

    writer.write( "(defclass theFact1 SolidSoft.jess.example.simplerule.TestFact1)" + LINE_SEPARATOR );
    writer.write( "(defclass theFact2 SolidSoft.jess.example.simplerule.TestFact2)" + LINE_SEPARATOR );
    writer.write( "(defclass theFact3 SolidSoft.jess.example.simplerule.TestFact3)" + LINE_SEPARATOR );
    writer.write( "(defclass theFact4 SolidSoft.jess.example.simplerule.TestFact4)" + LINE_SEPARATOR );
    writer.write( "(defclass theFact5 SolidSoft.jess.example.simplerule.TestFact5)" + LINE_SEPARATOR + LINE_SEPARATOR );

    int factTypeNo = 0;

    // Output the rules
    for ( int idx = 0; idx < ruleCount; idx++ )
    {
      if (factTypeNo == 5) factTypeNo = 0;
      factTypeNo++;

      writer.write( "(defrule rule" + idx + LINE_SEPARATOR );
      writer.write( "(theFact" + factTypeNo + " ( value " + idx + "))" + LINE_SEPARATOR );
      writer.write( "=>" + LINE_SEPARATOR );
      writer.write( "(call SolidSoft.jess.example.simplerule.TestFact1 logResult " + idx + ")" + LINE_SEPARATOR );
      writer.write( ")" + LINE_SEPARATOR + LINE_SEPARATOR );
    }

    String path = TestSimpleRulePerformance.class.getResource( CLP_FILE ).getPath( );
    path = path.replaceAll(".clp", "");
    path += "_" + ruleCount + ".clp";
    File clpFile = new File( path );
    FileOutputStream fsOut = new FileOutputStream( clpFile );

    fsOut.write( writer.getBuffer( ).toString( ).getBytes( ) );
    fsOut.close();
  }

  /**
  * Convert the facts from the InputStream to a list of
  * objects.
  */
  private static List getInputObjects( InputStream inputStream )
        throws IOException,
        JessException
  {
    List list = new ArrayList( );

    BufferedReader br = new BufferedReader( new InputStreamReader( inputStream ) );

    String line;
    while ( ( line = br.readLine( ) ) != null )
    {
      if ( line.trim( ).length( ) == 0 || line.trim( ).startsWith( ";" ) )
      {
        continue;
      }

      StringTokenizer st = new StringTokenizer( line, "() " );
      String make = st.nextToken( );

      if ( !"make".equals( make ) )
      {
        throw new IOException( "expected 'make' in: " + line );
      }

      String type = st.nextToken( );

      int factTypeNo = 0;

      if ( "theFact1".equals( type ) )
      {
        factTypeNo = 1;
      }
      else if ( "theFact2".equals( type ) )
      {
        factTypeNo = 2;
      }
      else if ( "theFact3".equals( type ) )
      {
        factTypeNo = 3;
      }
      else if ( "theFact4".equals( type ) )
      {
        factTypeNo = 4;
      }
      else if ( "theFact5".equals( type ) )
      {
        factTypeNo = 5;
      }

      if ( factTypeNo > 0 )
      {
        if ( !"^value".equals( st.nextToken( ) ) )
        {
          throw new IOException( "expected '^value' in: " + line );
        }

        int value = Integer.parseInt( st.nextToken( ) );
        Fact fact = null;
        switch (factTypeNo)
        {
          case 1:
            fact = new Fact("theFact1", rete);
            break;
          case 2:
            fact = new Fact("theFact2", rete);
            break;
          case 3:
            fact = new Fact("theFact3", rete);
            break;
          case 4:
            fact = new Fact("theFact4", rete);
            break;
          case 5:
            fact = new Fact("theFact5", rete);
            break;
        }

        if (fact != null)
        {
          fact.setSlotValue("value", new Value(value, RU.INTEGER));
          list.add( fact );
        }
      }
    }

    inputStream.close( );

    return list;
  }
}

The test uses five fact files. These are virtually identical, and define classes called TestFact1, TestFact2…TestFact5. TestFact1 is show below.

package SolidSoft.jess.example.simplerule;

import java.io.File;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;

public class TestFact1
{
  private int value;

  public TestFact1( int value )
  {
    this.value = value;
  }

  public int getValue( )
  {
    return this.value;
  }

  public void setValue( int value )
  {
    this.value = value;
  }

  public int getLogResult()
  {
    return 0;
  }

  public static void logResult(int value) throws FileNotFoundException, IOException
  {
    // Do nothing here
  }

  public String toString( )
  {
    return "TestFact1["
         + "value=" + this.value
         + "]";
  }
}

Appendix B

Source code - Drools

The TestSimpleRulePerformance class performs the test. Pass the name of the .DRL file as the first command line parameter. You can also create rule sets of a given size by providing an integer as the first command line parameter.

package solidsoft.drools.example.simplerule;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StringWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;
import org.drools.DroolsException;
import org.drools.FactException;
import org.drools.RuleBase;
import org.drools.rule.RuleSet;
import org.drools.WorkingMemory;
import org.drools.FactHandle;
import
org.drools.conflict.ComplexityConflictResolver;
import org.drools.io.RuleBaseLoader;
import org.xml.sax.SAXException;

public class TestSimpleRulePerformance
{
  private static final String DOT_FILE = "TestSimpleRulePerformance.dot";

  /**
  * The DAT file defines the facts that will be initially asserted to the engine
  */
  private static final String DAT_FILE = "TestSimpleRulePerformance_100.dat";

  /**
  * The LOG file captures the average elapsed times durign a test run.
  */
  private static final String LOG_FILE = "TestSimpleRulePerformance.log";

  /**
  * The DRL file contains the ruleset. Set to the default ruleset.
  */
  private static String DRL_FILE = "TestSimpleRulePerformance.drl";

  /**
  * The RuleBase creates and holds the Rete
  */
  private RuleBase ruleBase;

  /**
  * The total elapsed time
  */
  static long timeTotal = 0;

  /**
  * Holdes the size of the current ruleset
  */
  static long ruleSetSize = 0;

  /**
  * List of solidsoft.drools.example.simplerule.* objects
  * read from the provided *.dat data file and to be asserted into the
  * WorkingMemory.
  */
  private List inputObjects;

  /**
  * The WorkingMemory generated by the rules in the DRL file.
  */
  private WorkingMemory workingMemory;

  /**
  * Creates a new TestSimpleRulePerformance object and executes its
  * run method.
  *
  * @param args if an argument is provided,
  * it is used as the name of the *.dat data file to use.
  */
  public static void main ( String[] args ) throws DroolsException, IOException, SAXException
  {
    String datFile = DAT_FILE;
    int ruleCount = 1000;
    boolean doCreateRules = false;

    if ( args.length > 0 )
    {
      try
      {
        ruleCount = Integer.parseInt( args[0] );
        doCreateRules = true;
      }
      catch( Exception ex )
      {
        // not an integer, so we assume it is the name of the .drl file;
        DRL_FILE = args[0];
      }
    }

    if ( doCreateRules )
    {
      createRules( ruleCount );
    }
    else
    {
      TestSimpleRulePerformance testPerf = new TestSimpleRulePerformance( datFile );

      // Warm up - execute the ruleset a few times
      for ( int wuIdx = 0; wuIdx < 4; wuIdx++ )
      {
        testPerf.execute( );
      }

      // Execute the ruleset a few times more and take the average time
      int exCount = 10;
      timeTotal = 0;

      for
( int exIdx = 0; exIdx < exCount; exIdx++ )
      {
        testPerf.execute( );
      }

      String elapsedTimeMsg = "" + ( timeTotal / exCount );
      System.out.println( elapsedTimeMsg );
      String commaSep = ", ";
      File logFile = new File( LOG_FILE );
      FileOutputStream fsOut = new FileOutputStream( logFile, true );
      fsOut.write( elapsedTimeMsg.getBytes( ) );

      if ( ruleSetSize == 10000 )
      {
        fsOut.write( System.getProperty( "line.separator" ).getBytes( ) );
      }
      else
      {
        fsOut.write( commaSep.getBytes( ) );
      }
        fsOut.close();
    }
  }

  /**
  * Read the DRL and DAT files, output the Rete to a DOT file,
  * and initialize a WorkingMemory.
  *
  * @param datFile the input data file
  */
  public TestSimpleRulePerformance( String datFile ) throws DroolsException, IOException, SAXException
  {
    System.out.println( "Loading DRL: " + DRL_FILE + "..." );
    ruleBase = RuleBaseLoader.loadFromUrl(
                   TestSimpleRulePerformance.class.getResource( DRL_FILE ),
                   ComplexityConflictResolver.getInstance( ) );

    // Set the working memory
    this.workingMemory = ruleBase.newWorkingMemory( );

    ruleSetSize = ( (RuleSet)ruleBase.getRuleSets( ).get( 0 )).getRules( ).length;
    System.out.println( "Reading DAT: " + datFile + "..." );
    this.inputObjects = getInputObjects( this.getClass( ).getResourceAsStream( datFile ) );
  }

  /**
  * Attempts to closely mimic Microsoft's Execute method on an MS-BRE Policy object by
  * 'reseting' the working memory, and then asserting the initial objects and firing
  * all rules.
  */
  public void execute( ) throws FactException
  {
    List factHandles = new ArrayList();

    // Start measuring elasped time
    long start = System.currentTimeMillis( );

    // Assert the initial facts
    for ( Iterator i = this.inputObjects.iterator( ); i.hasNext( ); )
    {
      factHandles.add ( this.workingMemory.assertObject( i.next( ) ) );
    }

    // Fire the rules on the agenda
    this.workingMemory.fireAllRules( );

    // Retract facts from working memory
    for ( Iterator i = factHandles.iterator( ); i.hasNext( ); )
    {
      this.workingMemory.retractObject( (FactHandle)i.next( ) );
    }

    // Stop measuring elapsed time
    timeTotal += (System.currentTimeMillis( ) - start);
  }

  /**
  * Creates a rules set with a given number of simple rules
  */
  private static void createRules( int ruleCount ) throws FileNotFoundException, IOException
  {
    final String LINE_SEPARATOR = System.getProperty( "line.separator" );

    StringWriter writer = new StringWriter( );

    writer.write( "<?xml version='1.0' encoding='UTF-8'?>" + LINE_SEPARATOR + LINE_SEPARATOR );
    writer.write( "<rule-set name='Simple Rules'" + LINE_SEPARATOR );
    writer.write( "        xmlns='http://drools.org/rules'" + LINE_SEPARATOR );
    writer.write( "        xmlns:java='http://drools.org/semantics/java'" + LINE_SEPARATOR );
    writer.write( "        xmlns:xs='http://www.w3.org/2001/XMLSchema-instance'" + LINE_SEPARATOR );
    writer.write( "        xs:schemaLocation='http://drools.org/rules rules.xsd" + LINE_SEPARATOR );
    writer.write( "                           http://drools.org/semantics/java java.xsd'>" + LINE_SEPARATOR + LINE_SEPARATOR );
    writer.write( "    <import>solidsoft.drools.example.simplerule.TestFact1</import>" + LINE_SEPARATOR );
    writer.write( "    <import>solidsoft.drools.example.simplerule.TestFact2</import>" + LINE_SEPARATOR );
    writer.write( "    <import>solidsoft.drools.example.simplerule.TestFact3</import>" + LINE_SEPARATOR );
    writer.write( "    <import>solidsoft.drools.example.simplerule.TestFact4</import>" + LINE_SEPARATOR );
    writer.write( "    <import>solidsoft.drools.example.simplerule.TestFact5</import>" + LINE_SEPARATOR + LINE_SEPARATOR);

    int factTypeNo = 0;

    // Output the rules

    for
( int idx = 0; idx < ruleCount; idx++ )
    {
      if ( factTypeNo == 5 ) factTypeNo = 0;
      factTypeNo++;

      writer.write( "    <rule name='is" + idx + "'>" + LINE_SEPARATOR );
      writer.write( "        <parameter identifier='theFact" + factTypeNo + "'><class>TestFact" + factTypeNo + "</class></parameter>" + LINE_SEPARATOR );
      writer.write( "        <java:condition>theFact" + factTypeNo + ".getValue() == " + idx + "</java:condition>" + LINE_SEPARATOR );
      writer.write( "        <java:consequence>" + LINE_SEPARATOR );
      writer.write( "            theFact" + factTypeNo + ".logResult(" + idx + ");" + LINE_SEPARATOR );
      writer.write( "        </java:consequence>" + LINE_SEPARATOR );
      writer.write( "    </rule>" + LINE_SEPARATOR  + LINE_SEPARATOR);
    }

    writer.write( "</rule-set>" + LINE_SEPARATOR );

    String path = TestSimpleRulePerformance.class.getResource( DRL_FILE ).getPath( );
    path = path.replaceAll(".drl", "");
    path += "_" + ruleCount + ".drl";
    File drlFile = new File( path );
    FileOutputStream fsOut = new FileOutputStream( drlFile );

    fsOut.write( writer.getBuffer( ).toString( ).getBytes( ) );
    fsOut.close();
  }

  /**
  * Convert the facts from the InputStream to a list of
  * objects.
  */
  private static List getInputObjects( InputStream inputStream ) throws IOException
  {
    List list = new ArrayList( );
    BufferedReader br = new BufferedReader( new InputStreamReader( inputStream ) );
    String line;

    while ( ( line = br.readLine( ) ) != null )
    {
      if ( line.trim( ).length( ) == 0 || line.trim( ).startsWith( ";" ) )
      {
        continue;
      }

      StringTokenizer st = new StringTokenizer( line, "() " );
      String make = st.nextToken( );

      if ( !"make".equals( make ) )
      {
        throw new IOException( "expected 'make' in: " + line );
      }

      String type = st.nextToken( );

      int factTypeNo = 0;

      if ( "theFact1".equals( type ) )
      {
        factTypeNo = 1;
      }
      else if ( "theFact2".equals( type ) )
      {
        factTypeNo = 2;
      }
      else if ( "theFact3".equals( type ) )
      {
        factTypeNo = 3;
      }
      else if ( "theFact4".equals( type ) )
      {
        factTypeNo = 4;
      }
      else if ( "theFact5".equals( type ) )
      {
        factTypeNo = 5;
      }

      if ( factTypeNo > 0 )
      {
        if ( !"^value".equals( st.nextToken( ) ) )
        {
          throw new IOException( "expected '^value' in: " + line );
        }

        int value = Integer.parseInt( st.nextToken( ) );

        switch ( factTypeNo )
        {
          case 1:
            list.add( new TestFact1( value ) );
            break;
          case 2:
            list.add( new TestFact2( value ) );
            break;
          case 3:
            list.add( new TestFact3( value ) );
            break;
          case 4:
            list.add( new TestFact4( value ) );
            break;
          case 5:
            list.add( new TestFact5( value ) );
            break;
        }
      }
    }

    inputStream.close( );

    return list;
  }
}

The test uses five fact files. These are virtually identical, and define classes called TestFact1, TestFact2…TestFact5. TestFact1 is show below.

package SolidSoft.drools.example.simplerule;

import java.io.File;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.IOException;

public class TestFact1
{
  private int value;

  public TestFact1( int value )
  {
    this.value = value;
  }

  public int getValue( )
  {
    return this.value;
  }

  public void logResult( int value ) throws FileNotFoundException, IOException
  {
    // Do nothing here
  }

  public String toString( )
  {
    return "TestFact1["
           + "value=" + this.value
           + "]";
  }
}


Appendix C

Source code - Microsoft BRE

The TestSimpleRulePerformance class performs the test. Pass the name of the MS_BRL file as the first command line parameter and the rule set size as the second parameter. You can also create rule sets of a given size by providing an integer as the first command line parameter.

namespace solidsoft.msbre.example.retetest
{
  using System;
  using System.Collections;
  using System.IO;
  using System.Text;
  using Microsoft.RuleEngine;

  ///


  ///   Summary description for Test1.
  ///

  class TestSimpleRulePerformance
  {
    ///
    ///   The DAT file defines the facts that will be initially asserted to the engine
    ///

    private static readonly string DAT_FILE = "TestSimpleRulePerformance_100.dat";

    ///
    ///   The LOG file captures the average elapsed times during a test run.
    ///

    private static readonly string LOG_FILE = "TestSimpleRulePerformance.log";

    ///
    ///   The XML BRML file contains the ruleset. Set to the default ruleset.
    ///

    private static string BRL_FILE = "TestSimpleRulePerformance.xml";

    ///
    ///   List of solidsoft.msbre.example.retetest.* objects
    ///   read from the provided *.dat data file and to be asserted into the
    ///   WorkingMemory.
    ///

    private IList inputObjects;

    ///
    ///   The total elapsed time
    ///

    private static long timeTotal = 0;

    ///
    ///   Executes the built Rete network
    ///

    private static RuleEngine ruleEngine = null;

    ///
    ///   Holds the size of the current ruleset
    ///

    private static long ruleSetSize = 0;

    ///

    ///   The main entry point for the application.
    ///

    [STAThread]
    static void Main( string[] args )
    {
      string datFile = DAT_FILE;
      int ruleCount = 1000;
      bool doCreateRules = false;

      if ( args.Length > 0 )
      {
        try
        {
          ruleCount = int.Parse( args[0] );
          ruleSetSize = ruleCount;
          doCreateRules = true;
        }
        catch( Exception )
        {
          // not an integer, so we assume it is the name of the .xml file;
          BRL_FILE = args[0];
          ruleSetSize = int.Parse( args[1] );
        }
      }

      if ( doCreateRules )
      {
        CreateRules(ruleCount);
      }
      else
      {
        TestSimpleRulePerformance testPerf = new TestSimpleRulePerformance( datFile );

        // Warm up - execute the ruleset a few times
        for (int wuIdx = 0; wuIdx < 4; wuIdx++)
        {
          testPerf.Execute( );
        }

        // Execute the ruleset several times more and take the average time
        int exCount = 10;

        timeTotal = 0;

        for ( int exIdx = 0; exIdx < exCount; exIdx++ )
        {
          testPerf.Execute( );
        }

        long elapsedTime = timeTotal / exCount;
        string elapsedTimeMsg = "" + elapsedTime.ToString( );

        Console.WriteLine( elapsedTimeMsg );

        string commaSep = ", ";

        StreamWriter swOut = new StreamWriter( LOG_FILE, true );
        swOut.Write(elapsedTimeMsg);

        if ( ruleSetSize == 10000 )
        {
          swOut.Write( "\r\n" );
        }
        else
        {
          swOut.Write( commaSep );
        }

        swOut.Close( );
      }
    }

    public
TestSimpleRulePerformance( string datFile )
    {
      Console.WriteLine( "Loading BRML: " + BRL_FILE + "..." );

      RuleSetInfo rsInf = new RuleSetInfo("test1", 1, 0);
      FileRuleStore ruleStore = new FileRuleStore(BRL_FILE);
      RuleSet rsReteTest = ruleStore.GetRuleSet(rsInf);

      // Create the Rete
      Console.WriteLine( "Creating Rule Engine" );
      ruleEngine = new RuleEngine(rsReteTest, true);

      Console.WriteLine( "Reading DAT: " + datFile + "..." );

      this.inputObjects = GetInputObjects( datFile );
    }

    ///
    ///   Execute the policy
    ///

    public void Execute( )
    {
      // Start measuring elasped time
      long start = DateTime.Now.Ticks;

      // Assert the initial facts
      foreach ( object fact in this.inputObjects)
      {
        ruleEngine.Assert( fact );
      }

      // Run the test
      ruleEngine.Execute();

      // Retract the facts from working memory
      foreach ( object fact in this.inputObjects)
      {
        ruleEngine.Retract( fact );
      }

      // Stop measuring elapsed time
      long end = DateTime.Now.Ticks;

      // Convert ticks to milliseconds
      timeTotal += Convert.ToInt64(new System.TimeSpan(end).TotalMilliseconds - new System.TimeSpan(start).TotalMilliseconds);

    }

    ///
    ///   Creates a rule set with a given number of simple rules
    ///

    private static void CreateRules(int ruleCount)
    {
      StringBuilder sbRules = new StringBuilder( );

      sbRules.Append("<?xml version=\"1.0\" encoding=\"utf-8\"?>");
      sbRules.Append("<brl xmlns=\"http://schemas.microsoft.com/businessruleslanguage/2002\">");
      sbRules.Append("  <ruleset name=\"test1\">");
      sbRules.Append("    <version major=\"1\" minor=\"0\" description=\"\" modifiedby=\"PKBTS2004DEV\\CharlesY\" date=\"2005-09-13T01:29:01.6223328+01:00\" />");
      sbRules.Append("    <configuration />");
      sbRules.Append("    <bindings>");


      for (int factNo = 1; factNo <= 5; factNo++)
      {

        sbRules.Append("      <class ref=\"theFact" + factNo.ToString() + "\" class=\"TestFact" + factNo.ToString() + "\" instance=\"0\" instances=\"20\" selectivity=\"1\">");
        sbRules.Append("        <assembly>ReteTestFacts, Version=1.0.0.0, Culture=neutral, PublicKeyToken=5ae7aee3322e38e0</assembly>");
        sbRules.Append("        <namespace>solidsoft.msbre.example.retetest</namespace>");
        sbRules.Append("      </class>");
      }

      sbRules.Append("    </bindings>");

      int factTypeNo = 0;

      // Output the rules
      for ( int idx = 0; idx < ruleCount; idx++ )
      {
        if (factTypeNo == 5) factTypeNo = 0;
        factTypeNo++;

        sbRules.Append("    <rule name=\"rule" + idx.ToString() + "\" priority=\"0\" active=\"true\">");
        sbRules.Append("      <if>");
        sbRules.Append("        <compare operator=\"equal\">");
        sbRules.Append("          <lhs>");
        sbRules.Append("            <function>");
        sbRules.Append("              <classmember classref=\"theFact" + factTypeNo + "\" member=\"get_Value\" sideeffects=\"false\" />");
        sbRules.Append("            </function>");
        sbRules.Append("          </lhs>");
        sbRules.Append("          <rhs>");
        sbRules.Append("            <constant>");
        sbRules.Append("              <int>" + idx.ToString() + "</int>");
        sbRules.Append("            </constant>");
        sbRules.Append("          </rhs>");
        sbRules.Append("        </compare>");
        sbRules.Append("      </if>");
        sbRules.Append("      <then>");
        sbRules.Append("        <function>");
        sbRules.Append("          <classmember classref=\"theFact" +  factTypeNo + "\" member=\"LogResult\" sideeffects=\"true\">");
        sbRules.Append("            <argument>");
        sbRules.Append("              <constant>");
        sbRules.Append("                <int>" + idx.ToString() + "</int>");
        sbRules.Append("              </constant>");
        sbRules.Append("            </argument>");
        sbRules.Append("          </classmember>");
        sbRules.Append("        </function>");
        sbRules.Append("      </then>");
        sbRules.Append("    </rule>");
      }

      sbRules.Append("  </ruleset>");
      sbRules.Append("</brl>");

      string path = BRL_FILE;
      path = path.Replace(".xml", "");
      path += "_" + ruleCount.ToString() + ".xml";

      StreamWriter swOut = new StreamWriter(path);
      swOut.Write(sbRules.ToString());
      swOut.Close();
    }

    ///


    ///   Convert the facts from the InputStream to a list of objects.
    ///

    private static object[] GetInputObjects( string datFile )
    {
      IList list = new ArrayList( );

      StreamReader srDat = new StreamReader(datFile);
      string line;

      while ( ( line = srDat.ReadLine() ) != null )
      {
        if ( line.Trim( ).Length == 0 || line.Trim( ).StartsWith( ";" ) )
        {
          continue;
        }

        string delims = "() ";
        string[] tokens = line.Split(delims.ToCharArray());
        string make = tokens[1];

        if ( !"make".Equals( make ) )
        {
          throw new IOException( "expected 'make' in: " + line );
        }

        string type = tokens[2];
        int factTypeNo = 0;

        if ( "theFact1".Equals( type ) )
        {
          factTypeNo = 1;
        }
        else if ( "theFact2".Equals( type ) )
        {
          factTypeNo = 2;
        }
        else if ( "theFact3".Equals( type ) )
        {
          factTypeNo = 3;
        }
        else if ( "theFact4".Equals( type ) )
        {
          factTypeNo = 4;
        }
        else if ( "theFact5".Equals( type ) )
        {
          factTypeNo = 5;
        }

        if ( factTypeNo > 0 )
        {
          if ( !"^value".Equals( tokens[4] ) )
          {
            throw new IOException( "expected '^value' in: " + line );
          }

          int val = int.Parse( tokens[5] );
          object fact = null;
          switch (factTypeNo)
          {
            case 1:
              fact = new TestFact1(val);
              break;
            case 2:
              fact = new TestFact2(val);
              break;
            case 3:
              fact = new TestFact3(val);
              break;
            case 4:
              fact = new TestFact4(val);
              break;
            case 5:
              fact = new TestFact5(val);
              break;
          }

          if (fact != null)
          {
            list.Add( fact );
          }
        }
      }

      object[] factsOut = new object[list.Count];
      list.CopyTo(factsOut, 0);
      return factsOut;
    }
  }
}

The test uses five fact files. These are virtually identical, and define classes called TestFact1, TestFact2…TestFact5. TestFact1 is show below.

namespace SolidSoft.msbre.example.retetest
{
  using System;
  using System.IO;

  ///
  ///   Summary description for TestFact1.
  ///

  public class TestFact1
  {
    private int _value;

    public TestFact1( int value )
    {
      this._value = value;
    }

    public int Value
    {
      get
      {
        return this._value;
      }

      set
      {
        this._value = value;
      }
    }

    public static void LogResult(int value)
    {
      // Do nothing here
    }

    public String toString( )
    {
      return "TestFact1["
           + "value=" + this._value.ToString()
           + "]";
    }
  }
}


Appendix D

Test Data

The following is the contents of the TestSimpleRulePerformance_100.dat file.

(make theFact1 ^value 0)
(make theFact2 ^value 101)
(make theFact3 ^value 202)
(make theFact4 ^value 303)
(make theFact5 ^value 404)
(make theFact1 ^value 505)
(make theFact2 ^value 606)
(make theFact3 ^value 707)
(make theFact4 ^value 808)
(make theFact5 ^value 909)
(make theFact1 ^value 1000)
(make theFact2 ^value 1101)
(make theFact3 ^value 1202)
(make theFact4 ^value 1303)
(make theFact5 ^value 1404)
(make theFact1 ^value 1505)
(make theFact2 ^value 1606)
(make theFact3 ^value 1707)
(make theFact4 ^value 1808)
(make theFact5 ^value 1909)
(make theFact1 ^value 2000)
(make theFact2 ^value 2101)
(make theFact3 ^value 2202)
(make theFact4 ^value 2303)
(make theFact5 ^value 2404)
(make theFact1 ^value 2505)
(make theFact2 ^value 2606)
(make theFact3 ^value 2707)
(make theFact4 ^value 2808)
(make theFact5 ^value 2909)
(make theFact1 ^value 3000)
(make theFact2 ^value 3101)
(make theFact3 ^value 3202)
(make theFact4 ^value 3303)
(make theFact5 ^value 3404)
(make theFact1 ^value 3505)
(make theFact2 ^value 3606)
(make theFact3 ^value 3707)
(make theFact4 ^value 3808)
(make theFact5 ^value 3909)
(make theFact1 ^value 4000)
(make theFact2 ^value 4101)
(make theFact3 ^value 4202)
(make theFact4 ^value 4303)
(make theFact5 ^value 4404)
(make theFact1 ^value 4505)
(make theFact2 ^value 4606)
(make theFact3 ^value 4707)
(make theFact4 ^value 4808)
(make theFact5 ^value 4909)
(make theFact1 ^value 5000)
(make theFact2 ^value 5101)
(make theFact3 ^value 5202)
(make theFact4 ^value 5303)
(make theFact5 ^value 5404)
(make theFact1 ^value 5505)
(make theFact2 ^value 5606)
(make theFact3 ^value 5707)
(make theFact4 ^value 5808)
(make theFact5 ^value 5909)
(make theFact1 ^value 6000)
(make theFact2 ^value 6101)
(make theFact3 ^value 6202)
(make theFact4 ^value 6303)
(make theFact5 ^value 6404)
(make theFact1 ^value 6505)
(make theFact2 ^value 6606)
(make theFact3 ^value 6707)
(make theFact4 ^value 6808)
(make theFact5 ^value 6909)
(make theFact1 ^value 7000)
(make theFact2 ^value 7101)
(make theFact3 ^value 7202)
(make theFact4 ^value 7303)
(make theFact5 ^value 7404)
(make theFact1 ^value 7505)
(make theFact2 ^value 7606)
(make theFact3 ^value 7707)
(make theFact4 ^value 7808)
(make theFact5 ^value 7909)
(make theFact1 ^value 8000)
(make theFact2 ^value 8101)
(make theFact3 ^value 8202)
(make theFact4 ^value 8303)
(make theFact5 ^value 8404)
(make theFact1 ^value 8505)
(make theFact2 ^value 8606)
(make theFact3 ^value 8707)
(make theFact4 ^value 8808)
(make theFact5 ^value 8909)
(make theFact1 ^value 9000)
(make theFact2 ^value 9101)
(make theFact3 ^value 9202)
(make theFact4 ^value 9303)
(make theFact5 ^value 9404)
(make theFact1 ^value 9505)
(make theFact2 ^value 9606)
(make theFact3 ^value 9707)
(make theFact4 ^value 9808)
(make theFact5 ^value 9909)


Appendix E

Detailed Results

The following are results obtained using the 100-rule data file in appendix B and rule sets between 1,000 and 10,000 rules in size. Each table shows overall results in the bold figures in the first three rows. The first row shows the rule set size. The second row shows the average elapsed time in milliseconds. The third row shows the adjusted figures used to generate the results graph. These adjusted figures were calculated by calculating the average time increment each time the rule-set was increased in size by 1,000 rules, and then dividing the actual millisecond value by this constant. This preserved the scaling characteristic information (the ‘gradient’ of the line), whilst adjusting the graphs to use the same y-axis range. The actual times in milliseconds is shown in the rest of the table. Each millisecond value is the average of ten consecutive execution of the given rule set.

Jess

 

 

 

 

 

 

 

 

 

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

16

38.5

59.6

79.6

98.5

114.4

139.3

156.7

177.4

198.7

0.788177

1.896552

2.935961

3.921182

4.852217

5.635468

6.862069

7.719212

8.738916

9.788177

 

 

 

 

 

 

 

 

 

 

16

37

61

85

96

116

139

156

176

197

16

40

59

78

98

114

137

156

175

197

16

38

60

80

98

114

137

156

176

199

15

39

59

79

97

113

137

156

176

198

16

39

59

79

98

117

137

156

176

198

16

40

58

80

101

114

137

156

176

198

16

39

59

77

96

114

137

156

176

200

16

38

62

81

98

114

138

156

176

198

16

38

58

80

107

113

137

159

180

199

17

37

61

77

96

115

157

160

187

203

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MS-BRE

 

 

 

 

 

 

 

 

 

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

22.4

56.1

83.4

109.9

132

159.4

184

213.8

238.7

254.8

0.86747

2.172547

3.229776

4.256024

5.111876

6.172978

7.125645

8.27969

9.243976

9.86747

 

 

 

 

 

 

 

 

 

 

23

52

91

108

130

159

182

210

252

261

23

62

86

108

130

156

181

230

237

253

21

60

81

108

129

155

182

209

238

256

22

60

81

108

130

157

184

211

238

256

22

60

81

108

131

165

182

210

236

252

22

56

83

115

136

167

182

211

237

252

23

53

86

115

134

163

182

210

236

252

22

53

80

113

141

155

182

214

237

262

23

53

80

108

129

156

182

210

238

252

23

52

85

108

130

161

201

223

238

252

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Drools

 

 

 

 

 

 

 

 

 

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

62.6

131

195.2

245

321.4

385.4

492.9

544.5

583.5

703.6

0.878939

1.839314

2.740718

3.439938

4.512637

5.411232

6.920593

7.645086

8.192668

9.878939

 

 

 

 

 

 

 

 

 

 

62

131

187

245

322

383

489

540

582

692

62

131

197

244

318

382

489

541

582

775

63

130

196

245

327

397

504

545

587

699

63

132

197

247

321

385

494

543

583

694

63

131

197

244

319

384

493

561

588

696

63

130

197

245

322

381

492

540

580

694

62

131

195

246

318

386

494

543

587

699

62

132

197

245

327

384

495

547

584

699

63

131

197

244

321

385

488

541

581

692

63

131

192

245

319

387

491

544

581

696

The test was not designed to provide reliable information about the relative performance of each engine, and the temptation to draw such conclusions should be resisted.   Having said that, it can be seen that Jess and MS-BRE performed significantly faster than Drools.    Please note that the MS-BRE test was knowingly optimised in two ways.   Firstly, there was a small optimisation in avoiding the use of the Policy class.  Secondly, switching side effects off within the rule conditions proved to be a significant optimisation (though even without this, MS-BRE performed test runs in significantly less time than Drools).   Both these optimisations were made in good faith as an attempt to more closely align the tests across the three engines.   However, I am not particularly familiar with the two Java engines, and it may be that I have missed optimisations or techniques that would have improved the performance results.   Again, I would ask that no-one reads more into these figures than is warranted.

All tests were conducted on the same machine. The specifications are provided below.

Property

Value

OS Name

Microsoft Windows XP Professional

Version

5.1.2600 Service Pack 2 Build 2600

OS Manufacturer

Microsoft Corporation

System Manufacturer

Clevo

System Model

4xx Series

System Type

X86-based PC

Processor

x86 Family 15 Model 2 Stepping 9 GenuineIntel ~2666 Mhz

BIOS Version/Date

Phoenix 4.06, 06/06/2003

SMBIOS Version

2.3

Hardware Abstraction Layer

Version = "5.1.2600.2180 (xpsp_sp2_rtm.040803-2158)"

Total Physical Memory

1,024.00 MB

Available Physical Memory

718.23 MB

Total Virtual Memory

2.00 GB

Available Virtual Memory

1.96 GB

Page File Space

2.40 GB

The Java code ran under Sun JRE 1.4.2 (09) (Java 2 Standard Edition)

The .NET code ran under .Net Framework 1.1.4322



[1] An updated version of this paper can be found at http://msdn.microsoft.com/library/default.asp?url=/library/en-us/BTS_2004WP/html/04d20926-20d2-4098-b701-52238a267eba.asp. It contains the same test results for the Microsoft Rules Engine as the original version of the paper.

Posted on Friday, September 16, 2005 1:51 AM | Back to top


Comments on this post: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Wow, great analysis as usual Charles.
Left by Scott Woodgate (MSFT) on Sep 16, 2005 3:34 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Thanks Scott. Didn't know you were following the debate :-)
Left by Charles Young on Sep 16, 2005 2:03 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Using Rete.reset in this case is wrong. If you look at JESS documentation closely, what reset does is this.

1. clear the working memory
2. re-assert any objects that have been asserted

this means that as the test runs, the number of facts asserted is equal to the iteration. Did you mean to do that? The test for Drools is correct and does clear the working memory. I don't know if that's what BRE does. What the JESS test should do is retract(object) and not reset. What you're measuring with that is the cost of retracting all objects and reasserting them.
Left by Peter Lin on Sep 16, 2005 4:27 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
I am writing some basic classes to generate clips rules and facts to duplicate the original tests I ran last year. I stupidly deleted the utilities after I ran the test to make room on my laptop. If you want them, I can send them to you. the tests should run in JESS and CLIPS. I plan to write up a short paper explaining the results and submit them to paul ballard to publish on TSS.net.

I think it's pretty clear that what you were testing on JESS was different than what was tested on BRE.

Peter Lin
Left by Peter Lin on Sep 16, 2005 7:04 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Thanks Peter. I am not a Jess or Drools expert which is why I felt it important to publish the source code for the tests. Glad I did. I must admit I could have made a better job of reading the Jess API documentation :-)

I amended the code and re-ran the tests using the approach you suggest. To make the tests as fair as possible, I amended the code for each engine to retract the facts in the same manner. I have updated the article with the amended code, results and graphs.

The changes made no difference to the overall conclusion. All three engines show a linear scale. This suggests to me that the number of facts asserted in such simplistic tests makes little impact on the overall scaling characteristics. My point therefore stands. You cannot conclude from Microsoft's results that they have incorrectly implemented their engine.

Do please send me your code (you can do this through this site if you wish using the 'Contact' tab at the top of this page). I will be happy to replicate the test in MS-BRE and publish the results.

Please note I have also now fixed various formatting issues with the code extracts shown in the article, and made sure the literal XML for the MS-BRE and Drools tests can be read.
Left by Charles Young on Sep 17, 2005 1:07 PM

# Debating Our Rules Engine
Requesting Gravatar...

If you're someone deeply interested in rule engine algorithms, and specifically Microsoft's implementation...
Left by Richard Seroter - SoCal BPI Musi on Sep 17, 2005 12:48 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
I never claimed to be authorative and challenged Microsoft to backup their claims. I'm still running some tests, but so far my results are completely different than what you got. I will post the code shortly. So far, it takes my laptop 1.4ghz centrino with 1gb of RAM 1 second to fire 1K rules.

All microsoft had to do was explain in greater detail what their test did and publish the test code. Unfortunately, Microsoft declined to do so, which should be a flag for everyone to question. I've challenged other companies on their assertion, and you can see them on TSS.net.

My interest is pointing flawed thinking about RETE, and bad benchmarks. Feel free to call me names if you like, but actions speak louder than words. I don't take criticism personally. In the end, what I care about is making sure benchmarks are good and the results back the claims.

once I post the results, you should be able to download it from dingo.sourceforge.net

peter
Left by Peter Lin on Sep 17, 2005 8:36 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Thanks Peter. I sense that I have offended you in some way, which was not my intention. You have made claims in robust and assertive language on several occassions, and I have therefore felt free to use similar language myself, because, as I have said repeatedly, I do not believe you have any grounds for the claims you have made (after all, this all started with your comments on Amazon, which appear now to have been removed, but which were quite stern - I seem to recall you accused Microsoft of dishonesty). I believe I have shown (with your help and correction above) that it is easy to run a simplistic test through an engine such as Jess as get the sort of results Microsoft got with their engine. I have addressed the issue of side effects elsewhere, which I am happy to agree is 'impure', but which does not invalidate the Rete algorithm implementation, and I have described in broad terms the undocumented classes and implementation that Microsoft has used in its engine. I have also addressed your recent concerns over the Assert class, which as I described on TSS, is not connected with the implementation of the rules engine, and pointed out that, because the classes in the Microsoft.RuleEngine.Rete namespace are undocumented, you cannot base your claims on Microsoft's implementation of Rete on the material contained on MSDN.

It may be that Microsoft has made some mistake, or even that they have wilfully attempted to mislead their developer community. I just can't see what grounds exist for thinking or claiming this.

This is a straight-forward disagreement. I hope we can continue to engage in useful debate in an open and friendly manner.
Left by Charles Young on Sep 17, 2005 9:21 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
It's getting late, but I've posted my results. After double checking the tests and reconstructing my original test, the results I saw were the result of bad methodology on my part. I've already apologized publicly on TSS.NET to all parties. The results I have do not show x increase in execute time as rule count increase by x. Instead, it is about 24-28% better.

I want to thank you for taking up my challenge. I respect you for that and sincerely thank you. I included some other tests, which demonstrate how RETE should perform. You can see results in the zip package.

peter lin
Left by Peter Lin on Sep 18, 2005 5:26 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Thanks Peter. My challenge then will be to reproduce your tests in MS-BRE and publish the results whatever the outcome. That way, we will hopefully be able to get some real evidence about the Rete implementation in Microsoft's product. It will take me a few days before I get this done.
Left by Charles Young on Sep 18, 2005 6:07 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
sounds great. I should warn you the file is pretty big and may take a while to download. I haven't been able to write up the results today, been super busy doing house work the entire day. Thanks again for giving me friendly kick in the butt.
Left by peter lin on Sep 18, 2005 6:42 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Here is the URL to download the file.
dingo.sourceforge.net/rete-benchmark.zip

I just wrote a new entry explaining how performance need not increase by x as ruleset size increase by x factor. woolfel.blogspot.com/2005/09/more-ideas-on-optimization-today-ive.html

I included pseduo-code to demonstrate how it would work. I haven't proven this idea experimentally, but is one of the several ideas I have been exploring the last 3 years. The debate inspired me to finally write down the idea. I plan to write up these and other optimizations for RETE later this year.

This particular optimization should mean that even for the 10K rule scenario with 1 object, the performance should be close to constant.
Left by Peter Lin on Sep 19, 2005 12:17 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Thank Peter - got it. I will have a look at some point in the next week or two.
Left by Charles Young on Sep 19, 2005 6:16 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
First of all, great work. And it is a good read.

But from an operational point of view where we maintain and test the business rules, would you ever recomend to a client to have a rule policy in place with more than a 1000 rules?

You know that if you modify one rule in a policy you can signifantly change the outcome of the inference engine. You might dissable a large part of the rule network, or you might created a conflict with just one other rule in the policy of 10.000 rules.

I can only imagine such a system when the rules are generated from data. But even then I wonder if an inference engine solution would be the best fit.



Left by Marco Ensing on Sep 20, 2005 2:16 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Most of the applications I know of first hand do not go beyond 1-2K rules. When it does, it means someone is naively writing rules like their writing procedural code, which means performance is going to be really bad.

This is one of the weakest areas of the rule engine domain. No one has managed to solve the rule writing/rule development problem really elegantly. the best product on the market today is iLog, but it's very expensive. As nice as iLog's tools are, it is still very hard for non-programmers to write good rules.

I'm told by one of the drools developers that iLog JRules actually implements the optimization I described in my blog and I believe ART implemented this style of optimization. Even though mindbox owns ART code base, it is not actively marketed. ART is written in C++ and it is still regarded by many experts to be the faster than all other RETE implementations.

I can't stress enough that RETE algorithm when implemented correctly can achieve phenominal performance even for cases where the network is very wide. There's no logical reason a RETE implementation can't handle 20K rules with just 5 object types and perform near constant rate. I've read several papers from commercial companies claiming RETE is slow or that it doesn't scale when the network is wide. I've made most of these mistakes first hand, only to realize it was my own stupidity that created the poor performance.

as far as removing rules. in a proper implementation, removing rules should not be a problem. Adding a rule may not be a problem. The critical factor in rule modification at runtime is whether or not the change results in an infinite loop. The only way I know how to handle that is to write a proof engine to validate the rule against the ruleset. The algorithm is straight forward, but the process is time intensive.
Left by Peter Lin on Sep 20, 2005 6:29 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
With regard to rule management, one of the slightly disappointing aspects of the current version of Microsoft's Rule Framework is that they appear to have pulled support for ruleset analysis before they shipped. In the beta stages of the development of the framework, Microsoft intended to provide support for ruleset anaysis components capable of performing "basic confluence, consistency and termination checks as well as identifying optimisations for ruleset execution".
Left by Charles Young on Sep 20, 2005 8:01 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
This is an interesting, and extensive analysis, but I think its time to move on from bickering over algorithms. If the Microsoft rule engine offers rule re-evaluation (the main benefit of operating in a RETE-like engine), then who cares how they implement the underlying algorithm as long as it performs well? Its unfortunate that a particular algorithm (RETE) has become synonomous with a particular type of rule engine, when in fact most vendors that have built such engines have made significant modifications to the published algorithm. The trend among leading vendors is to offer a choice of rule engine semantics - either re-evaluating or sequential. Fair Isaac Blaze Advisor did this first and now ILOG offers it as well.
Left by Alan Lewis on Sep 26, 2005 8:09 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
No problem with moving on. The argument was not about the relative merits of different algorithms, though. Rather, I was attempting to establish the true nature of the MS-BRE as a 'correct' Rete implementation against claims to the contrary. I know of at least one situation where the claims being made had a detrimental impact on a company's view of BizTalk Server.

The MS-BRE implements Rete in a straightforward manner, and offers no other model. However, what is not commonly understood is that the engine is a pluggable component within the MS Business Rules Framework. The <configuration> section of BRL (Microsoft's XML rule language) allows the specification of a 'translator' component. A translator component is responsible for translating rulesets (represented as in-memory object graphs, and typically created by the Rule Service, a 'rule store' component or custom code) into some executable format and handing processing off to an executor. The default translator translates to a Rete and invokes the MS-BRE. You can create alternative translators and executors as required, or even create bindings to existing third-party rule engines. So far, there is little sign of any momentum in terms of exploiting the Business Rules Framework, principally, I guess, because the Framework is only available currently via the BizTalk licence. Last I looked, the framework was also included with the forthcoming WWF (Windows Workflow Foundation), though I haven't checked the latest beta, so hopefully in time we will begin to see a much richer rules ecosystem grow around the BRF.
Left by Charles Young on Sep 27, 2005 9:35 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
I don't agree with this statement:

"The trend among leading vendors is to offer a choice of rule engine semantics - either re-evaluating or sequential. Fair Isaac Blaze Advisor did this first and now ILOG offers it as well."

the reason why iLog offers the options isn't performance, it's because of development. Writing rules so they perform well is very hard to learn and take a lot of time. Most businesses do not have experts in house and blame the rule engine. I've read the abstracts by ebay at this years semantic web conference and the problem appears to be development.

honestly, if the developers of a company can't think declaratively, then sequential engine is better. It's not practical or feasible to find an expert in many cases. To me, it makes sense to provide those options because each company is different and the learning curve is much too steep. Having worked on a large scale pre-trade compliance system, it can take years to teach developers how to think declaratively. In many cases from first hand experience, it's not feasible. Everyone has strengths and weaknesses, so it's not realistic to expect that any developer can just pick up a new approach in days and write great applications. For example, Corticon claims RETE rule engines are wrong. I've had discussions with the CEO of Corticon and clearly RETE is not the problem. The learning curve is the problem. Even though business rules industry has been around for 20 years, I think developing applications with rule engines is still 1/10th of where it needs to be. It still much too hard to write efficient rules that scale well. I'm totally biased and opinionate on this topic and I'm sure plenty of people will disagree with me.

in terms of Fair Issacs, they weren't the first. ART was one of the first to offer those kinds of features. I still haven't had to write up my results. I'm hoping next week I will have time.

peter
Left by peter lin on Oct 04, 2005 12:48 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
These are really good points. This thread prompted me to go and look at Beta 1 of the Microsoft Windows Workflow Foundation (WWF -see my comments above) which 'shipped' a couple of weeks ago. This public beta has dropped the integration of previous non-public betas with the MS Business Rules Framework, and has implemented a new sequential ruleset 'executor'. I've had quite a lot of discussion over the last few days with Jurgen Willis who is a member of the WWF product team with responsibility for implementing this new approach. He is very clear about why Microsoft are doing this - exactly the same reasons Peter is describing. WWF needs an approach that is easily understandable by, not only large numbers of developers, but also 'power users'. A declarative approach is just too much hard work.

WWF beta 1 offers no rule respository technology. Personally, I think WWF would really benefit from such a respository. We'll have to wait and see if MS thinks so too.

I've been writing this up, and plan to blog an article comparing and contrasting the two approaches in the next few days.
Left by Charles Young on Oct 04, 2005 5:58 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
You know that if you modify one rule in a policy you can signifantly change the outcome of the inference engine. You might dissable a large part of the rule network, or you might created a conflict with just one other rule in the policy of 10.000 rules.

Left by avatarlar on Jul 14, 2008 12:35 AM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
I can't stress enough that RETE algorithm when implemented correctly can achieve phenominal performance even for cases where the network is very wide. There's no logical reason a RETE implementation can't handle 20K rules with just 5 object types and perform near constant rate. I've read several papers from commercial companies claiming RETE is slow or that it doesn't scale when the network is wide. I've made most of these mistakes first hand, only to realize it was my own stupidity that created the poor performance
Left by Msn on Jul 17, 2008 8:47 PM

# re: Microsoft’s Rule Engine Scalability Results - A comparison with Jess and Drools
Requesting Gravatar...
Yeah, i agree, if you modify one rule in a policy you can signifantly change the outcome of the inference engine.
Left by Picture Frame on Jul 22, 2008 8:04 AM

Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net