25 Nov 2012 crhodes   » (Master)

In the last episode, we discovered some things about the implementation of discriminating functions in SBCL's CLOS, and also I discovered that I had actually documented some of it many years ago in the SBCL Internals manual: as well as the chapter on discriminating functions, there's some interesting stuff about how to make slot-value tolerably efficient. And so I sent Faré the functions for precompiling generic functions, and congratulated myself on a job well done.

And inevitably I got a reply, by return: “it looks like this doesn't work with eql-specializers.” Also “our generic functions have 417 eql-specializers between them.” Ah.

Faré is quite right, the code in the previous diary entry will signal an error on finding a method with eql specializers – and even if it were fixed to not have that problem, the underlying (cacheing) mechanism for efficient method calls, based on looking at the identity of the class-of each argument, fails to work when there are applicable methods with eql specializers (because the set of applicable methods for arguments of a class will vary on whether the argument matches an eql-specializer or not).

So, it is perhaps not surprising that there is an alternative optimized discriminating function mechanism which comes into play if a generic function has a substantial number of methods with eql-specializers: instead of a cacheing discriminating function, we generate and use a dispatching discriminating function, which generates a network of type tests to distinguish between all the possible cases of applicable methods, based on the actual types of the arguments – and importantly in this context, those types can include eql types.

The same sort of support exists in SBCL for constructing a dispatching discriminating function in advance as I presented for constructing a cacheing discriminating function. Something like the following:

(defun precompile-dispatching-gf (gf)
  (let* ((lock (sb-pcl::gf-lock gf)))
    (setf (sb-pcl::gf-precompute-dfun-and-emf-p (sb-pcl::gf-arg-info gf)) t)
    (multiple-value-bind (dfun cache info)
        (sb-pcl::make-final-dispatch-dfun gf)
      (sb-thread::call-with-recursive-system-lock ; or -SPINLOCK
       (lambda () 
         (sb-pcl::set-dfun gf dfun cache info)
         (sb-mop:set-funcallable-instance-function gf dfun))

(loop for x being the external-symbols of :cl
      initially (progn (fmakunbound 'bar) (fmakunbound 'baz)
                       (defgeneric bar (y z)) (defgeneric baz (y z)))
      do (eval `(defmethod bar ((y (eql ',x)) z) (list y z)))
         (eval `(defmethod baz ((y (eql ',x)) z) (list y z))))

(precompile-dispatching-gf #'bar)

(time (bar 'defmethod 3)) ; 6,250 processor cycles
(time (baz 'defmethod 3)) ; 1,098,642,785 processor cycles

I suppose that would make a noticeable difference to application startup times. Next up, unless I've made further oversights which need correction: automating this process, and some incidental thoughts.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!