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