Pattern Mining and Genetic Improvement in Compilers and Interpreters

Oliver Krauss

Abstract

Writing source code is a challenging task, requiring the understanding of complex concepts, algorithms and programming paradigms. This task becomes increasingly challenging when source code has to be optimized for non-functional properties such as run-time performance, memory usage or energy efficiency. These properties often depend on in-depth knowledge of the language, the compiler and even the hardware architecture the source code will be run on. This thesis deals with the identification and verification of patterns in software that influence such non-functional properties. The goal is to help get an understanding, which patterns should be considered or avoided when optimizing towards a certain feature, and where to apply these patterns in the software. This is achieved by the novel combination of two distinct fields of research. Software Pattern Mining and Genetic Improvement, a Search- Based Software Engineering technique. The approach is applied directly at the compiler and interpreter level. This enables mining of a fine-granular software representation, combining it with in-depth information about the language, and gathering fine-granular performance measurements. A novel algorithm Knowledge-guided Genetic Improvement is presented that allows the generation of multiple semantically equivalent versions of software. These are then mined for discriminative patterns via the novel Independent Growth of Ordered Relationships algorithm. Several bug patterns, often occurring in the mutation operation of Genetic Improvement (GI), have successfully been identified and proven to produce bugs with an average confidence of 90.1%. Fix patterns reduce these bugs with a confidence of 94%. Identified patterns have been successfully applied in the field of Genetic Improvement by doubling population diversity, and reducing failing individuals in the population to 36.9% compared to 80% identified in related work. This allows Knowledge-guided Genetic Improvement to improve the run-time performance of 22 out of 25 algorithms by an average of 33.5%. The work also successfully identifies anti-patterns and patterns in the run-time domain that are responsible for this improvement. This thesis lays a foundation for identifying and verifying patterns in the non-functional domain. As a side effect, it also makes the results of experiments in the domain of Genetic Improvement explainable. This opens up opportunities to drive research in the domains Software Pattern Mining and Genetic Improvement even further. In the future, identified patterns may even be directly applicable in a compiler or interpreter.

Kurzfassung

Das Entwickeln von Software ist eine anspruchsvolle Aufgabe, die ein Verständnis von komplexen Konzepten, Algorithmen und Programmierparadigmen erfordert. Diese Aufgabe wird noch schwieriger, wenn Software für bestimmte nicht-funktionale Anforderungen, wie Laufzeit, Speichernutzung oder Energieeffizienz optimiert werden soll. Dieses Verhalten ist oft von der Sprache, dem Compiler und auch der Hardwarearchitektur abhängig, auf der die Software ausgeführt wird und erfordert fundierte Kenntnisse über diese. Diese Arbeit beschäftigt sich mit der Identifikation und Verifikation von Patterns in Software, die solche nicht-funktionale Anforderungen beeinflussen. Das Ziel ist es, verständlich zu machen, welche Patterns, an welcher Stelle in der Software, bei der Optimierung einer bestimmten nicht-funktionalen Anforderungen angewendet oder vermieden werden sollen. Dies wird durch die neuartige Kombination zweier Forschungsfelder erreicht. Software Pattern Mining und Genetic Improvement, eine Methode der Suchbasierten Softwareentwicklung. Diese Methodik wird direkt im Compiler und Interpreter angewendet. Dadurch wird die Suche fein-granularen Repräsentationsformen von Software ermöglicht und mit detaillierten Informationen über die Sprache sowie fein-granularer Laufzeitmessungen ermöglicht. Ein neuartiger Algorithmus Knowledge-guided Genetic Improvement wird vorgestellt, der die Generierung mehrerer semantisch äquivalenter Versionen von Algorithmen ermöglicht. Diese werden mit dem Independent Growth of Ordered Relationships Algorithmus nach diskriminativen Patterns durchsucht. Identifizierte Bug-Patterns, die oft im Mutations-Operator von Genetic Improvement entstehen, werden mit einer durchschnittlichen Sicherheit von 90.1% bestätigt. Patterns zur Prävention der Bugs werden mit 94% Sicherheit bestätigt. Diese Patterns wurden erfolgreich in der Domäne Genetic Improvement angewendet. Die Populationsdiversität wird verdoppelt, und Individuen, die Laufzeitfehler erzeugen, werden auf 36.9% im Vergleich zu 80% aus verwandten Arbeiten reduziert. Dies erlaubt Knowledge-guided Genetic Improvement die Laufzeit von 22 aus 25 getesteten Algorithmen im Durchschnitt um 33.5% zu reduzieren. In Folge werden Anti-Patterns und Patterns identifiziert, die für diese Verbesserung verantwortlich sind. Diese Arbeit legt eine Grundlage für die Identifikation und Verifikation von Patterns für nichtfunktionale Anforderungen. Als Nebeneffekt können so die Ergebnisse von Genetic Improvement erklärbar und nachvollziehbar gemacht werden. Dies eröffnet Möglichkeiten diese Forschung weiter zu vertiefen und voranzutreiben. In Zukunft können möglicherweise sogar Muster identifiziert werden, die direkt im Compiler oder Interpreter anwendbar sind.

PhD thesis, Johannes Kepler University Linz, April 2022