Very awesome :D!
Cheers, Jan
> On 09 Dec 2015, at 10:39, Michał Marczyk <michal.marc...@gmail.com> wrote:
>
> 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 clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> <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 clojure+unsubscr...@googlegroups.com
> <mailto:clojure+unsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
