clojure.walk/keywordize-keys 和 stringify-keys 不必要地分配

Question

clojure.walk/keywordize-keys 和 clojure.walk/stringify-keys 分配 [k v] 向量，并将它们转换为映射条目。

基准测试显示，直接操作映射条目更有效率。

(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

即使是像 {"a" {"b" {"c" 1, 9 "d"}, "z" 5}} 这样非常小的映射中，性能提升也是相对的。

Answer 1

登录为 https://clojure.atlassian.net/browse/CLJ-2765

Answer 2

正如我在相关的jira票据中提到的，所提出的解决方案没有覆盖记录，这些记录实现了 IPersistentMap，因此可以通过现有的 keywordize-keys 和 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}

我不确定这里最好的做法是什么。

Answer 3

使用 reduce-kv 会显著更快，没有必要分配和结构化映射条目。