Fork me on GitHub
Slack Archive

This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

2019-09-21

Channels

#clojure-dev
<
2019-09-21
>
ikitommi17:09:56

Hmm.. clojure.core/merge seems quite slow. Is this worth investigating or a known issue? 

➜  ~ clj -Sdeps '{:deps {criterium {:mvn/version "0.4.5"}}, :jvm-opts ["-server"]}'
Clojure 1.10.0
user=> (require '[criterium.core :as cc])
nil
user=> (cc/quick-bench (merge {} {}))
Evaluation count : 2712492 in 6 samples of 452082 calls.
             Execution time mean : 221.103323 ns
    Execution time std-deviation : 1.892978 ns
   Execution time lower quantile : 219.218989 ns ( 2.5%)
   Execution time upper quantile : 223.419465 ns (97.5%)
                   Overhead used : 1.964440 ns

ikitommi17:09:28

merge flamegraph

hiredman18:09:50

A merge of an empty map in to an empty map is basically the worst case to micro benchmark, what would make it faster is checking for empty maps at the beginning and doing nothing, which wouldn't speed up any real world use cases

slipset19:09:03

I guess you could gain some speed up by introducing multiple arities for the low arity cases.

slipset19:09:47

(merge {} {}) is (conj {} {}), no need to start the full reduce1 machinery for that.

slipset19:09:01

user> (cc/quick-bench (merge {} {}))
Evaluation count : 2421150 in 6 samples of 403525 calls.
             Execution time mean : 250.990304 ns
    Execution time std-deviation : 9.293609 ns
   Execution time lower quantile : 243.127947 ns ( 2.5%)
   Execution time upper quantile : 266.075269 ns (97.5%)
                   Overhead used : 2.076286 ns

Found 1 outliers in 6 samples (16.6667 %)
	low-severe	 1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
;; => nil
user> (defn unrolled-merge
  ([m1] m1)
  ([m1 m2]
   (conj (or m1 {}) m2))
  ([m1 m2 & ms]
   (#'clojure.core/reduce1 conj (merge m1 m2) ms)))
;; => #'user/unrolled-merge
user> (cc/quick-bench (unrolled-merge {} {}))
Evaluation count : 7737186 in 6 samples of 1289531 calls.
             Execution time mean : 75.288592 ns
    Execution time std-deviation : 1.673650 ns
   Execution time lower quantile : 73.961836 ns ( 2.5%)
   Execution time upper quantile : 78.025617 ns (97.5%)
                   Overhead used : 2.076286 ns

Found 1 outliers in 6 samples (16.6667 %)
	low-severe	 1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
;; => nil
user>

👍 4
slipset19:09:50

The ticket is here:

slipset19:09:09

The approach taken is to introduce merge1 which doesn’t use reduce1, and then reimplement merge later when the proper reduce is available.

slipset19:09:59

@U0NCTKEV8 I think @U055NJ5CC’s example is quite nice, since it clearly shows the overhead involved in merge

ikitommi20:09:03

In my case, it was a real-world merge of small maps. But the time it takes was about the same as with empty maps, just to highlight the issue. Last comments from 2017: "This ticket needs help. Step 0 is writing a benchmark harness that exercises maps of various sizes, and the various polymorphic arguments below.".

borkdude14:09:10

@U055NJ5CC is reduce into any faster?

borkdude14:09:53

maybe this calls for a library with a faster version of merge 🙂

ikitommi14:09:09

With into (using transients): 

;; 230ns
(cc/quick-bench
  (into {} {}))
With bifurcan: 
(import (io.lacuna.bifurcan Map Maps))

;; 17ns
(let [m1 (Map.)
      m2 (Map.)]
  (cc/quick-bench
    (.merge m1 m2 Maps/MERGE_LAST_WRITE_WINS)))

borkdude14:09:25

quite the speedup

borkdude14:09:08

maybe include coercing from and to a Clojure map since that's what you want eventually I guess?

ikitommi15:09:22

yeh, this is not the way… 

;; 230ns
(let [m1 {}
      m2 {}]
  (cc/quick-bench
    (clojure.lang.PersistentArrayMap/create
      (.toMap (.merge (Map/from ^java.util.Map m1)
                      (Map/from ^java.util.Map m2)
                      Maps/MERGE_LAST_WRITE_WINS)))))