Optimizing hash-array mapped tries for fast and lean immutable JVM collections

Michael J. Steindorfer, Jurgen J. Vinju

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Abstract

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).

Original languageEnglish
Title of host publicationOOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications
EditorsPatrick Eugster, Jonathan Aldrich
PublisherAssociation for Computing Machinery, Inc
Pages783-800
Number of pages18
ISBN (Electronic)9781450336895
DOIs
Publication statusPublished - 23 Oct 2015
Externally publishedYes
Event2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015) - Pittsburgh, United States
Duration: 25 Oct 201530 Oct 2015

Publication series

NameSIGPLAN Notices
PublisherACM
Number10
Volume50
ISSN (Electronic)1558-1160

Conference

Conference2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015)
Abbreviated titleOOPSLA2015
CountryUnited States
CityPittsburgh
Period25/10/1530/10/15

Keywords

  • Cache locality
  • Hash trie
  • Immutability
  • Java Virtual Machine
  • Performance
  • Persistent data structure

Fingerprint Dive into the research topics of 'Optimizing hash-array mapped tries for fast and lean immutable JVM collections'. Together they form a unique fingerprint.

Cite this