Skip to content
A CLOSsy way to trade genericity for performance.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
code Improve computation of specializer prototypes. May 23, 2019
test-suite
LICENSE
README.org

README.org

Sealable Metaobjects

Introduction

We present an extension of the Common Lisp Object System (CLOS) that allows a compiler to inline a generic function under certain conditions.

We should note that moving parts of the callee into the caller is usually a very bad idea. It prevents safe and efficient function redefinition and inflates the amount of generated machine code at the call site. Most severely, when moving parts of a generic function to the caller, we lose the ability to redefine or extend some of the involved objects and metaobjects.

Nevertheless, there are two cases where the aforementioned drawbacks are tolerable. The one case is when passing built-in Common Lisp objects to specified functions. The other case is for user code that has such extreme performance demands that the alternative of using this technique would be to refrain from using generic functions altogether.

The Technique

The goal is to inline a generic function under certain circumstances. These circumstances are:

  1. It is possible to statically determine the generic function being called.
  2. This generic function is sealed, i.e., it is an instance of SEALABLE-GENERIC-FUNCTION that has previously been passed to the function SEAL-GENERIC-FUNCTION.
  3. This sealed generic function has at least one sealed method, i.e., a method of type POTENTIALLY-SEALABLE-METHOD that specializes, on each relevant argument, on a built-in or sealed class, or an eql specializer whose object is an instance of a built-in or sealed class.
  4. It must be possible to determine, statically, that the types of all arguments in a specializing position uniquely determine the list of applicable methods.

Examples

The following examples illustrate how sealable metaobjects can be used. Each example code can be evaluated as-is. However, for actual use, we recommend the following practices:

  • Sealable generic functions should be defined in a separate file that is loaded early. If this is not done, its methods may not use the correct method-class. (An alternative is to specify the method class of each method explicitly).
  • Metaobject sealing should be the very last step when loading a project. Ideally, all calls to SEAL-GENERIC-FUNCTION should be in a separate file that ASDF loads last. This way, sealing can also be disabled conveniently, e.g., to measure whether sealing actually improves performance (Which you should do!).

Generic Plus

This example shows how one can implement a generic version of cl:+.

(sealable-metaobjects:define-sealable-generic-function generic-binary-+ (a b))

(defmethod generic-binary-+ ((a number) (b number))
  (+ a b))

(defmethod generic-binary-+ ((a character) (b character))
  (+ (char-code a)
     (char-code b)))

(sealable-metaobjects:seal-generic-function #'generic-binary-+)

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

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

You can quickly verify that this new operator is as efficient as cl:+:

(defun triple-1 (x)
  (declare (single-float x))
  (+ x x x))

(defun triple-2 (x)
  (declare (single-float x))
  (generic-+ x x x))

(disassemble #'triple-1)

(disassemble #'triple-2)

Yet, other than cl:+, generic-+ can be extended by the user, just like a regular generic function. The only restriction is that new methods must not interfere with the behavior of methods that specialize on sealed types only.

(defclass my-double-float ()
  ((%value :initarg :value :reader my-double-float-value)))

(defmethod generic-binary-+ ((a my-double-float) (b my-double-float))
  (make-instance 'my-double-float
    :value (+ (my-double-float-value a)
              (my-double-float-value b))))

(defun triple (x)
  (generic-+ x x x))

(my-double-float-value
 (triple
  (make-instance 'my-double-float :value 5.0d0)))

Generic Find

This example illustrates how one can implement a fast, generic version of cl:find.

(define-sealable-generic-function generic-find (item sequence &key test)
  ;; Only allow specialization on SEQUENCE, and not on ITEM.
  (:argument-precedence-order sequence))

(defmethod generic-find (elt (list list) &key (test #'eql))
  (loop for item in list
        when (funcall test item elt) do (return item)))

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

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

(disassemble #'small-prime-p)

Related Work

You can’t perform that action at this time.