Safe and flexible adaptation via alternate data structure representations

Amlan Kusum, Iulian Neamtiu, Rajiv Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


The choice of data structures is crucial for achieving high performance. For applications that are long-running and/or operate on large data sets, the best choice for main data structures can change multiple times over the course of a single execution. For example, in a graph-processing application where the graph evolves over time, the best data structure for representing the graph may change as the program executes. Similarly, in a database or a key-value store application, with changes in relative frequencies of different types of queries over time, the most efficient data structure changes as well. We introduce an approach that allows applications to adapt to current conditions (input characteristics, operations on data, state) by switching their data structures on-the-fly with little overhead and without the developer worrying about safety or specifying adaptation points (this is handled by our compiler infrastructure). We use our approach on different classes of problems that are computeand memory-intensive: graph algorithms, database indexing, and two real-world applications, the Memcached object cache and the Space Tyrant online game server. Our results show that off-the-shelf applications can be transformed into adaptive applications with modest programmer effort; that the adaptive versions outperform the original, fixed-representation versions; and that adaptation can be performed on-the-fly safely and with very little runtime overhead.

Original languageEnglish (US)
Title of host publicationProceedings of CC 2016
Subtitle of host publicationThe 25th International Conference on Compiler Construction
PublisherAssociation for Computing Machinery, Inc
Number of pages11
ISBN (Electronic)9781450342414
StatePublished - Mar 17 2016
Event25th International Conference on Compiler Construction, CC 2016 - Barcelona, Spain
Duration: Mar 17 2016Mar 18 2016

Publication series

NameProceedings of CC 2016: The 25th International Conference on Compiler Construction


Other25th International Conference on Compiler Construction, CC 2016

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Signal Processing
  • Software


  • Adaptation
  • Input characteristics
  • Runtime data structure selection
  • Space-time trade-off


Dive into the research topics of 'Safe and flexible adaptation via alternate data structure representations'. Together they form a unique fingerprint.

Cite this