faster, more flexible dispatch for clojure.walk

Question

The conditional dispatch in clojure.walk is slow and not open to extension. Prior to CLJ-1105 it did not support records.

Approach: Reimplement clojure.walk using protocols. The public API does not change. Users can extend the {{walk}} protocol to other types (for example, Java collections) if desired. As in CLJ-1105, this version of clojure.walk supports records.

Patch: 0002-CLJ-1239-protocol-dispatch-for-clojure.walk.patch

Performance: My tests indicate this is 1.5x-2x the speed of the original clojure.walk. See https://github.com/stuartsierra/clojure.walk2 for benchmarks.

Risks: This approach carries some risk of breaking user code that relied on type-specific behavior of the old clojure.walk. When running the full Clojure test suite, I discovered (and fixed) some breakages that did not show up in clojure.walk's unit tests. See, for example, (link: https://github.com/stuartsierra/clojure.walk2/commit/730eb756dcc424aa535d0872bd626079955c3892 text: commit 730eb75 in clojure.walk2)

Answer 1

Comment made by: vmarcinko

It looks, as it is now, that walking the tree and replacing forms doesn't preserve original meta-data contained in data structures.

Answer 2

Comment made by: jafingerhut

Patch 0001-CLJ-1239-protocol-dispatch-for-clojure.walk.patch no longer applies cleanly to latest Clojure master since the patch for CLJ-1105 was committed on Nov 22, 2013. From the description, it appears the intent was either that patch or this one, not both, so I am not sure what should happen with this patch, or even this ticket.

Answer 3

Comment made by: alexmiller

This patch and ticket are still candidates for future release.

Answer 4

Comment made by: stuart.sierra

Added new patch that applies on latest master after CLJ-1105.

Answer 5

_Comment made by: chouser@n01se.net_

The way this patch behaves can be surprising compared to regular maps:


(clojure.walk/prewalk-replace {[:a 1] nil} {:a 1, :b 2})
;=> {:b 2}

(defrecord Foo [a b])
(clojure.walk/prewalk-replace {[:a 1] nil} (map->Foo {:a 1, :b 2}))
;=> #user.Foo{:a 1, :b 2}


Note how the {{[:a 1]}} entry is removed from the map, but not from the record.

Here's an implementation that doesn't suffer from that problem, though it does scary class name munging instead: https://github.com/LonoCloud/synthread/blob/a315f861e04fd33ba5398adf6b5e75579d18ce4c/src/lonocloud/synthread/impl.clj#L66

Perhaps we could add to the defrecord abstraction to support well the kind of things that synthread code is doing clumsily, and then {{walk}} could take advantage of that.

Answer 6

Comment made by: alexmiller

@Chouser, can you file a new ticket related to this? It's hard to manage work on something from comments on a closed ticket.

Answer 7

Comment made by: alexmiller

@Chouser - Never mind! I was thinking this was the change that went into 1.6. Carry on. :)

Answer 8

Comment made by: bronsa

Alex, for what it matters clojure-1.6.0 after CLJ-1105 exibits the same behaviour as described by Chouser for this patch

Answer 9

Comment made by: glts

The current implementation of clojure.walk does not preserve metadata.

If this new implementation is ever revisited, it would be great to also keep the metadata on the elements where possible.

Answer 10

Reference: https://clojure.atlassian.net/browse/CLJ-1239 (reported by stuart.sierra)

Answer 11

(moved from https://ask.clojure.org/index.php/14453/could-clojure-walk-walk-be-less-lazy)

Not directly related to dispatch, but still performance: I noticed that clojure.walk/walk is perhaps lazier internally than it necessarily needs to be. It uses several lazy (map) calls whose output then gets fully consumed.

Would it be considered to change these calls to either (mapv) or the transducer arity of (map) for performance considerations?

Here is a quick diff of a rough suggestion of changes against current master:

diff --git a/src/clj/clojure/walk.clj b/src/clj/clojure/walk.clj
index 0f027e7a..96b089f6 100644
--- a/src/clj/clojure/walk.clj
+++ b/src/clj/clojure/walk.clj
@@ -41,13 +41,13 @@ the sorting function."}
   {:added "1.1"}
   [inner outer form]
   (cond
-   (list? form) (outer (with-meta (apply list (map inner form)) (meta form)))
+   (list? form) (outer (with-meta (apply list (mapv inner form)) (meta form)))
    (instance? clojure.lang.IMapEntry form)
    (outer (clojure.lang.MapEntry/create (inner (key form)) (inner (val form))))
-   (seq? form) (outer (with-meta (doall (map inner form)) (meta form)))
+   (seq? form) (outer (with-meta (seq (mapv inner form)) (meta form)))
    (instance? clojure.lang.IRecord form)
      (outer (reduce (fn [r x] (conj r (inner x))) form form))
-   (coll? form) (outer (into (empty form) (map inner form)))
+   (coll? form) (outer (into (empty form) (map inner) form))
    :else (outer form)))

 (defn postwalk
@@ -97,7 +97,7 @@ the sorting function."}
   [m]
   (let [f (fn [[k v]] (if (string? k) [(keyword k) v] [k v]))]
     ;; only apply to maps
-    (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
+    (postwalk (fn [x] (if (map? x) (into {} (map f) x) x)) m)))

 (defn stringify-keys
   "Recursively transforms all map keys from keywords to strings."
@@ -105,7 +105,7 @@ the sorting function."}
   [m]
   (let [f (fn [[k v]] (if (keyword? k) [(name k) v] [k v]))]
     ;; only apply to maps
-    (postwalk (fn [x] (if (map? x) (into {} (map f x)) x)) m)))
+    (postwalk (fn [x] (if (map? x) (into {} (map f) x) x)) m)))

this is somewhat related to some of the changes proposed in 0003-CLJ-1239-protocol-dispatch-for-clojure.walk.patch on CLJ-1239