Darwinian Data Structure Selection
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). We introduce artemis a multi-objective, cloud-based search-based optimisation framework that automatically finds optimal, tuned DDS modulo a test suite and changes an application to use that DDS. artemis achieves substantial performance improvements for every project in a set of 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) projects. The median improvement across all these best solutions is 4.8% for execution time, 10.1% for memory consumption and 5.1% for CPU usage.
These aggregate results understate artemis’s potential impact. Some of the benchmarks it improves are libraries or utility functions. Two examples are gson, a ubiquitous Java serialization framework, and xalan, the Apache project XML document transformation tool. artemis improves gson’s memory consumption by 16.5%, while also improving its execution time by 1% and CPU usage by 2.2%; artemis improves xalan’s memory consumption by 23.5%. Every client of these projects will benefit from performance improvements artemis achieves.