An Entry for 16th Annual (2019) "Humies" Awards For Human-Competitive Results – Produced by Genetic and Evolutionary Computation ========================================================================================================================================== 1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; "Darwinian Data Structure Selection" ------------------------------------------------------------------------------- 2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Michail Basios Department of Computer Science University College London Gower Street WC1E 6BT, United Kingdom e-mail: michail.basios@cs.ucl.ac.uk tel: +44 7449 657520 Lingbo Li Department of Computer Science University College London Gower Street WC1E 6BT, United Kingdom e-mail: lingbo.li@cs.ucl.ac.uk tel: +44 7427 157246 Fan Wu Department of Computer Science University College London Gower Street WC1E 6BT, United Kingdom e-mail: fan.wu@cs.ucl.ac.uk tel: +44 7807 630192 Leslie Kanthan Department of Computer Science University College London Gower Street WC1E 6BT, United Kingdom e-mail: l.kanthan@cs.ucl.ac.uk tel: +44 7866 300200 Earl T. Barr Department of Computer Science University College London Gower Street WC1E 6BT, United Kingdom e-mail: e.barr@cs.ucl.ac.uk tel: 44 (0)20 7679 3570 ------------------------------------------------------------------------------- 3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Michail Basios ------------------------------------------------------------------------------- 4. the abstract of the paper(s); 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. ------------------------------------------------------------------------------- 5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; (A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (G) The result solves a problem of indisputable difficulty in its field. (H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs). ------------------------------------------------------------------------------- 6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); (A) Artemis is patentable: it realises a new, language-agnostic way of optimising existing software by exposing data structures and its parameters, which it then tunes using multi-objective search. Our FSE publication is the first time this optimization technique was proposed, implemented, validated, and published to users as a service. You can try Artemis out and download its code and evaluation artifacts at http://darwinianoptimiser.com. Huawei is extremely interested in Artemis and offered grant to CREST UCL to fund further research. Buoyed by their interest, we are working with our university’s technology transfer division about spinning out a startup based on Artemis. (E) Humans struggle to optimise code; it is a laborious task with many pitfalls — attempts to optimise can even worsen performance! Data structure selection and optimisation is the optimisation problem of selecting among data structures and initialising them. Humans have invented a succession of increasingly better human-created solutions in the form of new data structures, new implementations of existing data structures, and new parameters for initialising them, all in search for better performance. Optimisation is especially hard in huge code bases with many developers focusing on specific features and parts of the code. In these, increasingly common, code bases, humans usually lack the global view needed to confidently and inexpensively apply optimisations. As a result, many applications are deployed and run unoptimised. Artemis, for the first time, automates data structure selection and optimisation. Artemis is language-agnostic and seamlessly integrates with existing build systems. Artemis uses testing to globally, statistically validate its optimisations. Especially when using data structures from libraries, developers tend to rely on defaults and neglect optimisations that selecting alternative implementations or tuning parameters can offer. When Artemis optimises a library or utility function, every client of that library or utility benefits from the performance improvements. In particular, Artemis optimised Google Guava (data structures) and gson library (serialisation), two state-of-the-art, ubiquitous libraries in the Java ecosystem. Artemis’ improvements of these libraries show that it can optimise real world applications with thousand lines of code written by many developers and used by millions of users. Artemis’ automation can also effectively and inexpensively optimise libraries for a specific client, a task human optimizers simply cannot do at a reasonable cost. When Artemis was applied to clients of the gson library, it lead to 16.5% less memory consumption, while the execution time was reduced by 1%. Accordingly, for Google Guava, Artemis reduced memory consumption by 9%, and the execution time by 13%; these are savings that exceed the optimisations humans applied to these libraries because Artemis found them after the human optimisation pass. Artemis will change the economics of software optimisation. (G) Code optimisation is a problem of indisputable difficulty in computer science. It is time-consuming and expensive, especially on large code bases. It is also brittle: an optimisation for one version of a program can break or become a de-optimisation in the next release. Knuth said “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.” Under the immense time pressures of industrial software development, developers are heeding one part of Knuth’s advice: they are avoiding premature optimisation. Developers, however, often go too far and neglect the “critical 3%". Indeed, development fads that focus on fast solutions, like “Premature Optimisation is the horror of all Evil" and “Hack until it works" [4], advocate avoiding optimization altogether. A common and concrete situation in which developers avoid optimisation is when they select data structures from libraries (as we note above in our answer to E); they tend to rely on defaults and neglect optimisations that alternative implementations or tuning parameters can offer. This neglect matters: data structure selection and tuning can greatly improve application performance. Consider three examples: 1) Selecting an implementation that creates unnecessary temporary objects for the program’s workload [6]; 2) Selecting a combination of Scala data structures that scaled better, reducing execution time from 45 to 1.5 minutes [5]; and 3) Avoiding the use of poor implementation, such as those in the Oracle bug database that leak memory [7]. Despite these improvements, optimisation is expensive and its ROI is unclear or even negative for many projects. Developers need automated help to tackle optimisation. Artemis is that help. Given a set of Darwinian data structures, Artemis can search for optimal solutions in the background on the cloud, freeing developers to focus on new features. Artemis makes economical small optimizations, such as a few percent, that would not pay for the developer time spent realizing them. And sometimes, of course, Artemis, by virtue of being used, will find unexpectedly big performance gains. (H) To show the effectiveness of Artemis and its ability to optimise the performance of real-world software, and how it outperforms other solutions, we used it for the SBSE Challenge Track 2017 [1], held in coordination with the SSBSE Symposium. We applied Artemis to one of the four selected suites of open source development projects (Google Guava) and automatically optimised its performance. From the proposed solutions that Artemis found, 27.45% of them improve all measures: execution time, CPU usage, and memory consumption. Specifically, Artemis improved Guava’s memory consumption of Guava by up to 13%, its execution time by up to 9%, and its CPU usage by 4% [2]. For these results and its novelty, Artemis won the Best Challenge Paper award [3]. ------------------------------------------------------------------------------- 7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); Michail Basios, Lingbo Li, Fan Wu, Leslie Kanthan, and Earl T. Barr. 2018. Darwinian data structure selection. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018). ACM, New York, NY, USA, 118-128. DOI: https://doi.org/10.1145/3236024.3236043 ------------------------------------------------------------------------------- 8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, will be divided equally among the co-authors. ------------------------------------------------------------------------------- 9. a statement stating why the authors expect that their entry would be the "best,"; Software optimisation is a difficult and strenuous process for human developers, especially when there are many interacting factors to consider in a large code base (as we discussed above in our answer to criterion G). Such optimisation can sometimes be critical to certain resource-demanding situations. We proposed a generic software optimisation framework, Artemis, which tackles the optimisation problem by automatically identifying and tuning its data structures and corresponding parameters. Our approach helps developers identify inefficient data structures that they may have selected, and can also automatically change the source code such that it uses optimised data structures and parameters. Therefore, Artemis not only provides optimisation suggestions like many other similar tools do, but also employs these optimisations automatically with minimal human input. Additionally, we provide developers a report with all the changes in the code such that they have full transparency over their code base. Our approach is generic and can be applied in multiple programming languages (such as Java and C++). It also has the full capacity of optimising multiple objectives at the same time (execution time, memory consumption and CPU usage). We have applied it on a variety of open source projects and well defined benchmarks, both for Java and C++ in our paper, to demonstrate its performance improvements and its ease of use. The programs that we have improved are popular, real-world systems, used by thousands or millions of users. Furthermore, our work won the best challenge paper award on SBSE 2017 when applied to optimise the performance of Google Guava library. The research has already attracted media attention and some of the media coverage are listed as follows: The morning paper blog" (a popular research blog) [8]; Hacker News (was listed as the top 5 most read articles during the day of the publication) [10]; Best Challenge Paper Award [1]; Reddit [9]; ------------------------------------------------------------------------------- 10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. GI (genetic improvement), GA (genetic algorithms) 11. The date of publication of each paper. Nov 4, 2018 ------------------------------------------------------------------------------- References [1] http://ssbse17.github.io/challenge/ [2] Basios, M., Li, L., Wu, F., Kanthan, L., & Barr, E. T. (2017, September). Optimising darwinian data structures on google guava. In International Symposium on Search Based Software Engineering (pp. 161-167). Springer, Cham. [3] http://ssbse17.github.io/photos/ [4] B. Hardin. Companies with hacking cultures fai. https://blog.bretthard.in/companies-with-hacking-cultures-fail-b8907a69e3d, 2016. [Online; accessed 25-February-2017]. [5] R. J. Nowling. Gotchas with Scala Mutable Collections and Large Data Sets. http://rnowling.github.io/software/engineering/2015/07/01/ gotcha-scala-collections.html, 2015. [Online; accessed 18-February-2017]. [6] G. Xu, M. Arnold, N. Mitchell, A. Rountev, and G. Sevitsky. Go with the flow: profiling copies to find runtime bloat. ACM Sigplan Notices, 44(6):419–430, 2009 [7] G. Xu and A. Rountev. Precise memory leak detection for java software using container profiling. In Software Engineering, 2008. ICSE’08. ACM/IEEE 30th International Conference On, pages 151–160. IEEE, 2008. [8] https://blog.acolyer.org/2018/12/14/darwinian-data-structure-selection/ [9] https://www.reddit.com/r/programming/comments/a68lge/darwinian_data_structure_selection/ [10] https://news.ycombinator.com/item?id=18678803