Hi,
I've been toying with the ClojureScript ports of the currently
available persistent data structures to see what it would take to port
them back to Clojure. Clearly it makes the most sense to start with
the sorted collections, since nothing else in Clojure depends on their
presence, so they are the natural candidate for the first data
structure to be replaced with a pure-Clojure implementation in an
actual release some day.
Here's a version of Clojure's sorted map and sorted set, using code
mostly pulled from the ClojureScript ports, with various adjustments /
bug fixes (corresponding patches for ClojureScript forthcoming):
https://github.com/michalmarczyk/sorted.clj
The aforementioned adjustments include using clojure.lang.MapEntry
instances where map entries are needed (the nodes of the tree do not
implement IMapEntry and are never handed to clients who request map
entries) and making the order in which reduce-kv sees the key/value
pairs consistent with the ordering of the collection.
As for performance -- that definitely needs to be measured more
carefully, but for now see some basic Criterium benchmarks below
(using Criterium 0.3.1).
Is there any interest in this becoming a part of contrib? It would be
great to test and tune this code "under the CA", as it were, so that
it can be merged back into the core library whenever it's mature
enough.
Cheers,
Michał
;;; (require '[sorted.core :as s] '[criterium.core :as c])
user> (let [m1 (apply sorted-map (interleave (range 1024) (range 1024)))
m2 (apply s/sorted-map (interleave (range 1024) (range 1024)))]
(c/quick-bench (get m1 128))
(c/quick-bench (get m2 128)))
WARNING: Final GC required 33.505380650613795 % of runtime
Evaluation count : 2943666 in 6 samples of 490611 calls.
Execution time mean : 207.229949 ns
Execution time std-deviation : 4.776218 ns
Execution time lower quantile : 201.418831 ns ( 2.5%)
Execution time upper quantile : 212.158227 ns (97.5%)
WARNING: Final GC required 31.98787196145191 % of runtime
Evaluation count : 2423634 in 6 samples of 403939 calls.
Execution time mean : 248.822429 ns
Execution time std-deviation : 5.108509 ns
Execution time lower quantile : 243.991806 ns ( 2.5%)
Execution time upper quantile : 255.985967 ns (97.5%)
nil
user> (let [m1 (apply sorted-map (interleave (range 1024) (range 1024)))
m2 (apply s/sorted-map (interleave (range 1024) (range 1024)))]
(c/quick-bench (assoc m1 128 :foo))
(c/quick-bench (assoc m2 128 :foo)))
WARNING: Final GC required 32.16487016906748 % of runtime
Evaluation count : 998310 in 6 samples of 166385 calls.
Execution time mean : 599.396595 ns
Execution time std-deviation : 32.981185 ns
Execution time lower quantile : 575.236121 ns ( 2.5%)
Execution time upper quantile : 642.289762 ns (97.5%)
WARNING: Final GC required 31.884187557043393 % of runtime
Evaluation count : 897798 in 6 samples of 149633 calls.
Execution time mean : 687.851624 ns
Execution time std-deviation : 40.570811 ns
Execution time lower quantile : 664.063322 ns ( 2.5%)
Execution time upper quantile : 744.437622 ns (97.5%)
nil