Department of Computer Science, Vrije Universiteit Brussel
Software Languages Lab (SOFT)
Instructor: Jennifer B. Sartor
Instructor email: jsartor@soft.vub.ac.be
Today's software is so large and complex, it's hard for a developer to choose one particular data structure for the lifetime of the application, and often one data structure is not optimal in terms of performance. Because applications have different phases -- building up data structures and populating them with data versus searching the data structure and accessing elements, for example -- we believe that the programmer should be relieved of the burden of choosing just one data representation. The building up phase could benefit from having data laid out in a linked list data structure, whereas accessing elements sequentially from a list performs better if the data is represented by an array. We propose a concept called Just-in-Time Data Structures (JIT DS) that lets the programmer choose one universal list data structure, while the runtime dynamically changes the underlying representation to give the best performance in terms of memory accesses and execution time.
A PhD student has introduced JIT DS and built a language called JITds to implement them. A JIT data structure class combines a number of other classes - the potential data representations - and holds the pointer to the current (only one) representation at a particular point in time. In fact the JIT DS class is a sub-class of all of its different representations, as any of the representations' methods can be called on a JIT DS class instance. The JIT DS class also defines transition functions, which define how to transition from one representation to another, and swap functions, which define when to transition to another data representation.
To get started with this master's thesis, you should read background research on JIT data structures, namely Mattias De Wael's ONWARD paper and his dissertation.