Darwinian data structure selection

Michail Basios, Lingbo Li, Fan Wu, Leslie Kanthan, Earl T. Barr

Abstract

Data structure selection and tuning is laborious but can vastly improve an application’s performance and memory footprint. Some data structures share a common interface and enjoy multiple implementations. We call them Darwinian Data Structures (DDS), since we can subject their implementations to survival of the fittest. We introduce ARTEMIS a multi-objective, cloud-based search-based optimisation framework that automatically finds optimal, tuned DDS modulo a test suite, then changes an application to use that DDS. ARTEMIS achieves substantial performance improvements for every project in 5 Java projects from DaCapo benchmark, 8 popular projects and 30 uniformly sampled projects from GitHub. For execution time, CPU usage, and memory consumption, ARTEMIS finds at least one solution that improves all measures for 86% (37/43) of the projects. The median improvement across the best solutions is 4.8%, 10.1%, 5.1% for runtime, memory and CPU usage.

BibTeX

@inproceedings{Basios-al:FSE18,
  author    = {Michail Basios and
               Lingbo Li and
               Fan Wu and
               Leslie Kanthan and
               Earl T. Barr},
  title     = {Darwinian data structure selection},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {118--128},
  publisher = {{ACM}},
  year      = {2018},
}

Darwinian data structure selection

Abstract

Related papers