+ :PROPERTIES:
+ :CUSTOM_ID: Protocol
+ :END:
+
+ In section [[#Examples]], we have seen a number of code fragments as
+ partial implementations of particular non-standard method dispatch,
+ using =generalizer= metaobjects to mediate between the methods of
+ the generic function and the actual arguments passed to it. In
+ section [[#Generalizer metaobjects]], we go into more detail regarding
+ these =generalizer= metaobjects, describing the generic function
+ invocation protocol in full, and showing how this protocol allows a
+ similar form of effective method cacheing as the standard one does.
+ In section [[#Generalizer performance]], we show the results of some
+ simple performance measurements to highlight the improvement that
+ this protocol can bring over a naïve implementation of generalized
+ dispatch, as well as highlighting the potential for further
+ improvement.
+
+** Generalizer metaobjects
+ :PROPERTIES:
+ :CUSTOM_ID: Generalizer metaobjects
+ :END:
+
+*** Generic function invocation
+ As in the standard generic function invocation protocol, the
+ generic function's actual functionality is provided by a
+ discriminating function. The functionality described in this
+ protocol is implemented by having a distinct subclass of
+ =standard-generic-function=, and a method on
+ =compute-discriminating-function= which produces a custom
+ discriminating function. The basic outline of the discriminating
+ function is the same as the standard one: it must first compute the
+ set of applicable methods given particular arguments; from that, it
+ must compute the effective method by combining the methods
+ appropriately according to the generic function's method
+ combination; finally, it must call the effective method with the
+ arguments.
+
+ Computing the set of applicable methods is done using a pair of
+ functions: =compute-applicable-methods=, the standard metaobject
+ function, and a new function
+ =compute-applicable-methods-using-generalizers=. We define a
+ custom method on =compute-applicable-methods= which tests the
+ applicability of a particular specializer against a given argument
+ using =specializer-accepts-p=, a new protocol function with
+ default implementations on =class= and =eql-specializer= to
+ implement the expected behaviour. In order to order the methods,
+ as required by the protocol, we define a pairwise comparison
+ operator =specializer<= which defines an ordering between
+ specializers for a given generalizer argument (remembering that
+ even in standard CLOS the ordering between =class= specializers
+ can change depending on the actual class of the argument).
+
+ The new =compute-applicable-methods-using-generalizers= is the
+ analogue of the MOP's =compute-applicable-methods-using-classes=.
+ Instead of calling it with the =class-of= each argument, we compute
+ the generalizers of each argument using the new function
+ =generalizer-of-using-class= (where the =-using-class= refers to
+ the class of the generic function rather than the class of the
+ object), and call it with the list of generalizers. As with the
+ standard function, a secondary return value indicates whether the
+ result of the function is definitive for that list of generalizers.
+
+ Thus, in generic function invocation, we first compute the
+ generalizers of the arguments; we compute the ordered set of
+ applicable methods, either from the generalizers or (if that is
+ not definitive) from the arguments themselves; then the normal
+ effective method computation and call can occur. Unfortunately,
+ the nature of an effective method object is not specified, so we
+ have to reach into implementation internals a little in order to
+ call it, but otherwise the remainder of the generic function
+ invocation protocol is unchanged from the standard one. In
+ particular, method combination is completely unchanged;
+ programmers can choose arbitrary method combinations, including
+ user-defined long form combinations, for their generic functions
+ involving generalized dispatch.
+
+*** Effective method memoization
+ :PROPERTIES:
+ :CUSTOM_ID: Memoization
+ :END:
+ The potential efficiency benefit to having =generalizer=
+ metaobjects lies in the use of
+ =compute-applicable-methods-using-generalizers=. If a particular
+ generalized specializer accepts a variety of objects (such as the
+ =signum= specializer accepting all reals with a given sign, or the
+ =accept= specializer accepting all HTTP requests with a particular
+ =Accept= header), then there is the possibility of cacheing and
+ reusing the results of the applicable and effective method
+ computation. If the computation of the applicable method from
+ =compute-applicable-methods-using-generalizers= is definitive,
+ then the ordered set of applicable methods and the effective
+ method can be cached.
+
+ One issue is what to use as the key for that cache. We cannot use
+ the generalizers themselves, as two generalizers that should be
+ considered equal for cache lookup will not compare as =equal= –
+ and indeed even the standard generalizer, the =class=, cannot be
+ used as we must be able to invalidate cache entries upon class
+ redefinition. The issue of =class= generalizers we can solve as
+ in \cite{Kiczales.Rodriguez:1990} by using the =wrapper= of a
+ class, which is distinct for each distinct (re)definition of a
+ class; for arbitrary generalizers, however, there is /a priori/ no
+ good way of computing a suitable hash key automatically, so we
+ allow the metaprogrammer to specify one by defining a method on
+ =generalizer-equal-hash-key=, and combining the hash keys for all
+ required arguments in a list to use as a key in an =equal=
+ hash-table.
+
+ [XXX could we actually compute a suitable hash key using the
+ generalizer's class name and initargs?]
+
+ - [X] =generalizer-of-using-class= (NB class of gf not class of object)
+ - [X] =compute-applicable-methods-using-generalizers=
+ - [X] =generalizer-equal-hash-key=
+ - [X] =specializer-accepts-generalizer-p=
+ - [X] =specializer-accepts-p=
+ - [X] =specializer<=
+** Performance
+ :PROPERTIES:
+ :CUSTOM_ID: Generalizer performance
+ :END:
+ We have argued that the protocol presented here allows for
+ expressive control of method dispatch while preserving the
+ possibility of efficiency. In this section, we quantify the
+ efficiency that the memoization protocol described in section
+ [[#Memoization]] achieves, by comparing it both to the same protocol
+ with no memoization, as well as with equivalent dispatch
+ implementations in the context of methods with regular
+ specializers, and with implementation in straightforward functions.
+
+ In the case of the =cons-specializer=, we benchmark the walker
+ acting on a small but non-trivial form. The implementation
+ strategies in the table below refer to: an implementation in a
+ single function with a large =typecase= to dispatch between all the
+ cases; the natural implementation in terms of a standard generic
+ function with multiple methods (the method on =cons= having a
+ slightly reduced =typecase= to dispatch on the first element, and
+ other methods handling =symbol= and other atoms); and three
+ separate cases using =cons-specializer= objects. As well as
+ measuring the effect of memoization against the full invocation
+ protocol, we can also introduce a special case: when only one
+ argument participates in method selection (all the other required
+ arguments only being specialized on =t=), we can avoid the
+ construction of a list of hash keys and simply use the key
+ from the single active generalizer directly.
+
+ Refer to \cite{Kiczales.Rodriguez:1990}
+
+ | implementation | time (µs/call) | overhead |
+ |-----------------------+----------------+----------|
+ | function | 3.17 | |
+ | standard-gf/methods | 3.6 | +14% |
+ | cons-gf/one-arg-cache | 7.4 | +130% |
+ | cons-gf | 15 | +370% |
+ | cons-gf/no-cache | 90 | +2700% |
+
+ The benchmarking results from this exercise are promising: in
+ particular, the introduction of the effective method cache speeds
+ up the use of generic specializers in this case by a factor of 6,
+ and the one-argument special case by another factor of 2. For this
+ workload, even the one-argument special case only gets to within a
+ factor of 2-3 of the function and standard generic function
+ implementations, but the overall picture is that the memoizability
+ in the protocol does indeed drastically reduce the overhead
+ compared with the full invocation.
+
+ For the =signum-specializer= case, we choose to benchmark the
+ computation of 20!, because that is the largest factorial whose
+ answer fits in SBCL's 63-bit fixnums – in an attempt to measure the
+ worst case for generic dispatch, where the work done within the
+ methods is as small as possible without being meaningless, and in
+ particular does not cause allocation or garbage collection to
+ obscure the picture.
+
+#+begin_src lisp :exports none
+(progn (gc :full t) (time (dotimes (i 10000) (%fact 20))))
+#+end_src
+
+ | implementation | time (µs/call) | overhead |
+ |-------------------------+----------------+----------|
+ | function | 0.6 | |
+ | standard-gf/fixnum | 1.2 | +100% |
+ | signum-gf/one-arg-cache | 7.5 | +1100% |
+ | signum-gf | 23 | +3800% |
+ | signum-gf/no-cache | 240 | +41000% |
+
+ The relative picture is similar to the =cons-specializer= case;
+ including a cache saves a factor of 10 in this case, and another
+ factor of 3 for the one-argument cache special case. The cost of
+ the genericity of the protocol here is starker; even the
+ one-argument cache is a factor of 6 slower than the standard
+ generic-function implementation, and a further factor of 2 away
+ from the implementation of factorial as a function. We discuss
+ ways in which we expect to be able to improve performance in
+ section [[#Future Work]].
+
+ We could allow the metaprogrammer to improve on the one-argument
+ performance by constructing a specialized cache: for =signum=
+ arguments of =rational= arguments, the logical cache structure is
+ to index a three-element vector with =(1+ signum)=. The current
+ protocol does not provide a way of eliding the two generic function
+ calls for the generic cache; we discuss possible approaches in
+ section [[#Conclusions]].