Just-in-Time Data Structures (FWOAL822)

While software applications have become larger and more complex with huge data sets, hardware has moved to multicore machines that are limited by memory access speed. Because of application phase behavior, each data structure can have different optimal data representations, or layouts, depending on its algorithms and data usage, at different program points. We propose Just-in-Time Data Structures (JIT DS), which will alleviate the need for the programmer to manually change representations or delineate phases; the underlying language virtual machine will monitor data structures and automatically decide when to transition to another data representation for optimal performance and memory efficiency. JIT DSs coordinate across the system stack, including communication from the application level and the software library level to the language virtual machine level, which will read hardware performance counters as part of its monitoring. The software engineer can insert declarative hints to guide transitions. Our JIT DS libraries will include annotations or predicates indicating behavior more conducive to a particular representation. The virtual machine will perform low-overhead profiling of data structure behavior to inform a data layout change. We will use JIT DSs to optimize application execution time and memory access latency, which is timely as there are more non-expert programmers, and as computer systems seek new holistic solutions to deal with hitting physical limits.

Keywords:Just-in-Time Data Structures

Disciplines:Systems theory, modelling and identification