random-state.net

Nikodemus Siivola

<< next | top | previous >>

Optimizing Lookup Functions Using LOAD-TIME-VALUE #
hacking, March 1st 2011

Consider code along the lines of this:

(defvar *foo-table* (make-hash-table))

(defun find-foo (name &optional errorp)
  (or (gethash name *foo-table*)
      (when errorp
        (error "No FOO called ~S." name))))

;;; Style Cop says: It is good form to keep the interfaces identical,
;;; even though the SETF version doesn't use the ERRORP.
(defun (setf find-foo) (foo name &optional errorp)
  (declare (ignore errorp))
  (setf (gethash name *foo-table*) foo))

Assuming that cases with constant NAME arguments exist, how to optimize them — aside from custom hashing schemes, etc?

  1. Make *FOO-TABLE* hold cells holding the actual objects.
  2. Use LOAD-TIME-VALUE to grab hold of the cell inline.
  3. (SETF FIND-FOO) will first grab the cell and then update it.

Thusly:

(defvar *foo-table* (make-hash-table))

(defun find-foo-cell (name create)
  (or (gethash name *foo-table*)
      (when create
        (setf (gethash name *foo-table*)
              (cons name nil)))))

(defun foo-from-cell (cell errorp &optional name)
  (or (cdr cell)
      (when errorp
        (error "No FOO called ~S." (or (car cell) name)))))

(defun find-foo (name &optional errorp)
  (foo-from-cell (find-foo-cell name nil) errorp name))

(define-compiler-macro find-foo (&whole form name &optional errorp)
  (if (constantp name)
      `(foo-from-cell (load-time-value (find-foo-cell ,name t)) ,errorp)
      form))

(defun (setf find-foo) (foo name &optional errorp)
  (declare (ignore errorp))
  (setf (cdr (find-foo-cell name t)) foo))

(define-compiler-macro (setf find-foo)
    (&whole form value name &optional errorp)
  (declare (ignore errorp))
  (if (constantp name)
      `(setf (cdr (load-time-value (find-foo-cell ,name t))) ,value)
      form))

...and then there are no hash-table accesses at runtime for the constant argument cases.

Depending on your implementation's support for SETF-compiler-macros, you may need to replace the SETF-function with

(defsetf find-foo set-foo) ; then SET-FOO and a compiler-macro for it

... but the same principle holds.