Skip to main content

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

De Wael, Mattias and Marr, Stefan and De Meuter, Wolfgang (2014) Data Interface + Algorithms = Efficient Programs: Separating Logic from Representation to Improve Performance. In: Proceedings of the 9th International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems PLE. ECOOP European Conference on Object-Oriented Programming . ACM, New York, USA. ISBN 978-1-4503-2914-9. (doi:10.1145/2633301.2633303) (KAR id:63830)

PDF Author's Accepted Manuscript
Language: English
Download (131kB)
[thumbnail of paper.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
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: Book section
DOI/Identification number: 10.1145/2633301.2633303
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Stefan Marr
Date Deposited: 26 Dec 2017 17:39 UTC
Last Modified: 09 Dec 2022 04:34 UTC
Resource URI: (The current URI for this page, for reference purposes)
Marr, Stefan:
  • Depositors only (login required):


Downloads per month over past year