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 Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems. (doi:https://doi.org/10.1145/2633301.2633303) (Full text available)

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: Conference or workshop item (Paper)
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: 03 Jan 2018 12:09 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