Implement CollReduce/IReduce on sorted maps and sets
Description
Attached patch implements CollReduce in Clojure and IReduce in ClojureScript on AVLMap and AVLSet for a faster reduce with fewer intermediate allocations.
The with-init reduce implementation (e.g. (reduce conj [] coll)) is modelled on your existing reduce-kv implementation for maps and trivially transformed for sets.
The no-init reduce implementation (e.g. (reduce + coll)) is a bit funky. I use the internal function select to find the rank=0 node, extract its value to use as an init, then walk over the avl tree a second time to do the reduction. I avoid duplicating the first item in the reduction with an identical? check on the current node against the rank=0 node. Once I hit the rank=0 node again, I revert back to normal with-init reduction to drop the identical? check. Let me know if you see a better approach. However, I expect no-init reduction to be quite rare in practice, so I didn't try very hard to avoid walking part of the tree twice e.g. by keeping an internal node stack or something.
The transient versions of avl-map and avl-set are currently not reducible or seqable at all, so I didn't implement CollReduce/IReduce on them either.
Environment
None
Attachments
1
Activity
Show:
Michał Marczyk August 23, 2016 at 1:45 AM
Just released 0.0.14 with your patch in it – thanks again!
Also, just a heads-up – it also includes a bugfix to split-key, see DAVL-8.
Michał Marczyk August 21, 2016 at 9:58 PM
I've run some before/after Criterium benchmarks (see results for maps below). The benefit is pretty clear! Thanks again for the patch.
I've pushed the patch to master, plus a commit with some extra generative tests. I'll cut a release soon. I might have another look at the no-init case of reduce, but I don't think it's worth holding up the release over that.
—
Bechmark results:
Before patch:
After patch:
Michał Marczyk August 18, 2016 at 11:18 PM
Hey, thanks very much for this! Looks great at first glance. I'll have a closer look this weekend and probably cut a new release.
Attached patch implements CollReduce in Clojure and IReduce in ClojureScript on AVLMap and AVLSet for a faster
reduce
with fewer intermediate allocations.Rough benchmark in Clojure 1.5.1, Oracle Java 8, Ubuntu 16.04, Haswell i7
The with-init reduce implementation (e.g.
(reduce conj [] coll)
) is modelled on your existingreduce-kv
implementation for maps and trivially transformed for sets.The no-init reduce implementation (e.g.
(reduce + coll)
) is a bit funky. I use the internal functionselect
to find the rank=0 node, extract its value to use as an init, then walk over the avl tree a second time to do the reduction. I avoid duplicating the first item in the reduction with anidentical?
check on the current node against the rank=0 node. Once I hit the rank=0 node again, I revert back to normal with-init reduction to drop theidentical?
check. Let me know if you see a better approach. However, I expect no-init reduction to be quite rare in practice, so I didn't try very hard to avoid walking part of the tree twice e.g. by keeping an internal node stack or something.The transient versions of avl-map and avl-set are currently not reducible or seqable at all, so I didn't implement CollReduce/IReduce on them either.