Resettable Memoize in Clojure

Memoize in Clojure is cool. Memoize is even built in to the core Clojure API. Resetting the built-in version is impossible since the atom used as a cache is hidden in a closure, but it’s easy to write a custom resettable version. Here are two versions that we came up with on IRC today.

Update: core.memoize

Check out the core.memoize library if you want more extensive control over your memoization. It includes support for a pluggable caching backend and cache manipulation functions.

Memoization: What It Is

In memoization, a higher-order function wraps your expensive (pure) function with a transparent cache, so that subsequent calls don’t have to re-process everything. The higher-order function stores the argument list and the result of calling the function with those arguments, and if it can, it returns that pre-computed result instead of re-computing the result via the expensive lower-order function. If your function has no side-effects, this is transparent to the caller. You’re trading increased memory use for speed, which is often a good tradeoff for expensive functions that return a small amount of data.

Memoization is perfect if the arguments that you need to call the function with never change. You compute the result once and re-use it indefinitely. At the other extreme, if every call to the function requires completely different arguments, then there is no point in memoizing it at all.

But what about the in-between case where the argument data changes, but only rarely? You need the ability to reset the memo. 99% of your calls will receive the speed benefits of using the cached version, and when your dataset does change, you can simply clear the cache and memoize a new version.

Resettable Memoize

Clojure’s memoize function uses an atom internally to store the cache state. Without too much work, we can introduce the ability to reset the memo by introducing a way to reach the atom.

Metadata-based reset for bleeding-edge Clojures

Clojure allows you to decorate your data with arbitrary metadata, which is perfect for our needs here. Around January of 2010, the master branch of Clojure in Git introduced the ability to annotate functions with metadata. a_strange_guy from #clojure on IRC wrote the following improved memoize function that exposes the cache storage atom as metadata. It can then be reset! normally.

;; By a_strange_guy on IRC. Exposes the atom in metadata to allow it
;; to be reset from the outside.
;; Doesn't work with stable versions of Clojure as of February 2010, because they don't allow metadata on 
;; functions yet. Requires a Master checkout from Git.

(defn memoize-visible-atom [f]
  (let [mem (atom {})]
    (with-meta
      (fn [& args]
        (if-let [e (find @mem args)]
          (val e)
          (let [ret (apply f args)]
            (swap! mem assoc args ret)
            ret)))
      {:memoize-atom mem})))

This is perfect, but unfortunately it doesn’t work on stable releases of Clojure yet (as of February 2010), because they don’t allow you to add metadata to functions.

Resetting with a magic argument

I wrote the following workaround based on a_strange_guy’s code:

;; For versions of Clojure that don't have metadata on functions, this
;; allows you to reset the atom by passing the magic argument :reset!

(defn memoize-visible-atom-hack [f]
  (let [mem (atom {})]
    (fn [& args]
      (if (= (first args) :reset!)
        (reset! mem {})
        (if-let [e (find @mem args)]
          (val e)
          (let [ret (apply f args)]
            (swap! mem assoc args ret)
            ret))))))

If you call your memoized function as (fn-name :reset!), the cache is cleared. Otherwise, it works as a normal memoize. Messy, yes, but it works, and it will do until metadata on functions makes its way into a stable Clojure release.

Clojure posts you might also like:

2 Responses to Resettable Memoize in Clojure

  1. I don’t remember what exactly I needed this for, but here’s a version of memoize that uses soft references so it will (presuming a non-braindead JVM) drop the least-recently-referenced cached results before OOMing.

    (defn soft-memoize
      "Returns a memoized version of a referentially transparent function. The
      memoized version of the function keeps a cache of the mapping from arguments
      to results and, when calls with the same arguments are repeated often, has
      higher performance at the expense of higher memory use.  This version uses
      SoftReferences so that the memoization will never cause an OOM."
      [f]
      (let [mem (ReferenceMap. ReferenceMap/SOFT ReferenceMap/SOFT)
            null-marker (gensym)]
        (fn [& args]
          (if-let [e (.get mem args)]
            (if (= e null-marker)
              nil
              e)
            (let [ret (apply f args)]
              (.put mem args (if ret ret null-marker))
              ret)))))