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)

PDF - Author's Accepted Manuscript
Download (129kB) Preview
[img]
Preview
Official URL
http://doi.org/10.1145/2633301.2633303

Abstract

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: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Stefan Marr
Date Deposited: 26 Dec 2017 17:39 UTC
Last Modified: 23 Sep 2019 11:33 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/63830 (The current URI for this page, for reference purposes)
Marr, Stefan: https://orcid.org/0000-0001-9059-5180
  • Depositors only (login required):

Downloads

Downloads per month over past year