Skip to content
Seal your generic functions for an extra boost in performance.
Common Lisp
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
code
test-suite Turn fast generic functions into a separate project. Mar 18, 2020
LICENSE Create a separate package for fast generic functions. Mar 18, 2020
README.org Turn fast generic functions into a separate project. Mar 18, 2020

README.org

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 this domain, it will perform a variety of optimizations.

Example 1 - Generic Find

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

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

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

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

(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.
(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"
You can’t perform that action at this time.