static-merge

[joinr]

If we enforce the invariant that we have literal maps, with distinct keys, we can merge statically with type hints and avoid iteration costs. I noticed I do this "a lot" in my legacy code, so this refactoring came out during optimization passes. Only works with Associatives

(defmacro static-merge
  [& ms]
  (assert (every? map? (rest ms)))
  (assert (every? #(= 1 %) (->> (rest ms) (mapcat keys) frequencies vals)))
  (let [kvs (mapcat seq (rest ms))]
    (reduce (fn [acc [k v]]
              `(assoc ~acc ~k ~v)) (first ms) kvs)))

;;type hinted method invocations avoid clojure.lang.RT shave off a bit of overhead
(defmacro static-merge2
  [& ms]
  (assert (every? map? (rest ms)))
  (assert (every? #(= 1 %) (->> (rest ms) (mapcat keys) frequencies vals)))
  (let [kvs (mapcat seq (rest ms))
        assoc! (fn [m k v]
                 `(.assoc  ~(with-meta m {:tag 'clojure.lang.Associative})
                              ~k ~v))]
    (reduce (fn [acc [k v]]
              (assoc! acc k v)) (first ms) kvs)))

fastest to slowest. Not sure if there's any downside to using .assoc directly over clojure.core/assoc (assumedly clojure.core/assoc is more general, but...)

user> (let [m {:a 2 :b 3}] (c/quick-bench (static-merge2  m {:c 4 :e 5} {:d 6 :f 7} {:h 9 :j 10})))
Evaluation count : 2711934 in 6 samples of 451989 calls.
             Execution time mean : 221.200769 ns
    Execution time std-deviation : 1.056652 ns
   Execution time lower quantile : 219.797515 ns ( 2.5%)
   Execution time upper quantile : 222.274280 ns (97.5%)
                   Overhead used : 1.859794 ns
nil
user> (let [m {:a 2 :b 3}] (c/quick-bench (static-merge  m {:c 4 :e 5} {:d 6 :f 7} {:h 9 :j 10})))
Evaluation count : 2555754 in 6 samples of 425959 calls.
             Execution time mean : 231.992038 ns
    Execution time std-deviation : 2.440858 ns
   Execution time lower quantile : 230.296052 ns ( 2.5%)
   Execution time upper quantile : 235.110715 ns (97.5%)
                   Overhead used : 1.859794 ns
nil
user> (let [m {:a 2 :b 3}] (c/quick-bench (fast-merge  m {:c 4 :e 5} {:d 6 :f 7} {:h 9 :j 10})))
Evaluation count : 870594 in 6 samples of 145099 calls.
             Execution time mean : 695.676793 ns
    Execution time std-deviation : 9.920187 ns
   Execution time lower quantile : 685.828793 ns ( 2.5%)
   Execution time upper quantile : 711.901821 ns (97.5%)
                   Overhead used : 1.859794 ns

Found 2 outliers in 6 samples (33.3333 %)
    low-severe   1 (16.6667 %)
    low-mild     1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
nil
user> (let [m {:a 2 :b 3}] (c/quick-bench (merge  m {:c 4 :e 5} {:d 6 :f 7} {:h 9 :j 10})))
Evaluation count : 567864 in 6 samples of 94644 calls.
             Execution time mean : 1.063203 µs
    Execution time std-deviation : 8.960491 ns
   Execution time lower quantile : 1.053826 µs ( 2.5%)
   Execution time upper quantile : 1.073839 µs (97.5%)
                   Overhead used : 1.859794 ns
nil

In this sample, static-merge is ~4.8x faster than clojure.core/merge, and ~3.14x (lol) faster than the fast-merge function submitted earlier.

[joinr]

It occurs to me there are probably even more efficiencies to be had if the thing you're merging into is a type or record, e.g. you can efficiently construct a new instance very quickly vs. having to do multiple assoc calls. hmm.

[bsless]

I was wondering if I should tackle this use case. Maybe after the big refactor (coming after memoize)