Explore CHAMP for immutable Collections

#1

As per this paper here https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf, there is a newer method for implementing immutable data structures (which are typically implemented using Trees).

The paper goes into detail showing how their implementations of collections (such as Vector) is much faster than implementations used in languages like Scala and Clojure. This is done by using compressed arrays, which have much better cache locality/memory representation compared to trees (Java doesn’t give you an real control over how memory is laid out so you can avoid cache misses, Array is one of the few JVM structures where you can have control over cache locality)

Would it be useful to spend an effort to implement said techniques in the Scala collections rewrite of 2.13.x, considering they would provide a significant speed boost to immutable collections such as Vector, which is frequently used as a default

12 Likes
#2

Yes, it’s the right time to experiment with new collection implementations :slight_smile:

Pull requests would be highly appreciated! Do you plan to work on that?

#3

My time is quite busy right now so I wouldn’t rely on me (especially if there is a deadline for the new collections). I was just putting it up here since I thought it would be really useful and now is the right time to do it.

I would have more time to look at it in a few weeks depending on how things go

#4

For reference, here are some Java implementations from the author: https://github.com/usethesource/capsule

I think this could definitely improve the immutable HashSet and HashMap implementations.