Serializable Coroutines for the HotSpot™ Java Virtual Machine

Lukas Stadler
Institute for System Software
Johannes Kepler University Linz, Austria

Abstract

Coroutines are non-preemptive light-weight processes. Their advantage over threads is that they do not have to be synchronized because they pass control to each other explicitly and deterministically. Coroutines are therefore an elegant and efficient implementation construct for numerous algorithmic problems.

Many mainstream languages and runtime environments, however, do not provide a coroutine implementation. Even if they do, these implementations often have less-than-optimal performance characteristics because of the trade-off between run time and memory efficiency.

As more and more languages are implemented on top of the Java virtual machine (JVM), many of which provide coroutine-like language features, the need for a coroutine implementation has emerged. This thesis presents an implementation of coroutines in the JVM that efficiently handles a large range of workloads. It imposes no overhead for applications that do not use coroutines and performs well for applications that do.

The implementation of two advanced concepts, namely thread-to-thread migration and serialization of coroutines, is also explained along with the API that is used to control them. For evaluation purposes, coroutines were used to implement JRuby fibers, which lead to a significant speedup of certain JRuby programs. This thesis concludes with general benchmarks that show the performance of the approach and outline its run-time and memory characteristics.

Kurzfassung

Coroutinen sind nicht-prämptive, leichtgewichtige Prozesse. Im Gegensatz zu Threads müssen sie nicht synchronisiert werden, da die Ausführungsreihenfolge explizit und deterministisch festgelegt wird. Dadurch ermöglichen sie eine elegante und effiziente Implementierung vieler Algorithmen.

Allerdings stellen viele verbreitete Laufzeitumgebungen und Programmiersprachen keine Coroutinen zur Verfügung, und existierende Coroutinen-Implementierungen bieten oft nur unzureichende Kompromisse zwischen Laufzeit- und Speichereffizienz.

Dadurch, dass es mehr und mehr Programmiersprachen-Implementierungen für Java VMs gibt, von denen viele Coroutinen-ähnliche Funktionen anbieten, ergibt sich eine vermehrte Nachfrage nach einer Coroutinen-Implementierung. Diese Arbeit präsentiert eine Implementierung, die für einen weiten Bereich verschiedener Aufgaben performant ist, wobei Programme, die Coroutinen nicht benutzen, nicht verlangsamt werden.

Auch zwei weitergehende Konzepte, das Migrieren von Coroutinen zwischen Threads und das Serialisieren von Coroutinen, werden zusammen mit dem benötigten API beschrieben.

Zur Evaluierung wurden JRuby fibers mittels Coroutinen implementiert, was zu einer starken Steigerung des Programmdurchsatzes führte. Die Arbeit schließt mit einer Evaluierung der Laufzeit- und Speichercharakteristika der Implementierung.

Master's thesis, Johannes Kepler University Linz, February 2011

Download as PDF