Skip to main content

Data Interface + Algorithms = Efficient Programs: Separating Logic from Representation to Improve Performance

De Wael, Mattias, Marr, Stefan, De Meuter, Wolfgang (2014) Data Interface + Algorithms = Efficient Programs: Separating Logic from Representation to Improve Performance. In: Proceedings of the 9th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems. (doi:10.1145/2633301.2633303)

PDF - Author's Accepted Manuscript
Download (129kB) Preview
Official URL


Finding the right algorithm–data structure combination is easy, but finding the right data structure for a set of algorithms is much less trivial. Moreover, using the same data representation throughout the whole program might be sub-optimal. Depending on several factors, often only known at runtime, some programs benefit from changing the data representation during execution. In this position paper we introduce the idea of Just-In-Time data structures, a combination of a data interface and a set of concrete data representations with different performance characteristics. These Just-In- Time data structures can dynamically swap their internal data representation when the cost of swapping is payed back many times in the remainder of the computation. To make Just-In-Time data structures work, research is needed at three fronts: 1. We need to better understand the synergy between different data representations and algorithms; 2. We need a structured approach to handle the transitions between data representations; 3. We need descriptive programming constructs to express which representation fits a program fragment best. Combined, this research will result in a structured programming approach where separating data interface from data representation, not only improves understandability and maintainability, but also improves performance through automated transitions of data representation.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1145/2633301.2633303
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Stefan Marr
Date Deposited: 26 Dec 2017 17:39 UTC
Last Modified: 29 May 2019 19:39 UTC
Resource URI: (The current URI for this page, for reference purposes)
Marr, Stefan:
  • Depositors only (login required):


Downloads per month over past year