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

Michael J. Steindorfer; Jurgen J. Vinju

doi:10.1145/2814270.2814312

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 proceeding › Conference contribution › Academic › peer-review

14 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 language	English
Title of host publication	OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications
Editors	Patrick Eugster, Jonathan Aldrich
Publisher	Association for Computing Machinery, Inc
Pages	783-800
Number of pages	18
ISBN (Electronic)	9781450336895
DOIs	https://doi.org/10.1145/2814270.2814312
Publication status	Published - 23 Oct 2015
Externally published	Yes
Event	2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015) - Pittsburgh, United States Duration: 25 Oct 2015 → 30 Oct 2015

Publication series

Name	SIGPLAN Notices
Publisher	ACM
Number	10
Volume	50
ISSN (Electronic)	1558-1160

Conference

Conference	2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015)
Abbreviated title	OOPSLA2015
Country/Territory	United States
City	Pittsburgh
Period	25/10/15 → 30/10/15

Keywords

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

Access to Document

10.1145/2814270.2814312

Cite this

Steindorfer, M. J., & Vinju, J. J. (2015). Optimizing hash-array mapped tries for fast and lean immutable JVM collections. In P. Eugster, & J. Aldrich (Eds.), OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications (pp. 783-800). (SIGPLAN Notices; Vol. 50, No. 10). Association for Computing Machinery, Inc. https://doi.org/10.1145/2814270.2814312

Steindorfer, Michael J. ; Vinju, Jurgen J. / Optimizing hash-array mapped tries for fast and lean immutable JVM collections. OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications. editor / Patrick Eugster ; Jonathan Aldrich. Association for Computing Machinery, Inc, 2015. pp. 783-800 (SIGPLAN Notices; 10).

@inproceedings{61c2fa770b124882824127a22801656e,

title = "Optimizing hash-array mapped tries for fast and lean immutable JVM collections",

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

keywords = "Cache locality, Hash trie, Immutability, Java Virtual Machine, Performance, Persistent data structure",

author = "Steindorfer, {Michael J.} and Vinju, {Jurgen J.}",

year = "2015",

month = oct,

day = "23",

doi = "10.1145/2814270.2814312",

language = "English",

series = "SIGPLAN Notices",

publisher = "Association for Computing Machinery, Inc",

number = "10",

pages = "783--800",

editor = "Patrick Eugster and Jonathan Aldrich",

booktitle = "OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications",

address = "United States",

note = "2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015), OOPSLA2015 ; Conference date: 25-10-2015 Through 30-10-2015",

}

Steindorfer, MJ & Vinju, JJ 2015, Optimizing hash-array mapped tries for fast and lean immutable JVM collections. in P Eugster & J Aldrich (eds), OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications. SIGPLAN Notices, no. 10, vol. 50, Association for Computing Machinery, Inc, pp. 783-800, 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015), Pittsburgh, California, United States, 25/10/15. https://doi.org/10.1145/2814270.2814312

Optimizing hash-array mapped tries for fast and lean immutable JVM collections. / Steindorfer, Michael J.; Vinju, Jurgen J.
OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications. ed. / Patrick Eugster; Jonathan Aldrich. Association for Computing Machinery, Inc, 2015. p. 783-800 (SIGPLAN Notices; Vol. 50, No. 10).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Steindorfer, Michael J.

AU - Vinju, Jurgen J.

PY - 2015/10/23

Y1 - 2015/10/23

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

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

KW - Cache locality

KW - Hash trie

KW - Immutability

KW - Java Virtual Machine

KW - Performance

KW - Persistent data structure

UR - http://www.scopus.com/inward/record.url?scp=84958680472&partnerID=8YFLogxK

U2 - 10.1145/2814270.2814312

DO - 10.1145/2814270.2814312

M3 - Conference contribution

AN - SCOPUS:84958680472

T3 - SIGPLAN Notices

SP - 783

EP - 800

BT - OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications

A2 - Eugster, Patrick

A2 - Aldrich, Jonathan

PB - Association for Computing Machinery, Inc

T2 - 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, (OOPSLA 2015)

Y2 - 25 October 2015 through 30 October 2015

ER -

Steindorfer MJ, Vinju JJ. Optimizing hash-array mapped tries for fast and lean immutable JVM collections. In Eugster P, Aldrich J, editors, OOPSLA 2015 - Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming Systems, Languages, and Applications. Association for Computing Machinery, Inc. 2015. p. 783-800. (SIGPLAN Notices; 10). doi: 10.1145/2814270.2814312

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this