Write a Blog >>
Onward! 2018
Wed 7 - Thu 8 November 2018 Boston, Massachusetts, United States
co-located with SPLASH 2018
Thu 8 Nov 2018 10:30 - 11:00 at The Loft - Data Structures Chair(s): Stefan Marr

Collections are commonly implemented as libraries by data structure experts, and are relied on heavily by application developers. The expert’s task is to implement a wide range of collections, and the application developer’s task is to pick an appropriate collection for each usage scenario. The design space for collections is huge, as data structures in practice implement not only their semantics, but also several performance-related concerns like memory layout, synchronisation, and (im)mutability.

This paper presents C♭, pronounced “C-flat”, a novel way to implement collections that lets experts implement the semantics of a collection data structure, in a way that is decoupled from its data representation. This simplifies collection implementation, and allows a collection’s performance to be tuned, for example, moving from a dense to a sparse representation, without changing its abstract specification.

We describe C♭, both abstractly and in terms of a specific prototype implementation in Java. We use our prototype implementation to show that C♭ is expressive enough to implement common collections, that the code is straightforward, and that the performance of C♭ collections is close to Java’s standard collections for most operations, and much higher for some.

Thu 8 Nov

onward-2018-papers
10:30 - 12:00: Onward! Papers - Data Structures at The Loft
Chair(s): Stefan MarrUniversity of Kent
onward-2018-papers10:30 - 11:00
Talk
Stephan BrandauerUppsala University, Elias CastegrenUppsala University, Tobias WrigstadUppsala University
Pre-print
onward-2018-papers11:00 - 11:30
Talk
Akio OkaTokyo Institute of Technology, Hidehiko MasuharaTokyo Institute of Technology, Tomoyuki AotaniTokyo Institute of Technology