Optimising Darwinian Data Structures on Google Guava

Michail Basios, Lingbo Li, Fan Wu, Leslie Kanthan, Earl T. BarrSSBSE 2017 · DOI

TL;DR

This paper introduces ARTEMIS, an automated framework that optimizes data structure selection and tuning in large Java codebases. By employing a multi-objective genetic algorithm, ARTEMIS can significantly improve program performance (execution time, memory usage, CPU usage) without sacrificing correctness, offering a practical solution to a tedious and often overlooked optimization problem.

What Problem Does This Paper Address?

Software developers often rely on default data structures provided by libraries, neglecting the potential for significant performance gains through careful selection and tuning of alternative implementations and parameters. This is due to the time-consuming, brittle, and often unclear benefits of manual optimization, especially in large codebases. The paper tackles this by addressing the "Darwinian Data Structure Selection (DS2)" problem: finding the optimal combination of data structures and their arguments to optimize program runtime performance.

Methods

The core of the paper is the ARTEMIS framework, a language-agnostic, cloud-based optimization system. ARTEMIS works in three main stages:

  1. Darwinian Data Structures Store Generator (DDSSG): This component analyzes library source code or documentation to build a hierarchy of "Darwinian" data structures – those with multiple implementations and tunable parameters. It identifies replaceable classes and their relationships.
  2. Extractor: This component takes the user's program source code, identifies potential Darwinian data structure locations, and generates a templated version of the code where these structures are replaced with generic identifiers. It also uses a preprocessing step to identify the most "costly" parts of the code, focusing optimization efforts.
  3. Optimizer: This is the heart of the system, employing a multi-objective Genetic Algorithm (specifically NSGA-II) to search for optimal combinations of data structure implementations and tuning parameters. It aims to simultaneously improve execution time, memory usage, and CPU usage while ensuring the program passes a given test suite. The optimization parameters are represented as an array of integers, and fitness functions are designed to capture the performance metrics.

Datasets

The paper evaluates ARTEMIS on the Google Guava library. Guava is described as an open-source set of common Java libraries, consisting of 252,688 Lines of Code and tested by 1,674,425 test cases with 61.7% branch coverage. No new benchmarks were introduced; Guava served as the real-world system for evaluation.

Key Insights and Ideas

  • Automating a Tedious Task: The primary insight is that a significant portion of performance optimization, specifically data structure selection and tuning, can be effectively automated. This frees up developers from a time-consuming and error-prone manual process.
  • Multi-Objective Optimization is Crucial: Recognizing that performance improvements often involve trade-offs (e.g., speed vs. memory), the paper highlights the necessity of a multi-objective approach. ARTEMIS simultaneously optimizes for execution time, memory usage, and CPU usage, providing a more holistic improvement.
  • "Darwinian" Data Structures as a Key Concept: The paper formalizes the idea of "Darwinian" data structures – those that are replaceable and tunable – as the prime targets for optimization. This concept provides a structured way to identify optimization opportunities.
  • Cost-Effectiveness: The study demonstrates that the computational cost of using ARTEMIS is negligible compared to the potential performance gains and the cost of manual optimization by human engineers.

Key Results

ARTEMIS achieved notable improvements on the Guava library:

  • Overall Improvement: 27.45% of the final solutions provided improvements across all measures (execution time, CPU usage, and memory consumption) without sacrificing any objective.
  • Individual Objective Improvements:
    • Memory consumption improved by up to 13%.
  • Execution time improved by up to 9%.
  • CPU usage improved by up to 4%.
  • Dominating Solutions: 14 out of 51 final solutions strictly dominated the original program, meaning they outperformed it in all measured aspects.
  • Number of Optimized Structures: ARTEMIS identified and optimized an average of 3 Darwinian data structures per solution, with a median of 3.
  • Computational Cost: The cost of optimizing Guava was estimated to be less than £7.85 using cloud computing resources.

Limitations and Future Work

  • Language Agnosticism: While ARTEMIS is designed to be language-agnostic, the current implementation and evaluation are focused on Java. Future work could involve adapting and validating it for other programming languages.
  • Scope of Optimization: The paper mentions that ARTEMIS was applied only to the "most used code" in Guava, identified by a preprocessor. Future work could explore optimizing the entire codebase, though this might increase computational cost.
  • Test Suite Dependency: The effectiveness of ARTEMIS relies on a comprehensive test suite to ensure that optimizations do not break program correctness. The quality and coverage of the test suite are critical.
  • Exploration of Other Objectives: The current optimization focuses on execution time, memory, and CPU usage. Future work could explore optimizing for other objectives like energy consumption or latency.

Summary updated

BibTeX
@inproceedings{basios2017optimising,
  author = {Michail Basios and Lingbo Li and Fan Wu and Leslie Kanthan and Earl T. Barr},
  title = {{Optimising Darwinian Data Structures on Google Guava}},
  booktitle = {SSBSE},
  year = {2017},
  doi = {10.1007/978-3-319-66299-2\_14},
}
Figure