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.