Re: Significant Speedup of Generic Function Dispatch

From: Ken Anderson <kanderso_at_bbn.com>
Date: Sat, 13 Apr 1996 14:15:40 +0100

  
  **Thanks a lot**
  It's a long time I want to add a cache to the gf and never began to implement
  it. I will be really happy to integrate it in the next release.
  Thanks again.
  
I've been quite suprised that STklos has been useful without any
optimization beyond coding in C. Before adopting a particular strategy, i
recommend doing some profiling of typical applications to find out where
the time is really going. While generic dispatch is an obvious candidate,
so is slot-ref. Also the TK metaclass may require other specialized
optimizations.

While Davd McClain's approach is likely to be an improvement in many cases,
some generics, such as display-object perhaps, have calling patterns that
are not helped by caching the most recently used applicable methods lists.
A slightly larger cache of two or three recent ones might also help. Of
course, this just adds to the cost if there is a total cache miss.

Let me describe a method lookup strategy i've been meaning to play with for
some time. The basic idea is to use a discrimination net to store the
applicable methods This net would be computed as each method is added.
Heres and example for the single argument case using describe. Describe in
the STk i'm running has 3 methods:
  
 #[<method> describe (<class>) #pbf2a4]
 #[<method> describe (<object>) #pc0564]
 #[<method> describe (<top>) #pc1458])

The discrimination net could look like:

((#[<class> <class>]
  (#t #[<method> describe (<class>) #pbf2a4]
      #[<method> describe (<object>) #pc0564]
      #[<method> describe (<top>) #pc1458]))
 (#[<class> <object>]
  (#t #[<method> describe (<object>) #pc0564]
      #[<method> describe (<top>) #pc1458]))
 (#[<class> <top>]
  (#t #[<method> describe (<top>) #pc1458])))

Then for a class like:

STk> (define-class <frog> () ())
#[undefined]

To find the appropriate methods, look for the first element in the list
who's car is a superclass of <frog>, <object> here. If there were more
than one argument you would continue searching that branch.

The net is order by length of class precedence list (longest first). Thus
you search more specific classes first. In the worst case you need to look
at the whole list (as the current lookup method does) but you don't need to
cons up a new list of applicable methods each time. For the common case of
a small number (1?) of methods performance should be similar to David
McClain's approach.

The CLOS approach of using a state machine that chooses an appropriate
discriminating function would be worth looking at too.
Received on Sat Apr 13 1996 - 20:19:13 CEST