Inline Caches with LOAD-TIME-VALUE #
hacking, February 19th 2011
This isn't anything new, but a handy technique that isn't maybe as well known as it could be.
Let's say you're receiving stuff that has timestamps over a stream, and you see that parsing those timestamp strings is taking more time than you'd like.
What's more, you notice that often enough several consequtive timestamps are identical — so you're parsing the same string over and over again.
Obviously any memoization technique could serve well here, but here's how you would do it with an inline 1-element cache.
(defun parse-timestamp (string)
;; LOAD-TIME-VALUE is kind of like "static" in C. Value of
;; CACHE will be bound to the _same_ CONS cell every time
;; this code run. It could just as well be any other
;; object, but a CONS is a nice lightweight object to use
;; for a 1-element cache.
;;
;; In its CDR we will store another CONS whose CAR is the
;; string and whose CDR is the corresponding timestamp.
;; Then we can use EQUAL to compare the strings, and pick
;; the cached value when appropriate.
;;
;; The second CONS is used so that we can replace it
;; atomically when needed: if multiple threads are running
;; in parallel, we don't want to mutate a cell. Otherwise
;; another thread might have just compared the string only
;; to have the timestamp change under its feet —
;; returning the wrong result.
;;
;; This "replace a whole object containing multiple
;; interdependant values" is a very useful portable
;; thread-safety technique (it only assumes that object
;; initialization has a memory barrier so that all threads
;; see consistent values of the new CONS immediately: if
;; they see the string in the new CONS, they must also see
;; the timestamp.)
(let* ((cache (load-time-value (cons 'timestamp-cache nil)))
(cached (cdr cache)))
(if (equal (car cached) string)
(cdr cached)
(let* ((timestamp (%parse-timestamp string))
(new-cached (cons string timestamp)))
(setf (cdr cache) new-cached)
timestamp))))