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

Michael J. Steindorfer, Jurgen J. Vinju

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

14 Citaten (Scopus)

Samenvatting

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

Originele taal-2Engels
TitelOOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications
RedacteurenPatrick Eugster, Jonathan Aldrich
UitgeverijAssociation for Computing Machinery, Inc
Pagina's783-800
Aantal pagina's18
ISBN van elektronische versie9781450336895
DOI's
StatusGepubliceerd - 23 okt. 2015
Extern gepubliceerdJa
Evenement2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015) - Pittsburgh, Verenigde Staten van Amerika
Duur: 25 okt. 201530 okt. 2015

Publicatie series

NaamSIGPLAN Notices
UitgeverijACM
Nummer10
Volume50
ISSN van elektronische versie1558-1160

Congres

Congres2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015)
Verkorte titelOOPSLA2015
Land/RegioVerenigde Staten van Amerika
StadPittsburgh
Periode25/10/1530/10/15

Vingerafdruk

Duik in de onderzoeksthema's van 'Optimizing hash-array mapped tries for fast and lean immutable JVM collections'. Samen vormen ze een unieke vingerafdruk.

Citeer dit