doc/internals/discriminating-functions.texinfo

   1 @node Discriminating Functions
   2 @comment  node-name,  next,  previous,  up
   3 @chapter Discriminating Functions
   4
   5 @menu
   6 * The Initial Discriminating Function::
   7 * Method-Based Discriminating Functions::
   8 * Accessor Discriminating Functions::
   9 * Cacheing and Dispatch Functions::
  10 * The Cacheing Mechanism::
  11 @end menu
  12
  13 The Common Lisp Object System specifies a great deal of run-time
  14 customizeability, such as class redefinition, generic function and
  15 method redefinition, addition and removal of methods and redefinitions
  16 of method combinations.  The additional flexibility defined by the
  17 Metaobject Protocol, specifying the generic functions called to achieve
  18 the effects of CLOS operations (and allowing many of them to be
  19 overridden by the user) makes any form of optimization seem intractable.
  20 And yet such optimization is necessary to achieve reasonable
  21 performance: the MOP specifies that a slot access looks up the class of
  22 the object, and the slot definition from that class and the slot name,
  23 and then invokes a generic function specialized on those three
  24 arguments.  This is clearly going to act against the user's intuition
  25 that a slot access given an instance should be relatively fast.
  26
  27 The optimizations performed cannot be done wholly at compile-time,
  28 however, thanks to all of these possibilities for run-time redefinition
  29 and extensibility.  This section describes the optimizations performed
  30 in SBCL's CLOS implementation in computing and calling the effective
  31 method for generic functions.
  32
  33 @node The Initial Discriminating Function
  34 @comment  node-name,  next,  previous,  up
  35 @section The Initial Discriminating Function
  36
  37 @findex compute-discriminating-function
  38 @findex sb-mop:compute-discriminating-function
  39
  40 The system method on @code{SB-MOP:COMPUTE-DISCRIMINATING-FUNCTION},
  41 under most circumstances, returns a function which closes over a
  42 structure of type @code{SB-PCL::INITIAL}, and which calls
  43 @code{SB-PCL::INITIAL-DFUN}.  This discriminating function is
  44 responsible for implementing the computation of the applicable methods,
  45 the effective method, and thence the result of the call to the generic
  46 function.  In addition, it implements optimization of these steps, based
  47 on the arguments it has been called with since the discriminating
  48 function was installed and the methods of the generic function.
  49
  50 @float Figure,fig:dfun-transitions
  51 @image{discriminating-functions}
  52 @end float
  53
  54 For each substantive change of the generic function (such as addition or
  55 removal of a method, or other reinitialization) the discriminating
  56 function is reset to its initial state.
  57
  58 The initial discriminating function can transition into a discriminating
  59 function optimized for the methods on the generic function
  60 (@code{SB-PCL::NO-METHODS}, @code{SB-PCL::DEFAULT-METHOD-ONLY},
  61 @code{SB-PCL::CONSTANT-VALUE}), for slot access
  62 (@code{SB-PCL::ONE-CLASS}, @code{SB-PCL::TWO-CLASS},
  63 @code{SB-PCL::ONE-INDEX}, @code{SB-PCL::N-N}@footnote{Would be better
  64 named as @code{M-N}, as there is no requirement for the number of
  65 classes and number of indices to be the same.}), or for dispatch based
  66 on its arguments (@code{SB-PCL::CACHING}, @code{SB-PCL::DISPATCH}).
  67 Those in the second category can transition into the third, or into a
  68 @code{SB-PCL::CHECKING} state where the choice between
  69 @code{SB-PCL::CACHING} and @code{SB-PCL::DISPATCH} has not yet been
  70 made.
  71
  72 The possible transitions are shown in @ref{fig:dfun-transitions}.
  73
  74 @node Method-Based Discriminating Functions
  75 @comment  node-name,  next,  previous,  up
  76 @section Method-Based Discriminating Functions
  77
  78 @findex no-applicable-method
  79
  80 The method-based discriminating functions are used if all the methods of
  81 the generic function at the time of the first call are suitable:
  82 therefore, these discriminating function strategies do not transition
  83 into any of the other states unless the generic function is
  84 reinitialized.  Of these discriminating functions, the simplest is the
  85 @code{SB-PCL::NO-METHODS}, which is appropriate when the generic
  86 function has no methods.  In this case, the discriminating function
  87 simply performs an argument count check@footnote{Actually, this bit
  88 isn't currently done.  Oops.} and then calls
  89 @code{NO-APPLICABLE-METHOD} with the appropriate arguments.
  90
  91 If all of the specializers in all methods of the generic function are
  92 the root of the class hierarchy, @code{t}, then no discrimination need
  93 be performed: all of the methods are applicable on every
  94 call@footnote{Hm, there might be another problem with argument count
  95 here.}.  In this case, the @code{SB-PCL::DEFAULT-METHOD-ONLY}
  96 discriminating function can call the effective method directly, as it
  97 will be the same for every generic function call.@footnote{I wonder if
  98 we're invalidating this right if we define a method on
  99 compute-applicable-methods...}
 100
 101 If all methods of the generic function are known by the system to be
 102 side-effect-free and return constants, and the generic function has
 103 standard-method-combination and no eql-specialized methods, then the
 104 @code{SB-PCL::CONSTANT-VALUE} discriminating function can simply cache
 105 the return values for given argument types.  Though this may initially
 106 appear to have limited applicability, type predicates are usually of
 107 this form, as in @ref{ex:pred}@footnote{There is vestigial code in SBCL
 108 for a currently unused specialization of @code{SB-PCL::CONSTANT-VALUE}
 109 for boolean values only.}.
 110
 111 @float Example,ex:pred
 112 @example
 113 (defgeneric foop (x))
 114 (defmethod foop ((foo foo)) t)
 115 (defmethod foop (object) nil)
 116 @end example
 117 @end float
 118
 119 More details of the cacheing mechanism are given in @ref{The Cacheing
 120 Mechanism} below.
 121
 122 @node Accessor Discriminating Functions
 123 @comment  node-name,  next,  previous,  up
 124 @section Accessor Discriminating Functions
 125
 126 Accessor Discriminating Functions are used when the effective method of
 127 all calls is an access to a slot, either reading, writing or checking
 128 boundness@footnote{Although there is ordinarily no way for a user to
 129 define a boundp method, some automatically generated generic functions
 130 have them.}; for this path to apply, there must be no non-standard
 131 methods on @code{SB-MOP:SLOT-VALUE-USING-CLASS} and its siblings.  The
 132 first state is @code{SB-PCL::ONE-CLASS}, entered when one class of
 133 instance has been accessed; the discriminating function here closes over
 134 the wrapper of the class and the slot index, and accesses the slot of
 135 the instance directly.
 136
 137 If a direct instance of another class is passed to the generic function
 138 for slot access, then another accessor discriminating function is
 139 created: if the index of the slot in the slots vector of each instance
 140 is the same, then a @code{SB-PCL::TWO-CLASS} function is created,
 141 closing over the two class wrappers and the index and performing the
 142 simple dispatch.  If the slot indexes are not the same, then we go to
 143 the @code{SB-PCL::N-N} state.
 144
 145 For slot accesses for more than two classes with the same index, we move
 146 to the @code{SB-PCL::ONE-INDEX} state which maintains a cache of
 147 wrappers for which the slot index is the same.  If at any point the slot
 148 index for an instance is not the same, the state moves to
 149 @code{SB-PCL::N-N}, which maintains a cache of wrappers and their
 150 associated indexes; if at any point an effective method which is not a
 151 simple slot access is encountered, then the discriminating function
 152 moves into the @code{SB-PCL::CHECKING}, @code{SB-PCL::CACHING} or
 153 @code{SB-PCL::DISPATCH} states.
 154
 155 @node Cacheing and Dispatch Functions
 156 @comment  node-name,  next,  previous,  up
 157 @section Cacheing and Dispatch Functions
 158
 159 @code{SB-PCL::CACHING} functions simply cache effective methods as a
 160 function of argument wrappers, while @code{SB-PCL::DISPATCH} functions
 161 have code that computes the actual dispatch.  @code{SB-PCL::CHECKING}
 162 functions have a cache, but on cache misses will recompute whether or
 163 not to generate a @code{SB-PCL::CACHING} or @code{SB-PCL::DISPATCH}
 164 function.
 165
 166 (FIXME: I'm actually not certain about the above paragraph.  Read the
 167 code again and see if it makes any more sense.)
 168
 169 @node The Cacheing Mechanism
 170 @comment  node-name,  next,  previous,  up
 171 @section The Cacheing Mechanism
 172
 173 In general, the cacheing mechanism works as follows: each class has an
 174 associated wrapper, with some number of uniformly-distributed random
 175 hash values associated with it; each cache has an associated index into
 176 this pseudovector of random hash values.  To look a value up from a
 177 cache from a single class, the hash corresponding to the cache's index
 178 is looked up and reduced to the size of the cache (by bitmasking, for
 179 cache sizes of a power of two); then the entry at that index is looked
 180 up and compared for identity with the wrapper in question.  If it
 181 matches, this is a hit; otherwise the cache is walked sequentially from
 182 this index, skipping the 0th entry.  If the original index is reached,
 183 the cache does not contain the value sought@footnote{Actually, there's
 184 some kind of scope for overflow.}.
 185
 186 To add an entry to a cache, much the same computation is executed.
 187 However, if there is a collision in hash values, before the cache is
 188 grown, an attempt is made to fill the cache using a different index into
 189 the wrappers' hash values.
 190
 191 Wrappers are invalidated for caches by setting all of their hash values
 192 to zero.  (Additionally, they are invalidated by setting their
 193 @code{depthoid} to -1, to communicate to structure type testers, and
 194 their @code{invalid} to non-@code{nil}, communicating to
 195 @code{obsolete-instance-trap}.
 196
 197 The hash value for multiple dispatch is computed by summing all of the
 198 individual hash values from each wrapper (excluding arguments for which
 199 all methods have @code{t} specializers, for which no dispatch
 200 computation needs to be done), jumping to the cache miss case if any
 201 wrapper has a zero hash index.
 202
 203 (FIXME: As of sbcl-0.9.x.y, the generality of multiple hash values per
 204 wrapper was removed, as it appeared to do nothing in particular for
 205 performance in real-world situations.)
 206
 207 References (O for working BibTeX):
 208
 209 The CLOS standards proposal
 210
 211 Kiczales and Rodruigez
 212
 213 AMOP