Welcome! Please see the About page for a little more info on how this works.

–1 vote
in Collections by

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

43 Answers

0 votes
by

Comment made by: ztellman

Oh, I forgot to mention that I didn't make a PersistentUnrolledSet, since the existing wrappers can use the unrolled map implementation. However, it would be moderately faster and more memory efficient to have one, so let me know if it seems worthwhile.

0 votes
by

Comment made by: bronsa

Zach, the patch you added isn't in the correct format, they need to be created using git format-patch

0 votes
by

Comment made by: bronsa

Also, I'm not sure if this is on-scope with the ticket but those patches break with **print-dup**, as it expects a static create(x) method for each inner class.

I'd suggest adding a create(Map x) static method for the inner PersistentUnrolledMap classes and a create(ISeq x) one for the inner PersistentUnrolledVector classes

0 votes
by

Comment made by: alexmiller

Re making patches, see: http://dev.clojure.org/display/community/Developing Patches

0 votes
by

Comment made by: wagjo

I wonder what is the overhead of having meta and 2 hash fields in the class. Have you considered a version where the hash is computed on the fly and where you have two sets of collections, one with meta field and one without, using former when the actual metadata is attached to the collection?

0 votes
by

Comment made by: ztellman

I've attached a patch using the proper method. Somehow I missed the detailed explanation for how to do this, sorry. I know the guidelines say not to delete previous patches, but since the first one isn't useful I've deleted it to minimize confusion.

I did the print-dup friendly create methods, and then realized that once these are properly integrated, 'pr' will just emit these as vectors. I'm fairly sure the create methods aren't necessary, so I've commented them out, but I'm happy to add them back in if they're useful for some reason I can't see.

I haven't given a lot of thought to memory efficiency, but I think caching the hashes are worthwhile. I can see an argument for creating a "with-meta" version of each collection, but since that would double the size of an already enormous patch, I think that should probably wait.

0 votes
by

Comment made by: ztellman

I found a bug! Like PersistentArrayMap, I have a special code path for comparing keywords, but my generators for collection-check were previously using only integer keys. There was an off-by-one error in the transient map implementation (link: 1), which was not present for non-keyword lookups.

I've taken a close look for other gaps in my test coverage, and can't find any. I don't think this substantively changes the risk of this patch (an updated version of which has been uploaded as 'unrolled-collections-2.diff'), but obviously where there's one bug, there may be others.

(link: 1) https://github.com/ztellman/cambrian-collections/commit/eb7dfe6d12e6774512dbab22a148202052442c6d#diff-4bf78dbf5b453f84ed59795a3bffe5fcR559

0 votes
by

Comment made by: ztellman

As an additional data point, I swapped out the data structures in the Cheshire JSON library. On the "no keyword-fn decode" benchmark, the current implementation takes 6us, with the unrolled data structures takes 4us, and with no data structures (just lexing the JSON via Jackson) takes 2us. Other benchmarks had similar results. So at least in this scenario, it halves the overhead.

Benchmarks can be run by cloning https://github.com/dakrone/cheshire, unrolled collections can be tested by using the 'unrolled-collections' branch. The pure lexing benchmark can be reproduced by messing around with the cheshire.parse namespace a bit.

0 votes
by

Comment made by: ztellman

Is there no way to get this into 1.7? It's an awfully big win to push off for another year.

0 votes
by

Comment made by: alexmiller

Hey Zach, it's definitely considered important but we have decided to drop almost everything not fully done for 1.7. Timeframe for following release is unknown, but certainly expected to be significantly less than a year. :)

0 votes
by

Comment made by: jszakmeister

You are all free to determine the time table, but I thought I'd point out that Zach is not entirely off-base. Clojure 1.4.0 was released April 5th, 2012. Clojure 1.5.0 was released March 1st, 2013 with 1.6.0 showing up March 25th, 2014. So it appears that the current cadence is around a year.

0 votes
by

Comment made by: alexmiller

John, there is no point to comments like this. Let's please keep issue comments focused on the issue.

0 votes
by

Comment made by: ztellman

I did a small write-up on this patch which should help in the eventual code review: http://blog.factual.com/using-clojure-to-generate-java-to-reimplement-clojure

0 votes
by

Comment made by: ztellman

Per my conversation with Alex at the Conj, here's a patch that only contains the unrolled vectors, and uses the more efficient constructor for PersistentVector when spilling over.

0 votes
by

Comment made by: alexmiller

Zach, I created a new placeholder for the map work at http://dev.clojure.org/jira/browse/CLJ-1610.

...