next up previous

Appendix C Performance Considerations

This appendix explains various techniques that the user can apply to a CLIPS program to maximize performance. Included are discussions of pattern ordering in rules, use of deffunctions in lieu of nonoverloaded generic functions, parameter restriction ordering in generic function methods, and various approaches to improving the speed of messagepassing and reading slots of instances.

C.1 ORDERING OF PATTERNS ON THE LHS

The issues which affect performance of a rulebased system are considerably different from those which affect conventional programs. This section discusses the single most important issue: the ordering of patterns on the LHS of a rule.

CLIPS is a rule language based on the RETE algorithm. The RETE algorithm was designed specifically to provide very efficient patternmatching. CLIPS has attempted to implement this algorithm in a manner that combines efficient performance with powerful features. When used properly, CLIPS can provide very reasonable performance, even on microcomputers. However, to use CLIPS properly requires some understanding of how the patternmatcher works.

Prior to initiating execution, each rule is loaded into the system and a network of all patterns that appear on the LHS of any rule is constructed. As facts and instances of reactive classes (referred to collectively as pattern entities) are created, they are filtered through the pattern network. If the pattern entities match any of the patterns in the network, the rules associated with those patterns are partially instantiated. When pattern entities exist that match all patterns on the LHS of the rule, variable bindings (if any) are considered. They are considered from the top to the bottom; i.e., the first pattern on the LHS of a rule is considered, then the second, and so on. If the variable bindings for all patterns are consistent with the constraints applied to the variables, the rules are activated and placed on the agenda.

This is a very simple description of what occurs in CLIPS, but it gives the basic idea. A number of important considerations come out of this. Basic patternmatching is done by filtering through the pattern network. The time involved in doing this is fairly constant. The slow portion of basic patternmatching comes from comparing variable bindings across patterns. Therefore, the single most important performance factor is the ordering of patterns on the LHS of the rule. Unfortunately, there are no hard and fast methods that will always order the patterns properly. At best, there seem to be three ìquasiî methods for ordering the patterns.

1) Most specific to most general. The more wildcards or unbound variables there are in a pattern, the lower it should go. If the rule firing can be controlled by a single pattern, place that pattern first. This technique often is used to provide control structure in an expert system; e.g., some kind of ìphaseî fact. Putting this kind of pattern first will guarantee that the rest of the rule will not be considered until that pattern exists. This is most effective if the single pattern consists only of literal constraints. If multiple patterns with variable bindings control rule firing, arrange the patterns so the most important variables are bound first and compared as soon as possible to the other pattern constraints. The use of phase facts is not recommended for large programs if they are used solely for controlling the flow of execution (use modules instead).

2) Patterns with the lowest number of occurrences in the factlist or instancelist should go near the top. A large number of patterns of a particular form in the factlist or instancelist can cause numerous partial instantiations of a rule that have to be ìweededî out by comparing the variable bindings, a slower operation.

3) Volatile patterns (ones that are retracted and asserted continuously) should go last, particularly if the rest of the patterns are mostly independent. Every time a pattern entity is created, it must be filtered through the network. If a pattern entity causes a partial rule instantiation, the variable bindings must be considered. By putting volatile patterns last, the variable bindings only will be checked if all of the rest of the patterns already exist.

These rules are not independent and commonly conflict with each other. At best, they provide some rough guidelines. Since all systems have these characteristics in different proportions, at a glance the most efficient manner of ordering patterns for a given system is not evident. The best approach is to develop the rules with minimal consideration of ordering. When the reasoning is fairly well verified, experiment with the patterns until the optimum configuration is found.

Another performance issue is the use of multifield variables and wildcards ($?). Although they provide a powerful capability, they must be used very carefully. Since they can bind to zero or more fields, they can cause multiple instantiations of a single rule. In particular, the use of multiple multifield variables in one pattern can cause a very large number of instantiations.

Some final notes on rule performance. Experience suggests that the user should keep the expert system ìlean and mean.î The list of pattern entities should not be used as a data base for storage of extraneous information. Store and patternmatch only on that information necessary for reasoning. Keep the patternmatching to a minimum and be as specific as possible. Many short, simple rules perform better than long, complex rules and have the added benefit of being easier to understand and maintain.

C.2 DEFFUNCTIONS VERSUS GENERIC FUNCTIONS

Deffunctions execute more quickly than generic function because generic functions must first examine their arguments to determine which methods are applicable. If a generic function has only one method, a deffunction probably would be better. Care should be taken when determining if a particular function truly needs to be overloaded. In addition, if recompiling and relinking CLIPS is not prohibitive, userdefined external functions are even more efficient than deffunctions. This is because deffunction are interpreted whereas external functions are directly executed. For more details, see sections 7 and 8.2.

C.3 ORDERING OF METHOD PARAMETER RESTRICTIONS

When the generic dispatch examines a generic functionís method to determine if it is applicable to a particular set of arguments, it examines that methodís parameter restrictions from left to right. The programmer can take advantage of this by placing parameter restrictions which are less frequently satisfied than others first in the list. Thus, the generic dispatch can conclude as quickly as possible when a method is not applicable to a generic function call. If a group of restrictions are all equally likely to be satisfied, placing the simpler restrictions first, such as those without queries, will also allow the generic dispatch to conclude more quickly for a method that is not applicable. For more details, see section 8.4.3.

C.4 INSTANCEADDRESSES VERSUS INSTANCENAMES

COOL allows instances of userdefined classes to be referenced either by address or by name in functions which manipulate instances, such as messagepassing with the send function. However, when an instance is referenced by name, CLIPS must perform an internal lookup to find the instanceaddress anyway. If the same instance is going to be manipulated many times, it might be advantageous to store the instanceaddress and use that as a reference. This will allow CLIPS to always go directly to the instance. For more details, see sections 2.4.2 and 12.16.4.6.

C.5 READING INSTANCE SLOTS DIRECTLY

Normally, messagepassing must be used to read or set a slot of an instance. However, slots can be read directly within instanceset queries and messagehandlers, and they can be set directly within messagehandlers. Accessing slots directly is significantly faster than messagepassing. Unless messagepassing is required (because of slot daemons), direct access should be used when allowed. For more details, see sections 9.4.2, 9.4.3, 9.4.4, 9.6.3, 9.6.4 and 9.7.3.




next up previous