Inline Caches with LOAD-TIME-VALUE, part 2
So why would you want to use
LOAD-TIME-VALUE to implement a cache instead of doing
something like this:
(let (cache)
(defun parse-timestamp (string)
(let ((cached cache))
(if (equal string (car cached))
(cdr cached)
(let ((stamp (%parse-timestamp string)))
(setf cache (cons string stamp))
stamp)))))
...or this?
(defparameter *cache* nil)
(defun parse-timestamp (string)
(let ((cached *cache*))
(if (equal (car cached) string)
(cdr cached)
(let ((stamp (%parse-timestamp string)))
(setf *cache* (cons string stamp))
stamp))))
It's the reason why I'm talking about inline caches. While
using toplevel closure or a global variable to implement the cache
works fine, consider inlining (and compiler-macros.)
Simply by proclaiming the LOAD-TIME-VALUE-using function
INLINE, you will be giving each call site their own
cache--which is often exactly what you want. (Admittedly
this timestamp parsing probably doesn't warrant that.)
Similarly, you can define the a two-level cache with both
local/call-site and global lookups (though again, timestamp parsing
almost certainly doesn't need this):
(defvar *global-timestamp-cache* nil)
(defconstant +timestamp-cache-max-size+ 12)
;;; A global lookup with a simple size-limited cache.
(defun parse-timestamp (string)
(let* ((cache *global-timestamp-cache*)
(stamp (cdr (assoc string cache :test #'equal))))
(or stamp
(let ((stamp (%%parse-timestamp string)))
(setf *global-timestamp-cache*
(cons (cons string stamp)
(if (>= (length cache) +timestamp-cache-max-size+)
(subseq cache 0 (1- +timestamp-cache-max-size+))
cache)))
stamp))))
;;; Two cases: constant string arguments get constant timestamps,
;;; and more importantly, we add a per-call-site 1-element cache.
(define-compiler-macro parse-timestamp (string)
(if (stringp string)
`',(%parse-timestamp string)
(alexandria:with-gensyms (cache cached stamp)
(alexandria:once-only (string)
`(let* ((,cache (load-time-value (cons 'local-timestamp-cache nil)))
(,cached (cdr ,cache)))
;; NOTINLINE inhibits compiler-macro expansion.
(declare (notinline parse-timestamp))
(if (equal ,string (car ,cached))
(cdr ,cached)
(let ((,stamp (parse-timestamp ,string)))
(setf (cdr ,cache) (cons ,string ,stamp))
,stamp)))))))
I keep saying that timestamp parsing doesn't need local (call-site) caches.
What does?
- Things that are in the really critical path where avoiding a function
call is a win.
- Things where there are multiple arguments ("keys"), and one or
more of them are often constant: (foo 'bar 'quux zot). In this
case the local lookups are much more likely to result in a cache hit
because only one argument out of three varies--and since the local
lookup only needs to index using a single key, it is always going to be
faster than the global cache lookup which needs to index using all three
keys/arguments.
Final note regarding caches, and inline caches in particular: don't
go overboard with them. Unless you actually need them, they will
hinder your performance more than they help it: a cache miss means
extra work done compared to a straight up call, so unless the number
of cache hits is sufficient to compensate for that they're not worth
it. As always, the profiler is your friend.
Syndicated 2011-02-21 06:25:42 from Nikodemus Siivola
