UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Darwinian Data Structure Selection

Basios, M; Li, L; Wu, F; Kanthan, L; Barr, E; (2018) Darwinian Data Structure Selection. In: Leavens, Gary T., (ed.) Proceedings of ESEC/FSE '18 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM: FL, USA. Green open access

[img]
Preview
Text
Barr_fse18main-id170-p.pdf - ["content_typename_Accepted version" not defined]

Download (1MB) | Preview

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. 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%. Every client of these projects will benefit from these performance improvements.

Type: Proceedings paper
Title: Darwinian Data Structure Selection
Event: ESEC/FSE '18 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering
Location: Lake Buena Vista, FL, USA
Dates: 04 November 2018 - 10 November 2018
ISBN-13: 978-1-4503-5573-5
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/3236024.3236043
Publisher version: https://doi.org/10.1145/3236024.3236043
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Search-based Software Engineering, Genetic Improvement, Software Analysis and Optimisation, Data Structure Optimisation
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/10062922
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item