Explore reimplementing HashMap as CHAMP (Compressed Hash-Array Mapped Prefix-tree)

[pivovarit]

Related Epic: #2308

CompressedHAMP is designed to provide a smaller footprint and better cache locality than standard HAMT which features one array encoding both sub-node references and data values.

To improve things we can split the array into two dedicated ones: one for values, and one for sub-node references and use two 32-bit bitmaps.

Another idea to explore is if it would make sense to give up physical tree structure in favor of logical with one array backing the whole map. Would allow decreasing pointer chasing but would penalize modifications.

We should follow up and investigate if it makes sense to do the same move as Scala did in 2.13.

scala/collection-strawman#192
scala/scala@d5ae93e

References:

• https://blog.acolyer.org/2015/11/27/hamt/
• https://michael.steindorfer.name/publications/oopsla15.pdf

[danieldietrich]

We should consider to port it from usethesource/capsule.
Here the author gave an overview over data structures.

[pivovarit]

Great, I was aware of the library - wasn't aware of that thread. Definitely helpful!

btw, do you think it would make sense to do a push before 1.0.0? 🤔

[danieldietrich]

@pivovarit I plan to include it in 2.0.0, which is already in the make but in a very early alpha state. Collections aren't part of it, currently.

I also plan to get my hands on the essential data structures BMT, Red/Black Tree and CHAMP. I'm not sure if it makes sense that you invest time.

[wrandelshofer]

I made an experimental (and very dirty) port of CHAMP collections in a fork of vavr:
https://github.com/wrandelshofer/vavr#readme

I decided to implement linked collections with sequence numbers. This is much simpler to do, than keeping a linked list or a vector in sync with the CHAMP trie. However performance is a mixed bag. Most operations are quite fast, except accesses to the first/last entry of the collection - which are linear in time. Also, occasionally, we need to renumber the sequence numbers, which may cause unexpected slow-downs. Memory efficiency should be quite good though.

So, maybe my fork is just a demonstration of how not to do it. 😂

[wrandelshofer]

I made some progress now.

I have now implemented four different CHAMP-based collections:

• vavr.ChampMap
• vavr.SequencedChampMap
• vavr.ChampSet
• vavr.SequencedChampSet

Here is the current README file. It shows a performance comparison with vavr.HashMap, vavr.LinkedHashMap and scala.HashMap, scala.VectorMap, scala.TreeSeqMap.

https://github.com/wrandelshofer/vavr/blob/6569c67e3d5c3b4dae681fa762c714c8d074d7ab/README.md

The performance of the sequenced collections (the ones that preserve the insertion order) is now O(1) for all operations.
There are no performance cliffs anymore.

The code is in a very rough draft state. Let me know, what you think about it.

[danieldietrich]

Hi @wrandelshofer, the benchmarks look really impressive! From my point of view, you are welcome to create a PR that replaces the according Vavr collections (keeping their names).

[wrandelshofer]

Thank you. I am going to create a PR. 😀

[danieldietrich]

Awesome, I am really looking forward to this great improvement!

[wrandelshofer]

Please, do not worry. I am working hard on the PR. So far I have converted 2 collections. I have 2 more to go. 😅

The code I am working on is in this branch:
https://github.com/wrandelshofer/vavr/tree/champ-dev

(No need to look at it. It is in disarray.)

What are your plans with respect to Java 21?
It would be a shame, if I downgraded all my code to Java 8, and would then have to upgrade to 21 again. 🚧 🏗️ 👷‍♂️

[wrandelshofer]

I have now made a pull request. See
#2745