Nikodemus Siivola

<< next | top | previous >>

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)

See also: Inline Caches with LOAD-TIME-VALUE, part 2