Benchmarking OPSJ

Production Systems Technologies, Inc.

Abstract: OPSJ is a rule-based programming system implemented in JAVA. Because current JAVA implementations do not permit JAVA programs to execute as fast as comparable programs written in C or C++, special care was taken to provide the most efficient implementation possible for OPSJ. OPSJ uses the proprietary Rete II algorithm, a very advanced version of the industry-standard Rete algorithm. This whitepaper describes the results of benchmarking OPSJ against a typical C-based system that uses standard Rete, CLIPS 6.10. Only standard, independently-developed benchmark programs were run. The tests showed that OPSJ is slightly faster than CLIPS 6.10 on simple problems, while on very complex problems it is more than a hundred times faster than the system that uses standard Rete.

Introduction

This whitepaper describes the results of benchmarking OPSJ against a popular standard-Rete system, CLIPS 6.10, written in C. Two benchmark programs are used, Waltz and Manners. Both of these programs permit the amount of data operated on by the rules to be varied. By increasing the amount of data, these benchmarks can be scaled from fairly simple to quite complex. These programs were all independently developed; to insure the fairness of the results, we are not using any benchmarks written by Production Systems Technologies.

The tests were run on an Intel Pentium 3 system under Microsoft Windows. The OPSJ system was run under SUN’s JDK 1.4.1. The CLIPS system was compiled with Microsoft’s Visual C++ compiler. The OPSJ system was compiled with the “-O” (optimize) switch. The CLIPS system was compiled with the “-O2” (optimize for maximize speed) switch. To insure the accuracy of the results, all systems that took less than 1 second were run 10 times, and the run times were averaged.

The Manners Benchmark

The Manners benchmark program is from the suite of benchmarks collected by Dr. Daniel Miranker's group at the University of Texas. Manners scales by increasing the number of working memory elements the rules have to deal with. In the smallest problem reported below, working memory has an average of about 400 objects. In the biggest problem, working memory averages over 1900 objects. At times during the runs for the bigger problems, the conflict set can also grow large, though the average size of the conflict set for even the longest run is less than 100 activations.

Manners assigns seats to guests at a dinner party, seating people on the basis of their genders and their interests. It attempts to put people of different sexes and with common hobbies next to each other. The amount of work this program does depends on the number of guests at the party. We ran this problem with from 32 to 128 guests. The results are shown in Table 1.

Guests	Rules Fired	CLIPS 6.10 Run Time (sec)	OPSJ Run Time (sec)	Relative Speed
32	624	1.3	0.9	1.8
64	2272	40.4	1.6	25.3
128	8640	4087	12.6	324.4

Table 1. Run Times for CLIPS 6.10 and OPSJ on Manners.

Note that OPSJ's speed advantage increases as the problem scales up. This is due to the Rete II algorithm used by OPSJ. Rete II is better able to handle large working memories and large numbers of full and partial rule matches than the earlier algorithm.

The Waltz Benchmark

The Waltz benchmark program also comes from the University of Texas benchmark suite. Like Manners, this program has a fixed number of rules, and scaling is achieved by giving the program bigger and bigger problems to work on. The condition parts of the rules in this system are more complex than the conditions in Manners.

This program performs Waltz labeling. That is, it is presented with a collection of lines such as might be found by an edge detector in a computer vision system. It applies a set of constraints to the lines in order to create a labeling for them. The labels indicate how the lines correspond to edges in a three-dimensional scene.

Four runs of this program were made, with the number of regions to be labeled varying from 12 to 50. Unlike the other program, Waltz produces a large amount of output. The amount of output would be sufficient to skew the results for the smaller problems. As it comes from the University of Texas benchmark library, the program has the output statements commented out. For the timing runs, we left them commented out. As with the Manners benchmark, OPSJ was faster than CLIPS 6.10 on all examples, and its speed advantage was greatest with the most complex problems.

Regions	Rules Fired	CLIPS Run Time (seconds)	OPSJ Run Time (seconds)	Relative Speed
12	3578	13.8	0.4	34.5
25	7166	81.9	0.9	91.0
37	10,478	187.8	1.5	125.2
50	14,066	345.6	2.2	157.1

Table 2. Run Times for CLIPS 6.10 and OPSJ on Waltz.

Conclusions

These benchmark programs test the ability of rule based systems to deal with large working memories and large numbers of full and partial matches for the rules. Benchmarks of this nature are interesting because they are the best predictors of how well a rule interpreter can handle complex rule bases. When a rule-based system has performance problems, it is almost always the result of the rules having to deal with more data than the match algorithm can handle efficiently. (The number of rules in the system does not affect performance much in modern systems because standard algorithms can easily handle large numbers of rules.)

Rete II was developed specifically to make it possible for rule systems to deal efficiently with large amounts of data as well as large numbers of rules. As the tables above illustrate, OPSJ is dramatically faster than CLIPS 6.10 on problems involving large amounts of data.

We wish to express our appreciation to Dr. Miranker and his associates at the University of Texas for creating the rule benchmark suite and making it available to the community at large.

[ Home ] [ OPS/J ] [ CLIPS/R2 ] [ OPS/R2 ] [ RETE-II ] [ About PST ] [ Users ] [ Licensing ] [ Legal Issues ]