bsless / bsless/clj-fast

Faster fast-merge

Open
#1 47 comments 1 reaction 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.