Fast Generic Functions

This library introduces fast generic functions, i.e., functions that behave just like regular generic functions, except that the can be sealed on certain domains. If the compiler can then statically detect that the arguments to a fast generic function fall within such a domain, it will perform a variety of optimizations.

Example 1 - Generic Find

This example illustrates how one can define a (hopefully) fast method for finding items in a sequence.

The first step is to define a generic function whose generic function class is fast-generic-function.

(defgeneric generic-find (item sequence &key test)
  (:generic-function-class fast-generic-functions:fast-generic-function))

Once this definition is loaded (and only then, so you shouldn’t put the next snippets in the same file as the defgeneric form), it is possible to add methods to it in the usual way.

(defmethod generic-find (item (list list) &key (test #'eql))
  (and (member item list :test test)
       t))

(defmethod generic-find (item (vector vector) &key (test #'eql))
  (cl:find item vector :test test))

(seal-domain #'generic-find '(t list))
(seal-domain #'generic-find '(t vector))

The novelty are the two calls to seal-domain. These calls seal the specified part of the function domain, and at the same time install compiler optimizations for calls to that generic function.

Whenever the compiler can detect that the arguments of a call to a fast generic function fall within such a sealed domain, the entire call can be optimized in a variety of ways. By default, the call to the fast generic function’s discriminating function will be replaced by a direct call to a custom effective method function. This means that there will be zero overhead for determining the generic function’s behavior. The following example illustrates this:

(defun small-prime-p (x)
  (generic-find x '(2 3 5 7 11)))

;; The call to GENERIC-FIND should have been replaced by a direct call to
;; the appropriate effective method function.
(disassemble #'small-prime-p)

It is even possible to inline the entire effective method into the call site. However, to avoid code bloat, this feature is disabled by default. To enable it, each method withing the sealed domain must contain an appropriate declaration, as shown in the next example.

Example 2 - Extensible Number Functions

(defgeneric binary-+ (x y)
  (:generic-function-class fast-generic-function))

(defmethod binary-+ ((x number) (y number))
  (declare (method-properties inlineable))
  (+ x y))

(seal-domain #'binary-+ '(number number))

It is easy to generalize such a binary function to a function that accepts any number of arguments:

(defun generic-+ (&rest things)
  (cond ((null things) 0)
        ((null (rest things)) (first things))
        (t (reduce #'binary-+ things))))

(define-compiler-macro generic-+ (&rest things)
  (cond ((null things) 0)
        ((null (rest things)) (first things))
        (t (reduce (lambda (a b) `(binary-+ ,a ,b)) things))))

With all this in place, we can use our generic-+ function much like Common Lisp’s built-in + without worrying about performance. The next code snippet shows that in fact, each call to generic-+ is inlined and turned into a single addss instruction.

(disassemble
 (compile nil
   '(lambda (x y z)
     (declare (single-float x y z))
     (generic-+ x y z))))

;; disassembly for (lambda (x y z))
;; Size: 38 bytes. Origin: #x52FD9354
;; 54:       498B4510         mov RAX, [R13+16]
;; 58:       488945F8         mov [RBP-8], RAX
;; 5C:       0F28CC           movaps XMM1, XMM4
;; 5F:       F30F58CB         addss XMM1, XMM3
;; 63:       F30F58CA         addss XMM1, XMM2
;; 67:       660F7ECA         movd EDX, XMM1
;; 6B:       48C1E220         shl RDX, 32
;; 6F:       80CA19           or DL, 25
;; 72:       488BE5           mov RSP, RBP
;; 75:       F8               clc
;; 76:       5D               pop RBP
;; 77:       C3               ret
;; 78:       CC10             int3 16

Once a fast generic function has been sealed, it is not possible to add, remove, or redefine methods within the sealed domain. However, outside of the sealed domain, it behaves just like a standard generic function. That means we can extend its behavior, e.g., to allow addition of strings:

(defmethod binary-+ ((x string) (y string))
  (concatenate 'string x y))

(generic-+ "foo" "bar" "baz")
;; => "foobarbaz"

Specializing on a User-Defined Class

By default, only built-in classes and structure classes can appear as specializers of a method within a sealed domain of a fast generic function. However, it is also possible to define custom sealable classes. This example illustrates how.

Since this example has plenty of dependencies (metaobject definition and use, generic function definition and method defintion, sealing and use of a sealed function), each of the following snippets of code should be put into its own file.

In the first snippet, we define sealable standard class, that is both a sealable class and a standard class.

(defclass sealable-standard-class
    (sealable-metaobjects:sealable-class standard-class)
  ())

(defmethod validate-superclass
    ((class sealable-standard-class)
     (superclass standard-class))
  t)

In the next snippet, we define a class foo whose metaclass is our newly introduced sealable-standard-class. Because the implementation of fast generic functions uses literal instances to find an optimized effective method function at load time, each sealable class must also have a suitable method on make-load-form.

(defclass foo ()
  ((x :reader x :initarg :x))
  (:metaclass sealable-standard-class))

(defmethod make-load-form ((foo foo) &optional env)
  (make-load-form-saving-slots foo :slot-names '(x) :environment env))

In the next snippet, we define a fast generic function op.

(defgeneric op (foo)
  (:generic-function-class fast-generic-functions:fast-generic-function))

Once we have loaded the definition of op, we can add individual methods and seal some of them. In particular, we can add a method that specializes on the foo class.

We could also have defined this method without foo being a sealable class, but then the call to seal-domain would have signaled an error.

(defmethod op ((foo foo))
  (* 2 (x foo)))

(sealable-metaobjects:seal-domain #'op '(foo))

Finally, we have everything in place for having optimized calls to op in the case where its argument is of type foo.

(defun bar ()
  (let ((foo (make-instance 'foo :x 42)))
    (declare (foo foo))
    (op foo)))

If this example is too intimidating for you, please remember that you can always specialize fast methods on built-in classes (like integer and simple-vector) or structure classes (everything defined via defstruct).