• Optimizing Hash-array Mapped T...

Result: Optimizing Hash-array Mapped Tries for Fast and Lean Immutable JVM Collections

Title:
Optimizing Hash-array Mapped Tries for Fast and Lean Immutable JVM Collections
Authors:
Steindorfer, Michael, Vinju, Jurgen
Contributors:
Centrum Wiskunde & Informatica (CWI), Analysis and Transformation based on rEliAble tool coMpositionS (ATEAMS), Centre Inria de l'Université de Lille, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centrum Wiskunde & Informatica (CWI)
Source:
Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming. :783-800
Publisher Information:
CCSD; ACM, 2015.
Publication Year:
2015
Collection:
collection:INRIA
collection:INRIA-LILLE
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
Subject Terms:
Hash trie, Java Virtual Machine, cache locality, immutability, performance, persistent data structure, [INFO.INFO-SE]Computer Science [cs], Software Engineering [cs.SE]
Subject Geographic:
New York, United States
Original Identifier:
HAL: hal-01261487
Document Type:
Conference conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1145/2814270.2814312
DOI:
10.1145/2814270.2814312
Availability:
https://inria.hal.science/hal-01261487
Accession Number:
edshal.hal.01261487v1
Database:
HAL

Further Information

The data structures under-pinning collection API (e.g. lists, sets, maps) in the standard libraries of programming languages are used intensively in many applications. The standard libraries of recent Java Virtual Machine languages, such as Clojure or Scala, contain scalable and well-performing immutable collection data structures that are implemented as Hash-Array Mapped Tries (HAMTs). HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. This particularly prohibits their application in programs which process larger data sets. In this paper, we propose changes to the HAMT design that increase the overall performance of immutable sets and maps. The resulting general purpose design increases cache locality and features a canonical representation. It outperforms Scala’s and Clojure’s data structure implementations in terms of memory footprint and runtime efficiency of iteration (1.3–6.7 x) and equality checking (3–25.4 x).