Zur Seitenansicht
 

Titelaufnahme

Titel
On-stack Replacement in Truffle Interpreters for Non-structured Languages / submitted by Raphael Mosaner
AutorInnenMosaner, Raphael
Beurteiler / BeurteilerinMössenböck, Hanspeter
ErschienenLinz, 2018
Umfang65 Seiten : Illustrationen
HochschulschriftUniversität Linz, Masterarbeit, 2018
SpracheEnglisch
DokumenttypMasterarbeit
Schlagwörter (EN)on-stack replacement / OSR / truffle
URNurn:nbn:at:at-ubl:1-25407 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist gemäß den "Hinweisen für BenützerInnen" verfügbar
Dateien
On-stack Replacement in Truffle Interpreters for Non-structured Languages [0.89 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Truffle ist ein weit verbreitetes Framework um performante Interpreter für Programmiersprachen zu entwickeln, was durch den Einsatz des dynamischen Graal Compilers ermöglicht wird. Neben etlichen Optimierungen stellt Truffle auch einen Mechanisums für On-stack Replacement (OSR) zur Verfügung, der es ermöglicht, von einer interpretierten Version einer lang laufenden Schleife zu einer optimierten, kompilierten Version zu wechseln noch während diese ausgeführt wird. Dieser Mechanismus beschleunigt vor allem den Programmstart, wo Schleifen ansonsten solange interpretiert werden, bis die umgebende Methode kompiliert wird, was für selten ausgeführte Funktionen unter Umständen nie der Fall ist. Jedoch erwartet Truffles OSR Mechanismus, dass Schleifen bereits von der Sprachimplementierung identifiziert und als solche dargestellt werden. Daher können Bytecode Interpreter, die Kontrollflussstrukturen nur implizit über unstrukturierte Sprungbefehle darstellen nicht von der bestehenden Implementierung von Truffles OSR profitieren. Um OSR auch für solche unstrukturierten Sprachen zu ermöglichen, beschreibt diese Arbeit einen Ansatz, der Schleifen teilwesie rekonstruiert um diese dann explizit darstellen zu können. Desweiteren wird der beschriebene Ansatz anhand eines Prototyps für Sulong, ein Bytecode Interpreter für LLVM Bitcode, mit dessen Hilfe C und C++ Programme ausgeführt werden können, umgesetzt. Bei der anschließenden Evaluierung mittels C Benchmark-Tests zeigen sich teils signifikante Verbesserungen beim Programmstart sofern OSR anwendbar ist. So konnte die Ursprungsversion von Sulong Benchmarks wie fannkuch nicht innerhalb eines Tages ausführen, was durch den Einsatz von OSR auf weniger als 30 Minuten reduziert werden konnte. Obwohl noch Probleme mit anderen Compiler Optimierungen bestehen, denken wir, dass auch Interpreter für andere unstrukturierte Sprachen auf ähnliche Art und Weise von Truffles OSR Mechanismus profitieren können.

Zusammenfassung (Englisch)

Truffle is a widely used language implementation framework that allows the implementation of fast interpreters by employing the dynamic Graal compiler. Amongst other optimizations, Truffle provides a mechanism for On-stack Replacement (OSR) that allows switching from a long-running, interpreted version of a loop to an optimized machine-code version of that loop while it is being executed. This mechanism especially speeds up program start where otherwise loops are interpreted until the surrounding function is compiled, which might not ever be the case for rarely executed functions. However, Truffles OSR approach assumes that the language implementation can explicitly identify and represent host-language loops. Bytecode interpreters, on the other side, represent control flow implicitly via unstructured jumps and thus cannot use Truffles OSR implementation as is. To enable OSR also for such non-structured languages, this thesis proposes the partial reconstruction of loops in order to explicitly represent them in a bytecode interpreter. Furthermore, it shows an implementation of the presented approach in Sulong, a bytecode interpreter for LLVM bitcode, which allows the execution of C/C++. Evaluation with a set of C benchmarks indicates significant improvements in program warm-up with OSR being applicable. For example, while Sulong originally could not execute some benchmarks where execution remained in an interpreted loop within a day (such as fannkuch), employing OSR reduced their total run time to less than half an hour. While there are still interferences with other compiler optimizations, we believe that interpreters for other non-structured languages could employ similar techniques to benefit from Truffles OSR mechanism as well.

Statistik
Das PDF-Dokument wurde 8 mal heruntergeladen.