Faster fast-merge
- Dominant language
- Clojure
- Stars
- 251
- Forks
- 2
- PR merge metrics
- No merged PRs in 30d
Description
I was independently working on something similar, albeit with a focus on improving clojure.core/merge performance. Watching Tommi's talk reminded me of the slowness (and I end up using it in a lot of legacy code on hot paths...). I tried just optimizing the persistent map-based variant, which got me into the same ballpark you referenced (~30%). Going with transients and a useful heuristic yields some better fruit though (~50%)...
I did some testing to eliminate sources of slowdown:
- prefer discrete args vs. the default var-args for everything version,
- use transients instead of persistent map-based conj,
- use direct method invocation everywhere,
- accumulate keys from r->l instead of l->r, since we can prune more (in some cases, e.g. 2-arg versions like (merge {:a 2 :b 3 :c 4} {:a 1 :b 1 :c 1}) we can exclude all keys from l since they already appear in R, leading to 0 actual assoc's)
```
(defn rmerge! [^clojure.lang.IKVReduce l r]
(.kvreduce l
(fn [^clojure.lang.ITransientAssociative acc k v]
(if-not (acc k)
(.assoc acc k v)
acc)) r))
;;~50% faster.
(defn fast-merge
([] {})
([m] m)
([m1 m2] (rmerge m1 m2))
([m1 m2 m3] (->> (transient m3) (rmerge! m2) (rmerge! m1) persistent!))
([m1 m2 m3 m4] (->> (transient m4) (rmerge! m3) (rmerge! m2) (rmerge! m1) persistent!))
([m1 m2 m3 m4 m5] (->> (transient m5) (rmerge! m4) (rmerge! m3) (rmerge! m2) (rmerge! m1) persistent!))
([m1 m2 m3 m4 m5 & ms]
(let [rs (reverse ms)]
(->> (reduce rmerge! (transient (first rs)) (rest rs))
(rmerge! m5)
(rmerge! m4)
(rmerge! m3)
(rmerge! m3)
(rmerge! m1)
persistent!))))
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading clojure.core/merge and the supplied fast-merge and rmerge! variants, focusing on the transient and argument-count cases described in the issue. Benchmark the merge scenarios discussed in the body; done means an integrated implementation preserves merge behavior and confirms the reported performance improvement.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- clojure
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100