Cheers Alex! See below for the results of yesterday's run of my benchmark suite for the basic operations. (I'll post some benchmark results for the new functions in a separate message sometime soon.)
In general, it's fair to expect (persistent) assoc/dissoc to be slower with data.avl maps, since AVL trees do more work to rebalance themselves than red-black trees. (That's on average, of course.) The upside is that lookups in AVL trees are faster on average, sometimes quite dramatically, due to the trees being shallower. It's worth pointing out that this really is "on average" -- individual timings depend on the path through the tree the lookup operation needs to traverse, and for nodes at exactly the same position in the tree the built-ins are slightly faster (23.9 ns vs. 25.5 ns for a lookup succeeding at the root node, see the (get % 131071) benchmark case below; as I recall, 0 happens to occupy the same position in both benchmark maps as well) -- but if we hit a deeper part of a red-black tree, data.avl is likely to win by a large margin, as in the case of the 311 ns (data.avl) vs. 588 ns (built-in) result for looking up 299999 in the two benchmark maps. For longer chains of "updates" -- including construction of instances with more than a handful of elements -- data.avl wins thanks to its support for transients; in particular, inserting 300000 entries in ascending order of keys took 197 ns with data.avl's sorted-map during my benchmark run yesterday vs. 317 ns with the built-in. ;;; the setup: (def ks (range 300000)) (def ksks (interleave ks ks)) (def rb (apply sorted-map ksks)) (def avl (apply avl/sorted-map ksks)) ;;; the actual benchmark run Clojure 1.5.1 user=> (all-benchmarks) (lookup-benchmarks) =================== (c/bench (get avl 0)) WARNING: Final GC required 17.95425214438086 % of runtime WARNING: Final GC required 1.44548564181991 % of runtime Evaluation count : 233348580 in 60 samples of 3889143 calls. Execution time mean : 257.269857 ns Execution time std-deviation : 2.083817 ns Execution time lower quantile : 254.044412 ns ( 2.5%) Execution time upper quantile : 261.944879 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (get rb 0)) WARNING: Final GC required 1.443796805141993 % of runtime Evaluation count : 245219880 in 60 samples of 4086998 calls. Execution time mean : 244.222199 ns Execution time std-deviation : 1.613109 ns Execution time lower quantile : 240.981893 ns ( 2.5%) Execution time upper quantile : 247.680884 ns (97.5%) Overhead used : 2.115402 ns (c/bench (get avl 131071)) WARNING: Final GC required 1.538687432575083 % of runtime Evaluation count : 2189108520 in 60 samples of 36485142 calls. Execution time mean : 25.463933 ns Execution time std-deviation : 0.159206 ns Execution time lower quantile : 25.242537 ns ( 2.5%) Execution time upper quantile : 25.846594 ns (97.5%) Overhead used : 2.115402 ns Found 2 outliers in 60 samples (3.3333 %) low-severe 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (get rb 131071)) WARNING: Final GC required 1.544907815808739 % of runtime Evaluation count : 2306183280 in 60 samples of 38436388 calls. Execution time mean : 23.873777 ns Execution time std-deviation : 0.243375 ns Execution time lower quantile : 23.590693 ns ( 2.5%) Execution time upper quantile : 24.503250 ns (97.5%) Overhead used : 2.115402 ns Found 3 outliers in 60 samples (5.0000 %) low-severe 1 (1.6667 %) low-mild 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (get avl 299999)) WARNING: Final GC required 1.4317314000518289 % of runtime Evaluation count : 192818880 in 60 samples of 3213648 calls. Execution time mean : 311.396507 ns Execution time std-deviation : 2.029572 ns Execution time lower quantile : 308.219265 ns ( 2.5%) Execution time upper quantile : 315.544485 ns (97.5%) Overhead used : 2.115402 ns (c/bench (get rb 299999)) WARNING: Final GC required 1.424486278904469 % of runtime Evaluation count : 102060180 in 60 samples of 1701003 calls. Execution time mean : 588.846851 ns Execution time std-deviation : 3.124839 ns Execution time lower quantile : 584.394022 ns ( 2.5%) Execution time upper quantile : 594.415623 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (construction-benchmarks) ========================= (c/bench (apply avl/sorted-map ksks)) WARNING: Final GC required 5.3006864743254365 % of runtime Evaluation count : 360 in 60 samples of 6 calls. Execution time mean : 197.715700 ms Execution time std-deviation : 1.410989 ms Execution time lower quantile : 195.528307 ms ( 2.5%) Execution time upper quantile : 200.733827 ms (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (apply sorted-map ksks)) WARNING: Final GC required 4.7280630882454275 % of runtime Evaluation count : 240 in 60 samples of 4 calls. Execution time mean : 317.073457 ms Execution time std-deviation : 1.799728 ms Execution time lower quantile : 314.404224 ms ( 2.5%) Execution time upper quantile : 320.886432 ms (97.5%) Overhead used : 2.115402 ns (assoc-benchmarks) ================== (c/bench (assoc avl -1 -1)) WARNING: Final GC required 1.4272766765260692 % of runtime Evaluation count : 94731120 in 60 samples of 1578852 calls. Execution time mean : 640.949880 ns Execution time std-deviation : 5.268487 ns Execution time lower quantile : 632.929494 ns ( 2.5%) Execution time upper quantile : 651.026693 ns (97.5%) Overhead used : 2.115402 ns (c/bench (assoc rb -1 -1)) WARNING: Final GC required 1.4813094150003698 % of runtime Evaluation count : 101334900 in 60 samples of 1688915 calls. Execution time mean : 586.478825 ns Execution time std-deviation : 6.445327 ns Execution time lower quantile : 577.251444 ns ( 2.5%) Execution time upper quantile : 600.983215 ns (97.5%) Overhead used : 2.115402 ns Found 2 outliers in 60 samples (3.3333 %) low-severe 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (assoc avl 131071.5 131071.5)) WARNING: Final GC required 1.44705071828203 % of runtime Evaluation count : 89874900 in 60 samples of 1497915 calls. Execution time mean : 674.654642 ns Execution time std-deviation : 7.380872 ns Execution time lower quantile : 662.647528 ns ( 2.5%) Execution time upper quantile : 690.152387 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (assoc rb 131071.5 131071.5)) WARNING: Final GC required 1.476998263803252 % of runtime Evaluation count : 104773620 in 60 samples of 1746227 calls. Execution time mean : 581.851687 ns Execution time std-deviation : 5.236315 ns Execution time lower quantile : 573.394307 ns ( 2.5%) Execution time upper quantile : 591.444744 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (assoc avl 300000 300000)) WARNING: Final GC required 1.4573754017132279 % of runtime Evaluation count : 52686120 in 60 samples of 878102 calls. Execution time mean : 1.143503 µs Execution time std-deviation : 8.905816 ns Execution time lower quantile : 1.128491 µs ( 2.5%) Execution time upper quantile : 1.161180 µs (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (assoc rb 300000 300000)) WARNING: Final GC required 1.4453736865925522 % of runtime Evaluation count : 61066200 in 60 samples of 1017770 calls. Execution time mean : 986.964073 ns Execution time std-deviation : 9.099675 ns Execution time lower quantile : 971.014487 ns ( 2.5%) Execution time upper quantile : 1.005402 µs (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (dissoc-benchmarks) =================== (c/bench (dissoc avl 0)) WARNING: Final GC required 1.409625923637254 % of runtime Evaluation count : 95106480 in 60 samples of 1585108 calls. Execution time mean : 632.360192 ns Execution time std-deviation : 6.758100 ns Execution time lower quantile : 622.348742 ns ( 2.5%) Execution time upper quantile : 644.801029 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (dissoc rb 0)) WARNING: Final GC required 1.4395319870486911 % of runtime Evaluation count : 98152980 in 60 samples of 1635883 calls. Execution time mean : 616.735094 ns Execution time std-deviation : 7.850262 ns Execution time lower quantile : 603.999108 ns ( 2.5%) Execution time upper quantile : 631.343617 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (dissoc avl 131071)) WARNING: Final GC required 1.521591424378216 % of runtime Evaluation count : 221033940 in 60 samples of 3683899 calls. Execution time mean : 274.098530 ns Execution time std-deviation : 2.452287 ns Execution time lower quantile : 270.107011 ns ( 2.5%) Execution time upper quantile : 279.445027 ns (97.5%) Overhead used : 2.115402 ns Found 6 outliers in 60 samples (10.0000 %) low-severe 6 (10.0000 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (dissoc rb 131071)) WARNING: Final GC required 1.518838691811953 % of runtime Evaluation count : 110069460 in 60 samples of 1834491 calls. Execution time mean : 544.040051 ns Execution time std-deviation : 6.594133 ns Execution time lower quantile : 533.460485 ns ( 2.5%) Execution time upper quantile : 559.612526 ns (97.5%) Overhead used : 2.115402 ns Found 2 outliers in 60 samples (3.3333 %) low-severe 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (dissoc avl 299999)) WARNING: Final GC required 1.4221011007954931 % of runtime Evaluation count : 55003980 in 60 samples of 916733 calls. Execution time mean : 1.106014 µs Execution time std-deviation : 7.937471 ns Execution time lower quantile : 1.090420 µs ( 2.5%) Execution time upper quantile : 1.119023 µs (97.5%) Overhead used : 2.115402 ns (c/bench (dissoc rb 299999)) WARNING: Final GC required 1.4984644559577371 % of runtime Evaluation count : 69322080 in 60 samples of 1155368 calls. Execution time mean : 866.398607 ns Execution time std-deviation : 9.504058 ns Execution time lower quantile : 851.988220 ns ( 2.5%) Execution time upper quantile : 887.694665 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (reduce-kv-benchmarks) ====================== (c/bench (reduce-kv + 0 avl)) WARNING: Final GC required 1.4943999357205922 % of runtime Evaluation count : 1680 in 60 samples of 28 calls. Execution time mean : 37.019830 ms Execution time std-deviation : 211.307503 µs Execution time lower quantile : 36.602312 ms ( 2.5%) Execution time upper quantile : 37.377517 ms (97.5%) Overhead used : 2.115402 ns (c/bench (reduce-kv + 0 rb)) WARNING: Final GC required 1.470636145118843 % of runtime Evaluation count : 1500 in 60 samples of 25 calls. Execution time mean : 41.019274 ms Execution time std-deviation : 285.334885 µs Execution time lower quantile : 40.541044 ms ( 2.5%) Execution time upper quantile : 41.504517 ms (97.5%) Overhead used : 2.115402 ns (select-benchmarks) =================== (c/bench (nth avl 0)) WARNING: Final GC required 1.494616669407989 % of runtime Evaluation count : 222102300 in 60 samples of 3701705 calls. Execution time mean : 269.443606 ns Execution time std-deviation : 2.158203 ns Execution time lower quantile : 265.797360 ns ( 2.5%) Execution time upper quantile : 273.406291 ns (97.5%) Overhead used : 2.115402 ns (c/bench (nth (seq rb) 0)) WARNING: Final GC required 1.420496053869465 % of runtime Evaluation count : 272733660 in 60 samples of 4545561 calls. Execution time mean : 218.593345 ns Execution time std-deviation : 1.965696 ns Execution time lower quantile : 215.009791 ns ( 2.5%) Execution time upper quantile : 221.595814 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (nth avl 131071)) WARNING: Final GC required 1.4913582150274651 % of runtime Evaluation count : 2340271560 in 60 samples of 39004526 calls. Execution time mean : 23.958321 ns Execution time std-deviation : 0.273586 ns Execution time lower quantile : 23.512070 ns ( 2.5%) Execution time upper quantile : 24.470681 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (nth (seq rb) 131071)) WARNING: Final GC required 1.442980458629981 % of runtime Evaluation count : 15240 in 60 samples of 254 calls. Execution time mean : 3.971846 ms Execution time std-deviation : 37.538641 µs Execution time lower quantile : 3.908583 ms ( 2.5%) Execution time upper quantile : 4.046135 ms (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (nth avl 299999)) WARNING: Final GC required 1.396166903433299 % of runtime Evaluation count : 62932200 in 60 samples of 1048870 calls. Execution time mean : 966.061999 ns Execution time std-deviation : 12.227245 ns Execution time lower quantile : 950.801928 ns ( 2.5%) Execution time upper quantile : 994.606117 ns (97.5%) Overhead used : 2.115402 ns Found 4 outliers in 60 samples (6.6667 %) low-severe 3 (5.0000 %) low-mild 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (nth (seq rb) 299999)) WARNING: Final GC required 1.411884727250311 % of runtime Evaluation count : 3480 in 60 samples of 58 calls. Execution time mean : 17.404103 ms Execution time std-deviation : 125.910185 µs Execution time lower quantile : 17.180238 ms ( 2.5%) Execution time upper quantile : 17.698525 ms (97.5%) Overhead used : 2.115402 ns Found 2 outliers in 60 samples (3.3333 %) low-severe 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (rank-of-benchmarks) ==================== (c/bench (avl/rank-of avl 0)) WARNING: Final GC required 1.410760546097934 % of runtime Evaluation count : 228328740 in 60 samples of 3805479 calls. Execution time mean : 262.229200 ns Execution time std-deviation : 1.545106 ns Execution time lower quantile : 260.026098 ns ( 2.5%) Execution time upper quantile : 265.501717 ns (97.5%) Overhead used : 2.115402 ns (c/bench (rb-rank-of rb 0)) WARNING: Final GC required 1.528903400498107 % of runtime Evaluation count : 122421060 in 60 samples of 2040351 calls. Execution time mean : 489.908995 ns Execution time std-deviation : 4.341988 ns Execution time lower quantile : 483.130264 ns ( 2.5%) Execution time upper quantile : 497.383919 ns (97.5%) Overhead used : 2.115402 ns Found 1 outliers in 60 samples (1.6667 %) low-severe 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (avl/rank-of avl 131071)) WARNING: Final GC required 1.601437516988401 % of runtime Evaluation count : 1923909240 in 60 samples of 32065154 calls. Execution time mean : 29.024185 ns Execution time std-deviation : 0.271967 ns Execution time lower quantile : 28.621628 ns ( 2.5%) Execution time upper quantile : 29.530897 ns (97.5%) Overhead used : 2.115402 ns Found 3 outliers in 60 samples (5.0000 %) low-severe 2 (3.3333 %) low-mild 1 (1.6667 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (rb-rank-of rb 131071)) WARNING: Final GC required 1.5253557008726901 % of runtime Evaluation count : 2700 in 60 samples of 45 calls. Execution time mean : 22.259014 ms Execution time std-deviation : 176.571734 µs Execution time lower quantile : 21.949530 ms ( 2.5%) Execution time upper quantile : 22.639924 ms (97.5%) Overhead used : 2.115402 ns (c/bench (avl/rank-of avl 299999)) WARNING: Final GC required 1.46116006270368 % of runtime Evaluation count : 139283400 in 60 samples of 2321390 calls. Execution time mean : 429.526612 ns Execution time std-deviation : 3.425081 ns Execution time lower quantile : 425.422751 ns ( 2.5%) Execution time upper quantile : 437.939328 ns (97.5%) Overhead used : 2.115402 ns Found 2 outliers in 60 samples (3.3333 %) low-severe 2 (3.3333 %) Variance from outliers : 1.6389 % Variance is slightly inflated by outliers (c/bench (rb-rank-of rb 299999)) WARNING: Final GC required 1.5002581976759541 % of runtime Evaluation count : 1200 in 60 samples of 20 calls. Execution time mean : 50.728340 ms Execution time std-deviation : 353.191435 µs Execution time lower quantile : 50.130720 ms ( 2.5%) Execution time upper quantile : 51.368250 ms (97.5%) Overhead used : 2.115402 ns nil On 23 April 2014 18:37, Alex Miller <a...@puredanger.com> wrote: > Great work as always! > > Are there any places where data.avl performs worse than the built-in sorted > maps and sets? > > > On Wednesday, April 23, 2014 7:59:59 AM UTC-5, Michał Marczyk wrote: >> >> Hi, >> >> I am pleased to announce the 0.0.12 release of data.avl, a Clojure >> Contrib library providing drop-in replacements for Clojure(Script)'s >> built-in sorted maps and sets with additional functionality: >> >> 1. real (non-view) logarithmic-time slicing and splits; >> >> 2. logarithmic-time nearest neighbour lookups and rank queries; >> >> 3. support for transients. >> >> This release is identical to 0.0.12-alpha1 except for the fact that >> the Vars clojure.data.avl/empty-{set,map}-hash{eq,code} are now marked >> private, as they should be. >> >> Changes since 0.0.11 include an important fix to the rebalancing >> algorithm, so I would strongly advise all users of 0.0.11 to upgrade >> as soon as possible. There are also several new additions to the API, >> on which more below. >> >> [org.clojure/data.avl "0.0.12"] >> >> <dependency> >> <groupId>org.clojure</groupId> >> <artifactId>data.avl</artifactId> >> <version>0.0.12</version> >> </dependency> >> >> org.clojure:data.avl:0.0.12 >> >> The following transcript of a REPL session includes calls to each of >> the new public functions: >> >> (require '[clojure.data.avl :as avl]) >> >> (avl/nearest (avl/sorted-set 0 1 2) < 2) >> ;= 1 >> >> (avl/subrange (avl/sorted-set 0 1 2 3 4 5) >= 1 < 4) >> ;= #{1 2 3} >> >> (avl/split-at 2 (avl/sorted-set 0 1 2 3 4 5)) >> ;= [#{0 1} #{2 3 4 5}] >> >> (avl/split-key 3 (avl/sorted-set 0 2 4 6)) >> ;= [#{0 2} nil #{4 6}] >> >> All of these functions operate in time logarithmic in the size of >> their inputs. avl/subrange returns a data.avl collection of the same >> type as its input and completely independent from it -- that is, it >> shares structure with the input where possible, but does not hold on >> to any parts of the tree containing keys that should not be present in >> the output. avl/split-at and avl/split-key return similarly >> independent data.avl collections; the middle element of the vector >> returned by split-key is the element at the split key if present in >> the input, nil otherwise. >> >> "split" is the name usually applied in the literature to the operation >> that splits a tree into a "left" tree, a middle element and a "right" >> tree. "subrange" could also be called "slice". The split-* functions >> take their collection argument last to be consistent with >> clojure.core's split-at and split-with. Arguments accepted by subrange >> are analogous to those taken by subseq/rsubseq. >> >> Many thanks to the two new contributors to this release (listed here >> in chronological order of ticket creation): Pepijn de Vos, who >> prompted me to develop the above-mentioned new features by creating >> the ticket asking for what is now avl/nearest and mentioning >> java.util.Navigable{Map,Set}, and who provided new tests for >> avl/nearest; and Andy Fingerhut, who kept on top of the hashing >> changes and provided the initial implementation of new-style hasheq >> for data.avl with further tests. >> >> Cheers, >> Michał > > -- > 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. -- 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.