Backport insertion-ordered immutable map to capsule

[msteindorfer]

I previously already implemented an insertion-ordered immutable map for another open-source project. The goal is to backport this implementation to capsule and integrate them into capsule's API.

[wrandelshofer]

Hi,

I made an experimental implementation of an insertion-ordered immutable map based on the CHAMP trie in Capsule. It stores elements with sequence numbers in the trie. Its iterators sort the elements with a bucket sort. It uses a large number of buckets (between N and N*4 buckets), so that the sorting can be performed in linear time.

I have benchmarked it against VectorMap in Scala. The performance is better, except for retrieval of the first/last element, which takes linear time in my implementation.

The code and benchmark results are here. https://github.com/wrandelshofer/vavr#readme

[jurgenvinju]

this is interesting! What kind of applications do you have in mind typically? Just to get an idea of what we could build on top of this.

[wrandelshofer]

Well, mostly the following kinds of applications:

• Real-time monitoring and control systems. The business objects can have multi-valued properties. The property values must be immutable. We can have hundreds of thousands of them per server instance. Currently we use unmodifiable collections and defensive copying. But this is error-prone, and we can not afford errors in this kind of applications. - We need immutable collections that can not throw UnmodifiableOperationException.

• Data visualisation and modeling tools. The model objects can have multi-valued properties. The property values must be immutable. We can have millions of them, and we must provide an undo/redo history for each of them. - We need immutable collections that we can safely share with many model objects.

• Graph algorithms. Some of the algorithms work with immutable sets and sequences. Our graphs are directed and may contain cycles. They can have hundreds of thousands of vertices. - For this, we need immutable collections that are performant, and are friendly to the garbage collector. (I am somewhat pessimistic about the garbage collector friendliness of CHAMP tries. Maybe I need to implement something based on the ByteBuffer or the upcoming Java Foreign Memory API instead).

[jurgenvinju]

👍 yes that sounds good. @msteindorfer do you have time to review @wrandelshofer 's branch? I think we might be able to use his contributions for Rascal as well. What do you think?