Skip to content

Instantly share code, notes, and snippets.

@tonsky tonsky/distinct_bench.cljs
Last active Dec 25, 2016

Embed
What would you like to do?
(defn quick-benchmark [fun]
(let [t0 (js/performance.now)]
(loop []
(dotimes [_ 10] (fun))
(when (< (- (js/performance.now) t0) 1000) (recur)))
(let [t0 (js/performance.now)
steps (loop [steps 0]
(dotimes [_ 10] (fun))
(if (< (- (js/performance.now) t0) 5000)
(recur (+ steps 10))
(+ steps 10)))
dt-ms (- (js/performance.now) t0)
avg-sec (/ dt-ms 1000.0 steps)]
avg-sec)))
(defn format-time [sec]
(cond
(> sec 60) (str (/ sec 60) " min")
(< sec 1e-6) (str (* sec 1e9) " ns")
(< sec 1e-3) (str (* sec 1e6) " µs")
(< sec 1) (str (* sec 1e3) " ms")
:else (str sec " sec")))
(defmacro race [body1 body2]
`(let [_# (assert (= ~body1 ~body2))
t1# (quick-benchmark (fn [] ~body1))
t2# (quick-benchmark (fn [] ~body2))
percent# (->> (/ t2# t1#) (* 100) (- 100) (int))]
(println ~(pr-str body1) "\t"
(format-time t1#) "=>" (format-time t2#)
(str "(" (- percent#) "%)"))))
(enable-console-print!)
(defn transient-distinct
([]
(fn [rf]
(let [seen (volatile! (transient {}))]
(fn
([] (rf))
([result] (rf result))
([result input]
(if ^boolean (-lookup @seen input false)
result
(do (vswap! seen -assoc! input true)
(rf result input))))))))
([coll]
(let [step (fn step [xs seen]
(lazy-seq
((fn [[f :as xs] seen]
(when-let [s (seq xs)]
(if ^boolean (-lookup seen f false)
(recur (rest s) seen)
(cons f (step (rest s) (-assoc! seen f true))))))
xs seen)))]
(step coll (transient {})))))
(doseq [size [10 100 1000 10000]
:let [coll (vec (repeatedly size #(rand-int 1000)))]]
(println size "elements")
(race (reduce + 0 (distinct coll))
(reduce + 0 (transient-distinct coll)))
(race (transduce (distinct) + 0 coll)
(transduce (transient-distinct) + 0 coll)))
10 elements
(reduce + 0 (distinct coll)) 12.360220502805724 µs => 9.504153281757874 µs (-23%)
(transduce (distinct) + 0 coll) 7.689213711227641 µs => 5.3549045227207 µs (-30%)
100 elements
(reduce + 0 (distinct coll)) 136.43424283765356 µs => 106.66990187713321 µs (-21%)
(transduce (distinct) + 0 coll) 73.05427319211107 µs => 48.737280701754386 µs (-33%)
1000 elements
(reduce + 0 (distinct coll)) 1.1207102908277415 ms => 919.8952205882359 µs (-17%)
(transduce (distinct) + 0 coll) 677.2834912043312 µs => 482.79681467181547 µs (-28%)
10000 elements
(reduce + 0 (distinct coll)) 4.777295238095228 ms => 4.3203448275862115 ms (-9%)
(transduce (distinct) + 0 coll) 2.889020114942531 ms => 2.44890487804879 ms (-15%)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.