Hi,
I am pleased to announce the 0.0.13 release of data.avl, a Clojure
Contrib library providing highly performant drop-in replacements for
Clojure(Script)'s built-in sorted maps and sets with the following
headline features:
0. performance often superior to the built-ins (owing to the smaller
height of AVL trees), see end of this email for some benchmarks
1. logarithmic-time slicing and splits:
(avl/split-key 3 (avl/sorted-set 0 1 2 3 4 5))
;= [#{0 1 2} 3 #{4 5 6}]
(avl/split-at 2 (avl/sorted-set 0 1 2 3 4 5))
;= [#{0 1} #{2 3 4 5}]
(avl/subrange (avl/sorted-set 0 1 2 3 4 5) >= 2 < 5)
;= #{2 3 4}
All returned collections are independent from the originals for GC
purposes (no holding on to out-of-range keys present in the
original collections), all operations run in O(log n) time in
asymptotic terms, and actually fast in real-world terms.
2. logarithmic-time access by rank and rank queries:
(nth (avl/sorted-set 0 1 2) 1)
;= 1
(avl/rank-of (avl/sorted-map-by > 0 0 1 1 2 2) 0)
;= 2
3. nearest-neighbour lookups:
(avl/nearest (avl/sorted-set 0 1 2) < 1)
;= 0
The complete clojure.core sorted collections API is also supported, as
is the transient API. See the README for more detailed examples and
feature descriptions.
Fixed in this release:
1. IMeta and IFn implementations now use correct method names in the
ClojureScript version.
2. sorted-map/sorted-map-by now throw exceptions if no value is
provided for the final key (in other words, if an odd number of
arguments is passed in) – patch by Andy Fingerhut, thanks!
Changed in this release:
1. Seqs over data.avl maps now use node objects themselves as map
entries. This is in line with the behaviour of Clojure's built-in
sorted maps. Previously seqs over data.avl maps used
freshly-allocated map entry objects; this had the benefit of not
holding on to subtrees in some scenarios, however not without some
performance and GC pressure cost to regular traversals. Note that
the new behaviour allows the user to rewrap key/value pairs as map
entries if they so choose in a separate map step.
2. Because of 1., AVL nodes now implement vector and map entry
interfaces.
Cheers,
Michał
;;; A handful of benchmarks
; CIDER 0.9.1 (Java 1.8.0_45-internal, Clojure 1.8.0-RC2, nREPL 0.2.10)
user> (def ks (range 10000))
#'user/ks
user> (def ksks (doall (interleave ks ks)))
#'user/ksks
user> (def m1 (apply sorted-map ksks))
#'user/m1
user> (def m2 (apply avl/sorted-map ksks))
#'user/m2
user> (.tree m1)
[4095 4095]
user> (.getTree m2)
[4095 4095]
user> (let []
(prn :>>>>>>>>> 0)
(c/quick-bench (get m1 0))
(c/quick-bench (get m2 0))
(prn :>>>>>>>>> 4095)
(c/quick-bench (get m1 4095))
(c/quick-bench (get m2 4095))
(prn :>>>>>>>>> 9999)
(c/quick-bench (get m1 9999))
(c/quick-bench (get m2 9999)))
:>>>>>>>>> 0
WARNING: Final GC required 9.525315094951035 % of runtime
WARNING: Final GC required 88.3127760569387 % of runtime
Evaluation count : 2280474 in 6 samples of 380079 calls.
Execution time mean : 262.138936 ns
Execution time std-deviation : 56.938518 ns
Execution time lower quantile : 237.779848 ns ( 2.5%)
Execution time upper quantile : 360.756510 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 64.2134 % Variance is severely inflated by
outliers
WARNING: Final GC required 78.56747149813818 % of runtime
Evaluation count : 2280498 in 6 samples of 380083 calls.
Execution time mean : 261.626921 ns
Execution time std-deviation : 42.454179 ns
Execution time lower quantile : 241.444705 ns ( 2.5%)
Execution time upper quantile : 335.120524 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 47.5275 % Variance is moderately inflated by
outliers
:>>>>>>>>> 4095
WARNING: Final GC required 168.0614206986717 % of runtime
Evaluation count : 10666656 in 6 samples of 1777776 calls.
Execution time mean : 25.939625 ns
Execution time std-deviation : 4.135726 ns
Execution time lower quantile : 22.648015 ns ( 2.5%)
Execution time upper quantile : 32.134865 ns (97.5%)
Overhead used : 20.503990 ns
WARNING: Final GC required 293.8046791844393 % of runtime
Evaluation count : 10666656 in 6 samples of 1777776 calls.
Execution time mean : 24.609377 ns
Execution time std-deviation : 1.015680 ns
Execution time lower quantile : 23.720800 ns ( 2.5%)
Execution time upper quantile : 26.283825 ns (97.5%)
Overhead used : 20.503990 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
:>>>>>>>>> 9999
WARNING: Final GC required 78.97582727524912 % of runtime
Evaluation count : 1140522 in 6 samples of 190087 calls.
Execution time mean : 529.174236 ns
Execution time std-deviation : 23.230815 ns
Execution time lower quantile : 507.273359 ns ( 2.5%)
Execution time upper quantile : 555.512190 ns (97.5%)
Overhead used : 20.503990 ns
WARNING: Final GC required 87.49793028683956 % of runtime
Evaluation count : 1675602 in 6 samples of 279267 calls.
Execution time mean : 349.221745 ns
Execution time std-deviation : 12.233391 ns
Execution time lower quantile : 337.078699 ns ( 2.5%)
Execution time upper quantile : 363.114841 ns (97.5%)
Overhead used : 20.503990 ns
nil
user> (let []
(prn :>>>>>>>>> 0)
(c/quick-bench (assoc m1 0 :foo))
(c/quick-bench (assoc m2 0 :foo))
(prn :>>>>>>>>> 4095)
(c/quick-bench (assoc m1 4095 :foo))
(c/quick-bench (assoc m2 4095 :foo))
(prn :>>>>>>>>> 9999)
(c/quick-bench (assoc m1 9999 :foo))
(c/quick-bench (assoc m2 9999 :foo)))
:>>>>>>>>> 0
WARNING: Final GC required 79.70772192106699 % of runtime
Evaluation count : 773178 in 6 samples of 128863 calls.
Execution time mean : 808.507111 ns
Execution time std-deviation : 61.200680 ns
Execution time lower quantile : 762.270652 ns ( 2.5%)
Execution time upper quantile : 908.666430 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 15.4042 % Variance is moderately inflated by
outliers
WARNING: Final GC required 84.33400243271444 % of runtime
Evaluation count : 998820 in 6 samples of 166470 calls.
Execution time mean : 630.508831 ns
Execution time std-deviation : 91.017019 ns
Execution time lower quantile : 575.191356 ns ( 2.5%)
Execution time upper quantile : 781.646846 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 31.9448 % Variance is moderately inflated by
outliers
:>>>>>>>>> 4095
WARNING: Final GC required 103.2558412368837 % of runtime
Evaluation count : 5464860 in 6 samples of 910810 calls.
Execution time mean : 91.206820 ns
Execution time std-deviation : 1.078039 ns
Execution time lower quantile : 90.392738 ns ( 2.5%)
Execution time upper quantile : 92.936436 ns (97.5%)
Overhead used : 20.503990 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
WARNING: Final GC required 106.0412652794005 % of runtime
Evaluation count : 7908216 in 6 samples of 1318036 calls.
Execution time mean : 59.355120 ns
Execution time std-deviation : 9.429309 ns
Execution time lower quantile : 54.620319 ns ( 2.5%)
Execution time upper quantile : 75.502688 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 47.4203 % Variance is moderately inflated by
outliers
:>>>>>>>>> 9999
WARNING: Final GC required 75.58865946291652 % of runtime
Evaluation count : 400044 in 6 samples of 66674 calls.
Execution time mean : 1.594050 µs
Execution time std-deviation : 219.064194 ns
Execution time lower quantile : 1.489967 µs ( 2.5%)
Execution time upper quantile : 1.974760 µs (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 31.8012 % Variance is moderately inflated by
outliers
WARNING: Final GC required 76.01108878983499 % of runtime
Evaluation count : 803382 in 6 samples of 133897 calls.
Execution time mean : 791.765204 ns
Execution time std-deviation : 168.051615 ns
Execution time lower quantile : 717.559893 ns ( 2.5%)
Execution time upper quantile : 1.083012 µs (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 64.0975 % Variance is severely inflated by
outliers
nil
user> (let []
(prn :>>>>>>>>> 0)
(c/quick-bench (dissoc m1 0))
(c/quick-bench (dissoc m2 0))
(prn :>>>>>>>>> 4095)
(c/quick-bench (dissoc m1 4095))
(c/quick-bench (dissoc m2 4095))
(prn :>>>>>>>>> 9999)
(c/quick-bench (dissoc m1 9999))
(c/quick-bench (dissoc m2 9999)))
:>>>>>>>>> 0
WARNING: Final GC required 79.81354408905999 % of runtime
Evaluation count : 817806 in 6 samples of 136301 calls.
Execution time mean : 787.499930 ns
Execution time std-deviation : 110.974262 ns
Execution time lower quantile : 713.765585 ns ( 2.5%)
Execution time upper quantile : 918.651003 ns (97.5%)
Overhead used : 20.503990 ns
WARNING: Final GC required 90.61234353859703 % of runtime
Evaluation count : 946194 in 6 samples of 157699 calls.
Execution time mean : 635.509493 ns
Execution time std-deviation : 77.766037 ns
Execution time lower quantile : 597.459648 ns ( 2.5%)
Execution time upper quantile : 770.025631 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 31.4010 % Variance is moderately inflated by
outliers
:>>>>>>>>> 4095
WARNING: Final GC required 93.51991061746037 % of runtime
Evaluation count : 798942 in 6 samples of 133157 calls.
Execution time mean : 780.434630 ns
Execution time std-deviation : 99.772759 ns
Execution time lower quantile : 734.638029 ns ( 2.5%)
Execution time upper quantile : 954.367116 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 31.5629 % Variance is moderately inflated by
outliers
WARNING: Final GC required 94.43044983352105 % of runtime
Evaluation count : 1809150 in 6 samples of 301525 calls.
Execution time mean : 322.068319 ns
Execution time std-deviation : 35.241688 ns
Execution time lower quantile : 305.599532 ns ( 2.5%)
Execution time upper quantile : 382.815046 ns (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 30.9167 % Variance is moderately inflated by
outliers
:>>>>>>>>> 9999
WARNING: Final GC required 80.04485962265078 % of runtime
Evaluation count : 534186 in 6 samples of 89031 calls.
Execution time mean : 1.147512 µs
Execution time std-deviation : 81.941160 ns
Execution time lower quantile : 1.091490 µs ( 2.5%)
Execution time upper quantile : 1.285711 µs (97.5%)
Overhead used : 20.503990 ns
Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
Variance from outliers : 15.2480 % Variance is moderately inflated by
outliers
WARNING: Final GC required 87.89464958140888 % of runtime
Evaluation count : 802812 in 6 samples of 133802 calls.
Execution time mean : 725.959454 ns
Execution time std-deviation : 10.399885 ns
Execution time lower quantile : 714.981891 ns ( 2.5%)
Execution time upper quantile : 738.599813 ns (97.5%)
Overhead used : 20.503990 ns
nil
user> (let [is (vec (range 10000))
f (fn [m]
(reduce + 0 (map #(get m %) is)))]
(assert (= (f m1) (f m2) (reduce + (range 10000))))
(c/quick-bench (f m1))
(c/quick-bench (f m2)))
WARNING: Final GC required 77.30439008557758 % of runtime
Evaluation count : 162 in 6 samples of 27 calls.
Execution time mean : 3.925850 ms
Execution time std-deviation : 103.741280 µs
Execution time lower quantile : 3.819278 ms ( 2.5%)
Execution time upper quantile : 4.051602 ms (97.5%)
Overhead used : 20.503990 ns
WARNING: Final GC required 78.43042165220535 % of runtime
Evaluation count : 168 in 6 samples of 28 calls.
Execution time mean : 3.675097 ms
Execution time std-deviation : 75.445252 µs
Execution time lower quantile : 3.619136 ms ( 2.5%)
Execution time upper quantile : 3.778653 ms (97.5%)
Overhead used : 20.503990 ns
nil
user> (let [is (vec (range 10000))
f (fn [m]
(reduce #(assoc %1 %2 (inc %2)) m is))]
(assert (= (f m1) (f m2)))
(c/quick-bench (f m1))
(c/quick-bench (f m2)))
WARNING: Final GC required 78.53825098940767 % of runtime
Evaluation count : 60 in 6 samples of 10 calls.
Execution time mean : 11.148259 ms
Execution time std-deviation : 467.628721 µs
Execution time lower quantile : 10.834884 ms ( 2.5%)
Execution time upper quantile : 11.933042 ms (97.5%)
Overhead used : 20.503990 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
WARNING: Final GC required 72.97434514655737 % of runtime
Evaluation count : 90 in 6 samples of 15 calls.
Execution time mean : 7.985624 ms
Execution time std-deviation : 1.351866 ms
Execution time lower quantile : 6.979696 ms ( 2.5%)
Execution time upper quantile : 9.972527 ms (97.5%)
Overhead used : 20.503990 ns
nil
user> (let [is (vec (filter odd? (range 10000)))
f (fn [m]
(reduce dissoc m is))]
(assert (= (f m1) (f m2)))
(c/quick-bench (f m1))
(c/quick-bench (f m2)))
WARNING: Final GC required 85.74697222348942 % of runtime
Evaluation count : 150 in 6 samples of 25 calls.
Execution time mean : 4.195302 ms
Execution time std-deviation : 110.162882 µs
Execution time lower quantile : 4.069522 ms ( 2.5%)
Execution time upper quantile : 4.331845 ms (97.5%)
Overhead used : 20.503990 ns
WARNING: Final GC required 76.40699619760906 % of runtime
Evaluation count : 168 in 6 samples of 28 calls.
Execution time mean : 3.932373 ms
Execution time std-deviation : 373.993149 µs
Execution time lower quantile : 3.657881 ms ( 2.5%)
Execution time upper quantile : 4.386778 ms (97.5%)
Overhead used : 20.503990 ns
nil
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
