Data Profiling to Guide Compiler Optimizations and Data Storage Transformations

Lukas Makor

This is a joint dissertation together with Sebastian Kloibhofer.

Abstract

Nowadays, applications are working with vast yet ever-increasing quantities of data. Processing these vast amounts of data involves challenges regarding memory consumption and performance. Thus, optimizing such applications is critical. Aside from manual optimizations by the developers, compilers play a vital role in program optimization. Modern compilers translate a program from a high-level programming language into machine code. In the process, they apply varying optimizations and tailor the program to the underlying hardware. However, we think there is still untapped potential: Taking a closer look at the data that actually flows through an application and its access patterns can help to optimize the application towards the specific workload. This includes optimizations on the data representation itself, such as transforming the structure of the data from an easy-to-use high-level representation into a faster or more memory- or cache-efficient lower-level representation.

There are many approaches to data-driven transformations and optimizations, including data-layout transformations, cache-conscious data-structure optimizations, and the identification and reporting of inefficiencies in data structures or containers for data-intensive applications. With this work, we want to investigate new directions in data-specific optimizations and extend support for them. One crucial aspect of our work is the integration of such optimizations into a state-of-the-art runtime and compiler infrastructure. With our work, we do not impede multithreading capabilities and perform the optimizations and transformations fully automatically, i.e., without user intervention. Additionally, we strive to preserve program semantics as much as possible; our approach should be fully transparent to the user and not impact the functionality of the program. As part of our efforts, we discuss cases that could lead to violations of semantics in detail and point out potential countermeasures for future implementations and extensions. We contribute several novel techniques for automated and opaque data-driven optimizations and transformations as part of this thesis, namely:

1. We propose an approach for automated transformation of large arrays of objects into a columnar layout to improve the cache behavior of applications. We present an implementation of this approach in a JavaScript runtime and showcase several optimization techniques in the JIT compiler that improve accesses to columnar arrays via dedicated loop transformations.
2. We developed profiling-based data structure replacement for a Java AOT compiler. This approach uses hand-crafted heuristics to automatically replace data structure allocations at individual allocation sites with customized, more memory-efficient variants. To estimate the applicability of this approach, we also analyzed the data structure usages in a comprehensive set of benchmarks.
3. We integrated field externalization into the same AOT compiler, a technique that uses profiling information to remove mostly unused fields from types to reduce the footprint of objects.

Our work is built on top of GraalVM, a high-performance multi-language virtual machine. The individual approaches we present in this thesis are intertwined with the JIT compiler of GraalVM and its AOT compilation system. We apply our techniques to programming languages that are widely used in industry. This demonstrates the viability of our work in a state-of-the-art production system and allows us to discuss and analyze its impact in the context of an already highly optimized system with modern compiler optimizations.

Kurzfassung

Heutzutage arbeiten Anwendungen mit riesigen und stetig wachsenden Datenmengen. Die Verarbeitung großer Datenmengen bringt Herausforderungen hinsichtlich Speicherverbrauch und Leistung mit sich. Daher ist die Optimierung solcher Anwendungen entscheidend. Neben manuellen Optimierungen durch die Entwickler:innen spielen Compiler eine wesentliche Rolle bei der Programmoptimierung. Moderne Compiler übersetzen ein Programm von einer Hochsprache in Maschinencode. Dabei wenden sie unterschiedliche Optimierungen an und passen das Programm an die zugrunde liegende Hardware an. Dennoch sehen wir noch ungenutztes Potenzial: Eine genauere Betrachtung der tatsächlich durch die Anwendung fließenden Daten und ihrer Zugriffsmuster lässt sich nutzen, um die Anwendung auf die konkrete Arbeitslast hin zu optimieren. Dazu gehören Optimierungen der Datenrepräsentation selbst, bei denen die Struktur der Daten von einer einfach zu verwendenden, abstrakten Darstellung in eine schnellere oder speicherbzw. cache-effizientere Form überführt wird.

Es gibt viele Ansätze für datengetriebene Transformationen und Optimierungen, einschließlich Transformationen des Datenlayouts, cache-spezifischer Optimierungen von Datenstrukturen und der Identifizierung und Meldung von Ineffizienzen in Datenstrukturen für datenintensive Anwendungen. Mit dieser Arbeit möchten wir neue Ansätze in diesem Forschungsfeld untersuchen und die Anwendungsgebiete für derartige Optimierungen erweitern. Ein wesentlicher Aspekt ist dabei die Integration in eine moderne Laufzeit- und Compilerinfrastruktur. Mit unserer Arbeit schränken wir die Multithreading-Fähigkeiten nicht ein und führen die Optimierungen und Transformationen vollautomatisch durch, d. h. ohne Benutzereingriff. Ebenso ist das Beibehalten der korrekten Programmsemantik von zentraler Bedeutung; unser Ansatz soll für Benutzer vollständig transparent sein und die Funktionalität des Programms nicht beeinträchtigen. Im Rahmen unserer Arbeit diskutieren wir daher ausführlich Fälle, die zu Verletzungen der Semantik führen können, und weisen auf mögliche Gegenmaßnahmen für zukünftige Implementierungen und Erweiterungen hin.

Im Rahmen dieser Dissertation stellen wir mehrere neuartige Techniken für automatisierte, datengetriebene Optimierungen und Transformationen vor, nämlich:

1. Wir präsentieren einen Ansatz zur automatischen Umwandlung großer Objektarrays in ein spaltenorientiertes Layout, um das Cache-Verhalten von Anwendungen zu verbessern. Wir beschreiben eine Implementierung dieses Ansatzes in einer JavaScript-Laufzeitumgebung und demonstrieren mehrere Optimierungstechniken in einem dynamischen Compiler, die Zugriffe auf spaltenorientierte Arrays durch dedizierte Schleifentransformationen beschleunigen.
2. Wir entwickelten einen profilbasierten Ansatz zum Ersetzen von Datenstrukturen für einen statischen Java-Compiler. Dieser nutzt manuelle Heuristiken, um die Allokation von Datenstrukturen an bestimmten Stellen im Programm automatisch durch eigens entwickelte, speichereffizientere Varianten zu ersetzen. Um die Anwendbarkeit dieses Ansatzes abzuschätzen, analysierten wir außerdem die Verwendung von Datenstrukturen anhand einer umfassenden Menge an Benchmarks.
3. Schließlich integrierten wir in denselben statischen Compiler die Externalisierung von Objektfeldern – eine Technik, die Profilinformationen verwendet, um überwiegend ungenutzte Felder aus Typen zu entfernen und damit den Speicherbedarf von Objekten zu reduzieren.

Unsere Arbeit baut auf GraalVM auf, einer hochleistungsfähigen, mehrsprachigen virtuellen Maschine. Die einzelnen in dieser Dissertation vorgestellten Ansätze sind eng mit dem dynamischen und dem statischen Compiler von GraalVM verwoben. Außerdem wenden wir unsere Techniken auf industrienahe und weitläufig verwendete Programmiersprachen an. Dies zeigt die Praxistauglichkeit unserer Arbeit in einem modernen Produktionssystem und ermöglicht es uns, deren Auswirkungen im Kontext eines bereits stark optimierten Systems mit modernen Compileroptimierungen zu diskutieren und zu analysieren.

PhD thesis, Johannes Kepler University Linz, September 2025