As discussed on the mailing list (link: 1), this patch has two unrolled variants of vectors and maps, with special inner classes for each cardinality. Currently both grow to six elements before spilling over into the general versions of the data structures, which is based on rough testing but can be easily changed. At Rich's request, I haven't included any integration into the rest of the code, and there are top-level static create() methods for each.
The sole reason for this patch is performance, both in terms of creating data structures and performing operations on them. This can be seen as a more verbose version of the trick currently played with PersistentArrayMap spilling over into PersistentHashMap. Based on the benchmarks, which can be run by cloning cambrian-collections (link: 2) and running 'lein test :benchmark', this should supplant PersistentArrayMap. Performance is at least on par with PAM, and often much faster. Especially noteworthy is the creation time, which is 5x faster for maps of all sizes (lein test :only cambrian-collections.map-test/benchmark-construction), and on par for 3-vectors, but 20x faster for 5-vectors. There are similar benefits for hash and equality calculations, as well as calls to reduce().
This is a big patch (over 5k lines), and will be kind of a pain to review. My assumption of correctness is based on the use of collection-check, and the fact that the underlying approach is very simple. I'm happy to provide a high-level description of the approach taken, though, if that will help the review process.
I'm hoping to get this into 1.7, so please let me know if there's anything I can do to help accomplish that.
(link: 1) https://groups.google.com/forum/#!topic/clojure-dev/pDhYoELjrcs
(link: 2) https://github.com/ztellman/cambrian-collections
Patch: unrolled-vector-2.patch
Screener Notes: The approach is clear and understandable. Given the volume of generated code, I believe that best way to improve confidence in this code is to get people using it asap, and add collection-test (link: 3) to the Clojure test suite. I would also like to get the generator (link: 4) included in the Clojure repo. We don't need to necessarily automate running it, but would be nice to have it nearby if we want to tweak something later.
(link: 3) https://github.com/ztellman/collection-check/blob/master/src/collection_check.clj
(link: 4) https://github.com/ztellman/cambrian-collections/blob/master/generate/cambrian_collections/vector.clj
