Standard

To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries. / Steindorfer, Michael J.; Vinju, Jurgen J.

PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery (ACM), 2018. p. 283-295.

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Harvard

Steindorfer, MJ & Vinju, JJ 2018, To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries. in PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery (ACM), pp. 283-295, 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, United States, 18/06/18. https://doi.org/10.1145/3192366.3192420

APA

Steindorfer, M. J., & Vinju, J. J. (2018). To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries. In PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 283-295). Association for Computing Machinery (ACM). https://doi.org/10.1145/3192366.3192420

Vancouver

Steindorfer MJ, Vinju JJ. To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries. In PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery (ACM). 2018. p. 283-295 https://doi.org/10.1145/3192366.3192420

Author

Steindorfer, Michael J. ; Vinju, Jurgen J. / To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries. PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery (ACM), 2018. pp. 283-295

BibTeX

@inproceedings{26b03e9c3241461fbbd3c638f03ef6a5,
title = "To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries",
abstract = "An immutable multi-map is a many-to-many map data structure with expected fast insert and lookup operations. This data structure is used for applications processing graphs or many-to-many relations as applied in compilers, runtimes of programming languages, or in static analysis of object-oriented systems. Collection data structures are assumed to carefully balance execution time of operations with memory consumption characteristics and need to scale gracefully from a few elements to multiple gigabytes at least. When processing larger in-memory data sets the overhead of the data structure encoding itself becomes a memory usage bottleneck, dominating the overall performance. In this paper we propose AXIOM, a novel hash-trie data structure that allows for a highly efficient and type-safe multi-map encoding by distinguishing inlined values of singleton sets from nested sets of multi-mappings. AXIOM strictly generalizes over previous hash-trie data structures by supporting the processing of fine-grained type-heterogeneous content on the implementation level (while API and language support for type-heterogeneity are not scope of this paper). We detail the design and optimizations of AXIOM and further compare it against state-of-the-art immutable maps and multi-maps in Java, Scala and Clojure. We isolate key differences using microbenchmarks and validate the resulting conclusions on a case study in static analysis. AXIOM reduces the key-value storage overhead by 1.87 x; with specializing and inlining across collection boundaries it improves by 5.1 x.",
keywords = "Data structures, Functional programming, Graph, Hashtable, JVM, Many-to-many relation, Multi-map, Optimization, Performance, Persistent data structures",
author = "Steindorfer, {Michael J.} and Vinju, {Jurgen J.}",
year = "2018",
month = jun,
day = "11",
doi = "10.1145/3192366.3192420",
language = "English",
pages = "283--295",
booktitle = "PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",
note = "39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018 ; Conference date: 18-06-2018 Through 22-06-2018",

}

RIS

TY - GEN

T1 - To-many or to-one? All-in-one! Efficient purely functional multi-maps with type-heterogeneous hash-tries

AU - Steindorfer, Michael J.

AU - Vinju, Jurgen J.

PY - 2018/6/11

Y1 - 2018/6/11

N2 - An immutable multi-map is a many-to-many map data structure with expected fast insert and lookup operations. This data structure is used for applications processing graphs or many-to-many relations as applied in compilers, runtimes of programming languages, or in static analysis of object-oriented systems. Collection data structures are assumed to carefully balance execution time of operations with memory consumption characteristics and need to scale gracefully from a few elements to multiple gigabytes at least. When processing larger in-memory data sets the overhead of the data structure encoding itself becomes a memory usage bottleneck, dominating the overall performance. In this paper we propose AXIOM, a novel hash-trie data structure that allows for a highly efficient and type-safe multi-map encoding by distinguishing inlined values of singleton sets from nested sets of multi-mappings. AXIOM strictly generalizes over previous hash-trie data structures by supporting the processing of fine-grained type-heterogeneous content on the implementation level (while API and language support for type-heterogeneity are not scope of this paper). We detail the design and optimizations of AXIOM and further compare it against state-of-the-art immutable maps and multi-maps in Java, Scala and Clojure. We isolate key differences using microbenchmarks and validate the resulting conclusions on a case study in static analysis. AXIOM reduces the key-value storage overhead by 1.87 x; with specializing and inlining across collection boundaries it improves by 5.1 x.

AB - An immutable multi-map is a many-to-many map data structure with expected fast insert and lookup operations. This data structure is used for applications processing graphs or many-to-many relations as applied in compilers, runtimes of programming languages, or in static analysis of object-oriented systems. Collection data structures are assumed to carefully balance execution time of operations with memory consumption characteristics and need to scale gracefully from a few elements to multiple gigabytes at least. When processing larger in-memory data sets the overhead of the data structure encoding itself becomes a memory usage bottleneck, dominating the overall performance. In this paper we propose AXIOM, a novel hash-trie data structure that allows for a highly efficient and type-safe multi-map encoding by distinguishing inlined values of singleton sets from nested sets of multi-mappings. AXIOM strictly generalizes over previous hash-trie data structures by supporting the processing of fine-grained type-heterogeneous content on the implementation level (while API and language support for type-heterogeneity are not scope of this paper). We detail the design and optimizations of AXIOM and further compare it against state-of-the-art immutable maps and multi-maps in Java, Scala and Clojure. We isolate key differences using microbenchmarks and validate the resulting conclusions on a case study in static analysis. AXIOM reduces the key-value storage overhead by 1.87 x; with specializing and inlining across collection boundaries it improves by 5.1 x.

KW - Data structures

KW - Functional programming

KW - Graph

KW - Hashtable

KW - JVM

KW - Many-to-many relation

KW - Multi-map

KW - Optimization

KW - Performance

KW - Persistent data structures

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

U2 - 10.1145/3192366.3192420

DO - 10.1145/3192366.3192420

M3 - Conference contribution

AN - SCOPUS:85049600876

SP - 283

EP - 295

BT - PLDI 2018 - Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation

PB - Association for Computing Machinery (ACM)

T2 - 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018

Y2 - 18 June 2018 through 22 June 2018

ER -

ID: 47964513