Wed 20 Jun 2018 17:00 - 17:25 at Grand Ballroom CD - Floats and Maps Chair(s): Hans-J. Boehm

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.87x; with specializing and inlining across collection boundaries it improves by 5.1x.

Wed 20 Jun

Displayed time zone: Eastern Time (US & Canada) change

16:10 - 17:25
Floats and MapsPLDI Research Papers at Grand Ballroom CD
Chair(s): Hans-J. Boehm Google
16:10
25m
Talk
Finding Root Causes of Floating Point Error
PLDI Research Papers
Alex Sanchez-Stern University of California, San Diego, Pavel Panchekha University of Washington, Sorin Lerner University of California, San Diego, Zachary Tatlock University of Washington, Seattle
Media Attached
16:35
25m
Talk
Ryƫ: Fast Float-to-String Conversion
PLDI Research Papers
Ulf Adams Google, Germany
Media Attached
17:00
25m
Talk
To-Many or To-One? All-in-One! Efficient Purely Functional Multi-maps with Type-Heterogeneous Hash-Tries
PLDI Research Papers
Michael J. Steindorfer Delft University of Technology, Jurgen Vinju Centrum Wiskunde & Informatica / Technische Universiteit Eindhoven / SWAT.engineering BV
Media Attached