Faster Lists

I have posted a 1.8-SNAPSHOT release to maven central containing a brand new JImmutableList implementation based on 32-way trees optimized for fast lookup at any index and allowing insertion and deletion only at the head/tail of the list. Starting with 1.8 this implementation will replace the JImmutableArray based JImmutableLists of previous releases.

The new trees are simpler and consume less memory than the old sparse array based list. The old implementation had the advantage of reusing the sparse array classes already present in the library. Unfortunately they also had the potential limitation that if you performed more than 2.4ish billion inserts and deletes on a single list it could exhaust the range of possible indexes for the underlying array. I warned about that in the comments and it was extremely unlikely to happen in real programs (who does 2.4 billion updates to an immutable list???) but it still bugged me to have that sort of limitation built in.

The new 32-way trees (not tries but similar in some respects to the tries used for hashing) avoid that limitation. Unlike the sparse arrays they are specifically optimized for the JImmutableList mode of operation. These optimizations pay off in my benchmarks with about a 35% speed improvement over the old implementation. I haven't calculated the memory savings over a sparse array but it's probably substantial since these trees don't need to maintain a node for every value in the tree.

I am running my random loop tests to see if they smoke out any bugs before making a new 1.8 release. In the meantime you can access the 1.8-SNAPSHOT release through maven if you'd like to try it out. The master branch in git also has the new code if you want to build from source.