Jun 14, 2023

Understanding CHAMP Data Structures

Learn about CHAMP data structures, an improvement on the Hash Array Mapped Trie (HAMT) used in the original implementation of Scala's HashMap. Discover how CHAMP data structures improve the runtime performances of immutable collections.

COMPUTERS TECHNOLOGY ALGORITHM

Debasish (দেবাশিস্) Ghosh 🇮🇳

Programmer. Author: Functional and Reactive Domain Modeling (Manning 2016), DSLs In Action (Manning 2010). Father. Husband. Seinfeld fanboy. FP aficionado.

Member of Scala

Scala's immutable HashMap implementation is based on the CHAMP data structure, developed by Michael J. Steindorfer in his OOPSLA paper https://t.co/msGYGEUCER 🧵(1/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
CHAMP is an improvement on the Hash Array Mapped Trie (HAMT) developed by Phil Bagwell - HAMT was used in the original implementation of Scala's HashMap but was replaced by CHAMP around 2018 (I think) (2/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
CHAMP is also a compressed hash array mapped trie over the hash of objects inserted in the map. The difference is that it uses a clever technique for compression using bitmaps. It improves on the runtime performance of immutable structures by providing better cache locality (3/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
More details regarding CHAMP based data structures and how they improve on the runtime performances of immutable collections are available from the author's talk in JVM Language Summit 2016 (https://t.co/89Rs5ocRuT) (4/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
Recently I came across his excellent thesis which also gives a very detailed account of trie based immutable collections, persistent data structures and the CHAMP encoding https://t.co/2yMu3JxMfG (5/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
I have been doing some readings on cache oblivious data structures (it all started with Erik Demaine's 6.851 though :-)) and found these pointers as good learning materials for JVM based ones. (6/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023
For some other implementations, Michael A Bender et al's Cache Oblivious Streaming B-trees (https://t.co/rnJ1Yjc2ir) provides a cache oblivious lookahead array that's used in implementation of Map in Haskell standard library. (7/7)
— Debasish (দেবাশিস্) Ghosh 🇮🇳 (@debasishg) June 14, 2023