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?
- Make *FOO-TABLE* hold cells holding the actual objects.
- Use LOAD-TIME-VALUE to grab hold of the cell inline.
- (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.