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.

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 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.

Completed

Details

Assignee

Reporter

Patch

Priority

Created August 17, 2016 at 7:29 PM
Updated August 23, 2016 at 7:20 PM
Resolved August 23, 2016 at 7:20 PM