Darwinian Data Structure Selection
| Autor: | Basios, Michail, Li, Lingbo, Wu, Fan, Kanthan, Leslie, Barr, Earl |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC FSE 18) November 2018, Lake Buena Vista, FL, USA |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1145/3236024.3236043 |
| Popis: | 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 \emph{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 \emph{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. 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, Apache's XML transformation tool. ARTEMIS improves gson by $16.5$\%, $1\%$ and $2.2\%$ for memory, runtime, and CPU; ARTEMIS improves xalan's memory consumption by $23.5$\%. \emph{Every} client of these projects will benefit from these performance improvements. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|