Mattias De Wael

Just-in-Time Data Structures

Mattias De Wael

Abstract

Today, software engineering practices focus on finding the single ``right'' data representation (i.e., data structure) for a program. The ``right'' data representation, however, might not exist: relying on a single representation of the data for the lifetime of the program can be suboptimal in terms of performance. We explore the idea of developing data structures for which changing the data representation is an intrinsic property. To this end we introduce Just-in-Time Data Structures, which enable representation changes at runtime, based on declarative input from a performance expert programmer. Just-in-Time Data Structures are an attempt to shift the focus from finding the ``right'' data structure to finding the ``right'' sequence of data representations. We present an extension to the Java language to develop Just-in-Time Data Structures and we show two example programs that benefit from changing the representation at runtime.