[ANN] data.avl 0.0.12 -- sorted collections with slice, nth, transient support
165 views
Skip to first unread message
Michał Marczyk
Apr 23, 2014, 8:59:59 AM4/23/14
to clojure
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ł
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ł
Alex Miller
Apr 23, 2014, 12:37:37 PM4/23/14
to clo...@googlegroups.com
Great work as always!
Are there any places where data.avl performs worse than the built-in sorted maps and sets?
Michał Marczyk
Apr 24, 2014, 2:51:19 AM4/24/14
to clojure
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
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
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
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
Michał Marczyk
Apr 29, 2014, 6:11:01 PM4/29/14
to clojure
Here's a round of benchmarks for the new functions
(avl/{nearest,subrange,split-at,split-key}), with a lookup benchmark
included as a point of reference.
Cheers,
Michał
(let [m (apply avl/sorted-map
(interleave (range 100000) (range 100000)))]
(c/bench (get m 99999))
(c/bench (avl/nearest m < 100000))
(c/bench (avl/subrange m >= 10000 < 75000))
(c/bench (avl/split-at 30000 m))
(c/bench (avl/split-key 30000 m)))
WARNING: Final GC required 4.244287716089524 % of runtime
Evaluation count : 213693000 in 60 samples of 3561550 calls.
Execution time mean : 278.027014 ns
Execution time std-deviation : 4.284738 ns
Execution time lower quantile : 273.830485 ns ( 2.5%)
Execution time upper quantile : 287.103701 ns (97.5%)
Overhead used : 2.289159 ns
Found 10 outliers in 60 samples (16.6667 %)
low-severe 9 (15.0000 %)
Execution time mean : 352.393290 ns
Execution time std-deviation : 5.226142 ns
Execution time lower quantile : 346.698762 ns ( 2.5%)
Execution time upper quantile : 364.246208 ns (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 4 (6.6667 %)
Execution time mean : 45.605490 µs
Execution time std-deviation : 682.937868 ns
Execution time lower quantile : 44.839275 µs ( 2.5%)
Execution time upper quantile : 47.176367 µs (97.5%)
Overhead used : 2.289159 ns
Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Execution time mean : 25.715076 µs
Execution time std-deviation : 366.924494 ns
Execution time lower quantile : 25.249912 µs ( 2.5%)
Execution time upper quantile : 26.592419 µs (97.5%)
Overhead used : 2.289159 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
Evaluation count : 2596800 in 60 samples of 43280 calls.
Execution time mean : 23.343989 µs
Execution time std-deviation : 308.669720 ns
Execution time lower quantile : 22.908707 µs ( 2.5%)
Execution time upper quantile : 24.143221 µs (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 4 (6.6667 %)
(avl/{nearest,subrange,split-at,split-key}), with a lookup benchmark
included as a point of reference.
Cheers,
Michał
(let [m (apply avl/sorted-map
(interleave (range 100000) (range 100000)))]
(c/bench (get m 99999))
(c/bench (avl/nearest m < 100000))
(c/bench (avl/subrange m >= 10000 < 75000))
(c/bench (avl/split-at 30000 m))
(c/bench (avl/split-key 30000 m)))
WARNING: Final GC required 4.244287716089524 % of runtime
Evaluation count : 213693000 in 60 samples of 3561550 calls.
Execution time mean : 278.027014 ns
Execution time std-deviation : 4.284738 ns
Execution time lower quantile : 273.830485 ns ( 2.5%)
Execution time upper quantile : 287.103701 ns (97.5%)
Overhead used : 2.289159 ns
Found 10 outliers in 60 samples (16.6667 %)
low-severe 9 (15.0000 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 168881400 in 60 samples of 2814690 calls.
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Execution time mean : 352.393290 ns
Execution time std-deviation : 5.226142 ns
Execution time lower quantile : 346.698762 ns ( 2.5%)
Execution time upper quantile : 364.246208 ns (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 1333200 in 60 samples of 22220 calls.
Execution time mean : 45.605490 µs
Execution time std-deviation : 682.937868 ns
Execution time lower quantile : 44.839275 µs ( 2.5%)
Execution time upper quantile : 47.176367 µs (97.5%)
Overhead used : 2.289159 ns
Found 3 outliers in 60 samples (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Evaluation count : 2338740 in 60 samples of 38979 calls.
Execution time mean : 25.715076 µs
Execution time std-deviation : 366.924494 ns
Execution time lower quantile : 25.249912 µs ( 2.5%)
Execution time upper quantile : 26.592419 µs (97.5%)
Overhead used : 2.289159 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
Execution time mean : 23.343989 µs
Execution time std-deviation : 308.669720 ns
Execution time lower quantile : 22.908707 µs ( 2.5%)
Execution time upper quantile : 24.143221 µs (97.5%)
Overhead used : 2.289159 ns
Found 4 outliers in 60 samples (6.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
Reply all
Reply to author
Forward
0 new messages