Faster fast-merge

[joinr]

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!))))

[bsless]

Nice! This is really interesting!
Are you interested in adding it via a PR?
If not, do I have your permission to add it?

[joinr]

Feel free to add away, just reference me in the comment if you do please. Maybe it helps others find a common repository of optimized functions. You should maybe benchmark as well to make sure my results are consistent as claimed.

I'm compiling some stuff specifically for low level perf (really just regaining performance that's left on the floor in clojure.core, primarily due to overly polymorphic code and naive implementations) while optimizing a couple of different projects (and incorporating old lessons), like the various performance optimization against rust here and little libs like structural.

Another area that sucks, fyi, is the default clojure.core/memoize. Can be sped up significantly with a concurrent mutable hashmap, and if you have a discrete number of args, you can get it way faster with a specialized function that uses multiple hashmaps vs. the stock & args variadic version.

[bsless]

Will do, expect it in the coming week :)

And now I realize where I recognized your name from. I was really surprised to see structural, like some form of converging evolution in front of our eyes. Perhaps we should cooperate further regarding performance.

Finally regarding memoize, yes and every place where apply is used.

I'll also have a look at the other repo you linked, seems interesting. Thanks.

[bsless]

brief update: Looks like your suggestion is faster under certain conditions, if not all. I'm reworking the benchmarks ns to get higher quality results and analysis, then it'll get in to the next release

[bsless]

Added to latest version :)

[joinr]

I just noticed in recent testing that the original code I submitted didn't invoke transient and rmerge! correctly for the 2-arity version. No problem though, because your implementation does! Good job :)

[joinr]

Just ran into the myopic realization that I assumed input supports IKVReduce without a fallback..

(defn rmerge! [l  r]
  (if (instance? clojure.lang.IKVReduce l)
    (.kvreduce ^clojure.lang.IKVReduce l (fn [^clojure.lang.ITransientAssociative acc k v]
                                           (if-not (acc k)
                                             (.assoc acc k v)
                                             acc)) r)
    (clojure.core.protocols/kv-reduce l (fn [^clojure.lang.ITransientAssociative acc k v]
                                          (if-not (acc k)
                                            (.assoc acc k v)
                                            acc)) r)))

This version will do a (meager) instance check to see if we can use the fast path, and fall back to the protocol invocation (e.g. for user defined types) otherwise.

[bsless]

Good catch. I reopened the issue and will close it again once I add it. Thank you :)

[joinr]

Very curious to see tmerge apparently getting beat by fast-merge since they're very close implementation-wise (excepting the transient usage, and the reversed order of input for map processing). I tmerge to dominate (as it did in my tests with effectively a similar implementation of fast-map-merge). Interesting.

[joinr]

From a cursory examination of your benchmarks, your tests are generating random maps via keyword? as a sample generator. Unless I'm mistaken. If this is the case, then you would be guaranteeing unique keys for map merges across maps. I believe this basically eliminates the performance advantages that you'd see in rmerge! and consequently tmerge to an extent, since they are able to ignore associng pre-existing keys going in reverse order. Instead, there's a bit of overhead introduced due to reversing and transient/persistent calls, particularly for smaller maps, where the stock left-to-right merge wouldn't have these. Perhaps another map sample generator would be informative, where merged maps share a subset of the same keys (perhaps a variable amount).

Could be that a better (specific) name for the reverse-optimized merge operation would be collapse. Or perhaps reverse-merge heh.

[joinr]

Caught another possible issue with your map generation code, dunno if it matters necessarily (likely only matters for the int? case).

When you generate random maps via randmap, the distribution over the integer key range will apparently double sample keys, so your map size isn't constant. Not sure if this a big problem in practice, or if you intend to have varying map sizes (this probably will not occur with the string and keyword cases, for example).

clj-fast.bench> (frequencies (map count (repeatedly 1000 #(randmap int? 1000) )))
{789 12,
 765 17,
 798 1,
 779 28,
 774 38,
 769 26,
 799 2,
 756 11,
 806 1,
 770 42,
 777 33,
 788 9,
 773 45,
 752 3,
 797 4,
 763 20,
 805 1,
 743 1,
 776 36,
 755 15,
 758 18,
 759 23,
 749 6,
 781 18,
 796 7,
 785 20,
 782 21,
 792 6,
 761 23,
 794 4,
 790 4,
 784 15,
 800 1,
 739 1,
 768 40,
 778 27,
 775 46,
 760 19,
 803 1,
 783 23,
 772 46,
 757 13,
 786 8,
 787 14,
 771 32,
 751 7,
 802 2,
 793 4,
 746 5,
 753 9,
 766 26,
 795 4,
 762 27,
 747 3,
 767 43,
 736 1,
 748 4,
 750 4,
 780 34,
 754 11,
 791 3,
 744 3,
 764 29}

[joinr]

Existing implementation of tmerge in clj-fast was inefficient. removed superflous instance checks and let binding, gets the performance down to fast-map-merge equivalence.

[joinr]

Added a test to the benchmarks that has parameter-driven proportional map key sharing for the maps (e.g. 10%, up to 100% of the key width are shared across the random maps). Baseline profiling with 50% shared keys shows tmerge dominating as expected. Will submit a PR for analysis in a bit.