clojure.walk/keywordize-keys and stringify-keys unnecessarily allocate

Question

clojure.walk/keywordize-keys and clojure.walk/stringify-keys allocate [k v] vectors that are converted to map entries.

Benchmarks show that it is more efficient to operate on map entries directly.

(require '[clojure.walk :as walk]
         '[criterium.core :as c])

(defn keywordize-keys
  [m]
  (walk/postwalk (fn [kv]
                   (if (and (map-entry? kv)
                            (string? (key kv)))
                     (clojure.lang.MapEntry. (keyword (key kv)) (val kv))
                     kv))
                 m))

(defn stringify-keys
  [m]
  (walk/postwalk (fn [kv]
                   (if (and (map-entry? kv)
                            (keyword? (key kv)))
                     (clojure.lang.MapEntry. (name (key kv)) (val kv))
                     kv))
                 m))

(let [sz 500000
      m (into {} (map (fn [i] [(str (random-uuid)) i]))
              (range sz))]
  ;; intern keys (doesn't seem to impact benchmark)
  (run! #(keyword (key %)) m)
  (doseq [f '[walk/keywordize-keys keywordize-keys]
          :let [f' (resolve f)]]
    (prn f)
    (c/quick-bench (f' m))
    nil))

;; walk/keywordize-keys
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 559.425609 ms
;;     Execution time std-deviation : 17.477808 ms
;;    Execution time lower quantile : 535.799373 ms ( 2.5%)
;;    Execution time upper quantile : 572.055045 ms (97.5%)
;;                    Overhead used : 2.097250 ns

;; keywordize-keys
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 413.512748 ms
;;     Execution time std-deviation : 9.081118 ms
;;    Execution time lower quantile : 402.917998 ms ( 2.5%)
;;    Execution time upper quantile : 422.893519 ms (97.5%)
;;                    Overhead used : 2.097250 ns

(let [sz 500000
      m (into {} (map (fn [i] [(keyword (str (random-uuid))) i]))
              (range sz))]
  (doseq [f '[walk/stringify-keys stringify-keys]
          :let [f' (resolve f)]]
    (prn f)
    (c/quick-bench (f' m))
    nil))

;; walk/stringify-keys
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 473.410415 ms
;;     Execution time std-deviation : 25.763722 ms
;;    Execution time lower quantile : 451.515206 ms ( 2.5%)
;;    Execution time upper quantile : 515.015561 ms (97.5%)
;;                    Overhead used : 2.097250 ns
;; 
;; Found 1 outliers in 6 samples (16.6667 %)
;; 	low-severe	 1 (16.6667 %)
;;  Variance from outliers : 14.2242 % Variance is moderately inflated by outliers

;; stringify-keys
;; Evaluation count : 6 in 6 samples of 1 calls.
;;              Execution time mean : 322.547283 ms
;;     Execution time std-deviation : 17.561204 ms
;;    Execution time lower quantile : 303.155082 ms ( 2.5%)
;;    Execution time upper quantile : 341.169831 ms (97.5%)
;;                    Overhead used : 2.097250 ns

The relative performance improvement is similar even in very small maps like {"a" {"b" {"c" 1, 9 "d"}, "z" 5}}.

Answer 1

Logged as https://clojure.atlassian.net/browse/CLJ-2765

Answer 2

As I said in the linked jira ticket, the proposed solution doesn't cover records, which implement IPersistentMap and thus are duly transformed by the existing implementations of keywordize-keys and stringify-keys:

user=> (defrecord A [b])
user.A
user=> (walk/stringify-keys (->A 1))
{"b" 1}
user=> (stringify-keys (->A 1))
#user.A{:b 1, "b" 1}

I’m not sure which is the best course of action here.

Answer 3

It would be significantly faster to use reduce-kv, no reason to allocate and destructure map entries