Skip to content
Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
390 lines (346 sloc) 15.7 KB
Marshall Abrams
Speed tests of key path functions from keypaths.clj
i.e. the functions list all paths through embedded maps by keys
;; NOTE: miner49r noted in an Issue here in 5/2018 that he has revised his SO answer,
;; and that it's now faster than his old answer, and in fact is faster than all other
;; solutions. This recent answer isn't included in this file, but can be found at
;; https://stackoverflow.com/a/38443772/1455243
Except where noted:
Clojure 1.9.0-alpha14
java version "1.8.0_112"
Java(TM) SE Runtime Environment (build 1.8.0_112-b16)
Java HotSpot(TM) 64-Bit Server VM (build 25.112-b16, mixed mode)
Criterium 0.4.4
Specter 1.0.0
Maps generated by make-big-map in keypaths.clj
The functions in keypaths.clj that I tested are by various authors.
The original versions can be found at:
http://stackoverflow.com/questions/21768802/how-can-i-get-the-nested-keys-of-a-map-in-clojure:
http://stackoverflow.com/questions/25268818/get-key-chains-of-a-tree-in-clojure
https://clojurians.slack.com/archives/C0FVDQLQ5/p1489779215484550
Times of functions in keypaths.clj on MacBook Air with a 27-path map
Summary in speed order:
miner49r-keypaths: 29.235649 µs
fast-specter-keypaths: 30.590085 µs
simple-specter-keypaths: 62.840230 µs
amalloy-keypaths: 75.740468 µs
noisesmith-keypaths: 87.693425 µs
AWebb-keypaths: 162.281035 µs
AlexMiller-keypaths: 243.756275 µs
Includes leaf values as well:
simple-specter-keypaths-with-leaves: 27.839481 µs
Times of functions in keypaths.clj on MacBook Air with a 6^6 = 46656-path map
Summary in speed order:
fast-specter-keypaths: 34.435956 ms
miner49r-keypaths: 37.897345 ms
simple-specter-keypaths: 119.600975 ms
noisesmith-keypaths: 180.448860 ms
amalloy-keypaths: 191.718783 ms
AWebb-keypaths: 193.172784 ms
AlexMiller-keypaths: 839.266448 ms
Includes leaf values as well:
simple-specter-keypaths-with-leaves: 35.945475 ms
Times of functions in keypaths.clj on MacBook Air with a 7^7 = 823543-path map
(These tests used Clojure 1.9.0alpha15.)
Summary in speed order:
fast-specter-keypaths: 577.668066 ms
miner49r-keypaths: 658.164156 ms
simple-specter-keypaths: 2.619101 sec
AWebb-keypaths: 3.158274 sec
noisesmith-keypaths: 4.568320 sec
amalloy-keypaths: 5.654859 sec
AlexMiller-keypaths: 26.941646 sec
Includes leaf values as well:
simple-specter-keypaths-with-leaves: 621.665484 ms
==============================================================
Times on MacBook Air with a 27-path map details:
user=> (test-keypath-fns (make-big-map 3 3))
-------------------------------------------------------
simple-specter-keypaths
Evaluation count : 978660 in 60 samples of 16311 calls.
Execution time mean : 62.840230 µs
Execution time std-deviation : 708.699588 ns
Execution time lower quantile : 61.177996 µs ( 2.5%)
Execution time upper quantile : 64.347385 µs (97.5%)
Overhead used : 5.183163 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 2 (3.3333 %)
low-mild 2 (3.3333 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
fast-specter-keypaths
Evaluation count : 1977000 in 60 samples of 32950 calls.
Execution time mean : 30.590085 µs
Execution time std-deviation : 436.141095 ns
Execution time lower quantile : 29.918400 µs ( 2.5%)
Execution time upper quantile : 31.695064 µs (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
miner49r-keypaths
Evaluation count : 2046540 in 60 samples of 34109 calls.
Execution time mean : 29.235649 µs
Execution time std-deviation : 363.741084 ns
Execution time lower quantile : 28.579011 µs ( 2.5%)
Execution time upper quantile : 29.891481 µs (97.5%)
Overhead used : 5.183163 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 1 (1.6667 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
amalloy-keypaths
Evaluation count : 802740 in 60 samples of 13379 calls.
Execution time mean : 75.740468 µs
Execution time std-deviation : 1.218964 µs
Execution time lower quantile : 73.892505 µs ( 2.5%)
Execution time upper quantile : 78.436584 µs (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
noisesmith-keypaths
Evaluation count : 693660 in 60 samples of 11561 calls.
Execution time mean : 87.693425 µs
Execution time std-deviation : 1.239632 µs
Execution time lower quantile : 85.617688 µs ( 2.5%)
Execution time upper quantile : 89.773737 µs (97.5%)
Overhead used : 5.183163 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 2 (3.3333 %)
low-mild 1 (1.6667 %)
high-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
AWebb-keypaths
Evaluation count : 376020 in 60 samples of 6267 calls.
Execution time mean : 162.281035 µs
Execution time std-deviation : 2.241839 µs
Execution time lower quantile : 159.142755 µs ( 2.5%)
Execution time upper quantile : 166.434460 µs (97.5%)
Overhead used : 5.183163 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 1 (1.6667 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
AlexMiller-keypaths
Evaluation count : 245220 in 60 samples of 4087 calls.
Execution time mean : 243.756275 µs
Execution time std-deviation : 2.802578 µs
Execution time lower quantile : 239.432062 µs ( 2.5%)
Execution time upper quantile : 248.041094 µs (97.5%)
Overhead used : 5.183163 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
nil
user=> (load-file "doc/notes/keypaths.clj")
#'user/miner49r-keypaths-all
user=> (def big3 (make-big-map 3 3))
#'user/big3
user=> (bench (def _ (doall (simple-specter-keypaths-with-leaves big3))))
Evaluation count : 2142000 in 60 samples of 35700 calls.
Execution time mean : 27.839481 µs
Execution time std-deviation : 345.943759 ns
Execution time lower quantile : 27.055491 µs ( 2.5%)
Execution time upper quantile : 28.510058 µs (97.5%)
Overhead used : 5.183163 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
nil
==============================================================
Times on MacBook Air with a 6^6 = 46656-path map details:
user=> (test-keypath-fns (make-big-map 6 6))
-------------------------------------------------------
simple-specter-keypaths
Evaluation count : 540 in 60 samples of 9 calls.
Execution time mean : 119.600975 ms
Execution time std-deviation : 1.141847 ms
Execution time lower quantile : 117.580309 ms ( 2.5%)
Execution time upper quantile : 121.711330 ms (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
fast-specter-keypaths
Evaluation count : 1800 in 60 samples of 30 calls.
Execution time mean : 34.435956 ms
Execution time std-deviation : 510.626189 µs
Execution time lower quantile : 33.861370 ms ( 2.5%)
Execution time upper quantile : 35.903883 ms (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
miner49r-keypaths
Evaluation count : 1620 in 60 samples of 27 calls.
Execution time mean : 37.897345 ms
Execution time std-deviation : 467.921592 µs
Execution time lower quantile : 37.156032 ms ( 2.5%)
Execution time upper quantile : 38.744788 ms (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
amalloy-keypaths
Evaluation count : 360 in 60 samples of 6 calls.
Execution time mean : 191.718783 ms
Execution time std-deviation : 2.275293 ms
Execution time lower quantile : 188.869284 ms ( 2.5%)
Execution time upper quantile : 198.178426 ms (97.5%)
Overhead used : 5.183163 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
-------------------------------------------------------
noisesmith-keypaths
Evaluation count : 360 in 60 samples of 6 calls.
Execution time mean : 180.448860 ms
Execution time std-deviation : 2.114388 ms
Execution time lower quantile : 176.528217 ms ( 2.5%)
Execution time upper quantile : 185.032269 ms (97.5%)
Overhead used : 5.183163 ns
Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
AWebb-keypaths
Evaluation count : 360 in 60 samples of 6 calls.
Execution time mean : 193.172784 ms
Execution time std-deviation : 2.222034 ms
Execution time lower quantile : 189.940117 ms ( 2.5%)
Execution time upper quantile : 197.549115 ms (97.5%)
Overhead used : 5.183163 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 1 (1.6667 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
AlexMiller-keypaths
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 839.266448 ms
Execution time std-deviation : 8.934431 ms
Execution time lower quantile : 826.642482 ms ( 2.5%)
Execution time upper quantile : 861.086162 ms (97.5%)
Overhead used : 5.183163 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 4 (6.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
user=> (bench (def _ (doall (simple-specter-keypaths-with-leaves big6))))
Evaluation count : 1740 in 60 samples of 29 calls.
Execution time mean : 35.945475 ms
Execution time std-deviation : 436.180237 µs
Execution time lower quantile : 35.245138 ms ( 2.5%)
Execution time upper quantile : 36.869227 ms (97.5%)
Overhead used : 5.183163 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
nil
================================================================
user=> (test-keypath-fns (make-big-map 7 7))
-------------------------------------------------------
simple-specter-keypaths
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 2.619101 sec
Execution time std-deviation : 38.621942 ms
Execution time lower quantile : 2.584118 sec ( 2.5%)
Execution time upper quantile : 2.723780 sec (97.5%)
Overhead used : 5.127383 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 2 (3.3333 %)
low-mild 2 (3.3333 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
fast-specter-keypaths
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 577.668066 ms
Execution time std-deviation : 12.702967 ms
Execution time lower quantile : 561.548389 ms ( 2.5%)
Execution time upper quantile : 604.271346 ms (97.5%)
Overhead used : 5.127383 ns
Found 5 outliers in 60 samples (8.3333 %)
low-severe 1 (1.6667 %)
low-mild 3 (5.0000 %)
high-mild 1 (1.6667 %)
Variance from outliers : 9.4615 % Variance is slightly inflated by outliers
-------------------------------------------------------
miner49r-keypaths
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 658.164156 ms
Execution time std-deviation : 10.899174 ms
Execution time lower quantile : 645.681955 ms ( 2.5%)
Execution time upper quantile : 688.105496 ms (97.5%)
Overhead used : 5.127383 ns
Found 4 outliers in 60 samples (6.6667 %)
low-severe 2 (3.3333 %)
low-mild 2 (3.3333 %)
Variance from outliers : 6.2446 % Variance is slightly inflated by outliers
-------------------------------------------------------
amalloy-keypaths
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 5.654859 sec
Execution time std-deviation : 41.188689 ms
Execution time lower quantile : 5.605222 sec ( 2.5%)
Execution time upper quantile : 5.730578 sec (97.5%)
Overhead used : 5.127383 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
-------------------------------------------------------
noisesmith-keypaths
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 4.568320 sec
Execution time std-deviation : 26.226468 ms
Execution time lower quantile : 4.517375 sec ( 2.5%)
Execution time upper quantile : 4.628493 sec (97.5%)
Overhead used : 5.127383 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
-------------------------------------------------------
AWebb-keypaths
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 3.158274 sec
Execution time std-deviation : 20.657650 ms
Execution time lower quantile : 3.129274 sec ( 2.5%)
Execution time upper quantile : 3.216785 sec (97.5%)
Overhead used : 5.127383 ns
Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
AlexMiller-keypaths
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 26.941646 sec
Execution time std-deviation : 131.701715 ms
Execution time lower quantile : 26.692784 sec ( 2.5%)
Execution time upper quantile : 27.173334 sec (97.5%)
Overhead used : 5.127383 ns
Found 2 outliers in 60 samples (3.3333 %)
low-severe 1 (1.6667 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
-------------------------------------------------------
simple-specter-keypaths-with-leaves
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 621.665484 ms
Execution time std-deviation : 9.823805 ms
Execution time lower quantile : 611.505654 ms ( 2.5%)
Execution time upper quantile : 647.784358 ms (97.5%)
Overhead used : 5.127383 ns
Found 5 outliers in 60 samples (8.3333 %)
low-severe 2 (3.3333 %)
low-mild 3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
nil
You can’t perform that action at this time.