Caching of Effective Methods

The overhead caused by method lookup is present in the single inheritance as well as in the multiple inheritance case. However, the overhead may be outrageous when using method combination, along the lines described in section . A message sending primitive (a generic function call) causes extensive searching in the class hierarchy for the necessary methods. In this section I will sketch a simple caching technique that can alleviate some of these problems.

Instead of using method-combination in, for instance, send , the following procedure with an identical parameter profile is used.

(define (get-method-combination object message)
  (let ((cached-effective-method (get object message)))
    (if cached-effective-method
        cached-effective-method
        (let ((effective-method (method-combination object message)))
          (put object message effective-method)
          effective-method))))

The get and put primitives access and mutate a two-dimensional table (see, e.g., [1]).

The first time a particular method (identified by method ) in a particular object is called, the effective method is being cached. Subsequent activations of the same method in the same object do not compute the method combination; rather, the cached value of the effective method is used.

It would have been more natural to cache the effective method on the class rather than on the objects of the class. In that way all instances of the same class could share the cached method. However, two instances of the same class do not share the procedure objects, which simulate the methods. Each instance has its own, local procedure objects. (This is, by the way, what makes it possible to represent an object as a ``dispatch procedure''). In that way also the effective method becomes specific to one and only one instance of a class. For more details about this problem, and for elements of a solution, see [2].

Empirical measurements indicate that the caching strategy pays well off with respect to time consumption. In an example where an effective method was formed by two before methods, three after methods, and a primary method, the caching technique was 10 to 20 times faster than without caching.

When a new method that contributes to an effective method is being introduced, it is important to get rid of the cached value. In the framework of this report, it would make sense to clear the cache of all methods of an object, upon redefinition of the class. In turn, this requires that we can get our hand on all instances of a class. This kind of administration may very well turn out to be more complicated than the caching proper.