Benchmarking DataScript’s btset against Clojure’s sorted-set/vector

btset_bench.clj

(defn bench-btset []
  (doseq [distinct    [:distinct :duplicates]
          size        [20000]
          [tn target] [["sorted-set" (sorted-set)]
                       ["btset"      (btset/btset)]
                       ["vector"     []]]
          :let [range          (if (= :distinct distinct)
                                 (shuffle (range size))
                                 (repeatedly size #(rand-int size)))
                shuffled-range (shuffle range)
                set            (into target range)]]
    
    (perf/bench {:target tn :test "conj" :size size}
      (into target range)) ;; conj test
    
    (when (re-find #"set" tn)
      
      (perf/bench {:target tn :test "disj" :size size}
        (reduce disj set shuffled-range)) ;; disj test
        
      (perf/bench {:target tn :test "lookup" :size size}
        (doseq [i shuffled-range] ;; lookup test
          (contains? set i))))

    (perf/bench {:target tn :test "iterate" :size size}
      (doseq [x set] ;; iterate test
        (+ 1 x)))

    (perf/bench {:target tn :test "reduce" :size size}
      (reduce + 0 set)))) ;; reduce test


;; RESULTS

(shuffle (range size))

sorted-set      conj     20000     17.835875683029492
     btset      conj     20000     18.37036214967569
    vector      conj     20000     0.34959030593729185

sorted-set      disj     20000     18.168823783596356
     btset      disj     20000     22.395973920822144

sorted-set    lookup     20000     5.9654844645191645
     btset    lookup     20000     7.042519446611404

sorted-set   iterate     20000     2.189330797739651
     btset   iterate     20000     0.3153424795693571
    vector   iterate     20000     0.141714130447539

sorted-set    reduce     20000     0.7951769507593579
     btset    reduce     20000     0.263221187638609
    vector    reduce     20000     0.222974837649373


(repeatedly size #(rand-int size))

sorted-set      conj     20000     15.006242486408778
     btset      conj     20000     15.08962018574987
    vector      conj     20000     0.6093513903112122

sorted-set      disj     20000     13.928321325033902
     btset      disj     20000     16.767084299524626

     btset    lookup     20000     7.977152438805653
sorted-set    lookup     20000     6.959129619995753

sorted-set   iterate     20000     1.5999760587064047
     btset   iterate     20000     0.22097026733373173
    vector   iterate     20000     0.16294185667744676

sorted-set    reduce     20000     0.5970166869106747
     btset    reduce     20000     0.18763109173828396
    vector    reduce     20000     0.25666135153709313

java version "1.8.0_102"
Java(TM) SE Runtime Environment (build 1.8.0_102-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.102-b14, mixed mode)

Clojure 1.7.0

OS X 10.11.6 (15G1217), MacBook Pro (Retina, Mid 2012), Intel Core i7 2,3 GHz

Times are median execution time in milliseconds