Collection Skeletons - Declarative Abstractions for Data Collections

Björn Franke, Zhibo Li, Magnus Morton, Michel Steuwer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Modern programming languages provide programmers with rich abstractions for data collections as part of their standard libraries, e.g. Containers in the C++ STL, the Java Collections Framework, or the Scala Collections API. Typically, these collections frameworks are organised as hierarchies that provide programmers with common abstract data types (ADTs) like lists, queues, and stacks. While convenient, this approach introduces problems which ultimately affect application performance due to users over-specifying collection data types limiting implementation flexibility. In this paper, we develop Collection Skeletons which provide a novel, declarative approach to data collections. Using our framework, programmers explicitly select properties for their collections, thereby truly decoupling specification from implementation. By making collection properties explicit immediate benefits materialise in form of reduced risk of over-specification and increased implementation flexibility. We have prototyped our declarative abstractions for collections as a C++ library, and demonstrate that benchmark applications rewritten to use Collection Skeletons incur little or no overhead. In fact, for several benchmarks, we observe performance speedups (on average between 2.57 to 2.93, and up to 16.37) and also enhanced performance portability across three different hardware platforms.
Original languageEnglish
Title of host publicationProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2022)
EditorsBernd Fischer, Lola Burgueño, Walter Cazzola
PublisherAssociation for Computing Machinery (ACM)
Number of pages13
ISBN (Electronic)978-1-4503-9919-7
Publication statusPublished - 1 Dec 2022
EventThe 15th ACM SIGPLAN International Conference on Software Language Engineering, 2022 - Auckland, New Zealand
Duration: 5 Dec 202210 Dec 2022
Conference number: 15


ConferenceThe 15th ACM SIGPLAN International Conference on Software Language Engineering, 2022
Abbreviated titleSLE 2022
Country/TerritoryNew Zealand
Internet address

Keywords / Materials (for Non-textual outputs)

  • Containers
  • collections
  • data structures
  • properties


Dive into the research topics of 'Collection Skeletons - Declarative Abstractions for Data Collections'. Together they form a unique fingerprint.

Cite this