Thread-safe and Efficient Data Representations in Dynamically-typed Languages

Benoit Daloze

Abstract

We are in the multi-core era. Dynamically-typed languages are in widespread use, but their support for multithreading still lags behind. Specifically, their runtime systems either lack support for parallelism completely or they have many drawbacks, such as not scaling, having a significant overhead for single-threaded applications and exposing implementation-level races to the user. Runtime systems use sophisticated techniques to efficiently represent the dynamic objects and versatile collections present in dynamically-typed languages. One of the major reasons for not supporting well parallelism is these techniques are often unsafe in multi-threaded environments. In this thesis, we present a solution for efficient and thread-safe shared-memory parallelism in dynamically-typed language runtimes. First, we design a new efficient and thread-safe object model for dynamic languages, only requiring synchronization when writing to objects shared between multiple threads. Accesses to objects reachable by only a single thread remain unsynchronized and maintain single-threaded performance. Then, we devise a thread-safe and scalable design for collections in dynamic languages, which we apply to array-like and dictionary-like collections. We use multiple levels of synchronization to optimize for the usage pattern of each collection instance. Collections operations are unsynchronized until the collection becomes reachable by multiple threads. For array accesses within bounds, we use a new mechanism for global synchronization, avoiding overhead for this usage pattern. For the general case, we introduce a new lock that provides scalability for both read and write accesses, while supporting the versatile operations that dynamic languages provide and retaining the sophisticated techniques for representing collections efficiently in memory. We evaluate our work in TruffleRuby, a state of the art high-performance implementation of the Ruby programming language. We show that our thread-safe objects and collections do not cause any overhead when they are reachable by only a single thread. Our experiments show that our approach scales linearly for object, array and dictionary accesses, achieves the same scalability as statically-typed languages for classic parallel algorithms, and scales better than other Ruby implementations on Ruby workloads.

Kurzfassung

Wir befinden uns in der Multicore-Ära. Dynamisch typisierte Sprachen sind weit verbreitet, aber ihre Unterstützung für Multi-Threading hinkt immer noch hinterher. Insbesondere ihre Laufzeitumgebungen haben entweder keine vollständige Unterstützung für Parallelität oder viele Nachteile, wie z.B. mangelnde Skalierung, Laufzeitnachteile von Programme die in einem einzigen Thread ausgeführt werden oder Race-Conditions der Implementierung die Einfluss auf die Benutzeranwendung haben können. Laufzeitumgebungen verwenden ausgefeilte Techniken, um die dynamischen Objekte und vielseitigen Collections-Frameworks von dynamischer Sprachen zu implementieren. Einer der Hauptgründe für die mangelnde Unterstützung von parallelen Sprachfeatures ist, dass diese Techniken in Multi-Threading-Umgebungen oft zu Abstürzen führen. In dieser Arbeit stellen wir eine Lösung für die effiziente und threadsichere Ausführung von Programmen mit gemeinsamen Speicherbereichen in Laufzeitumgebungen für dynamisch typisierte Sprachen vor. Zuerst stellen wir ein neues, effizientes und threadsicheres Objektmodell für dynamische Sprachen vor. Dieses Objektmodell erfordert Synchronisierung nur für Schreiboperationen auf Objekte die von mehreren Threads genutzt werden. Zugriffe auf Objekte, die nur von einem einzigen Thread erreicht werden können, bleiben unsynchronisiert und erreichen die gleiche Performance wie single-threaded Programme. Dann entwickeln wir ein threadsicheres und skalierbares Design für Collections in dynamischen Sprachen, die wir auf Array- und Dictionary-Datenstrukturen anwenden. Wir verwenden mehrere Synchronisationsebenen, um das Nutzungsmuster jeder Collection-Instanz zu optimieren. Die Collections-Vorgänge werden unsynchronisiert ausgeführt, bis die Instanz von mehreren Threads erreichbar wird. Für Array-Zugriffe innerhalb der Speichergrenzen verwenden wir einen neuen Mechanismus zur globalen Synchronisation, der den Overhead für dieses Nutzungsmuster vermeidet. Für den allgemeinen Fall stellen wir eine neue Sperrtechnik vor, die Skalierbarkeit für Lese- und Schreibzugriffe bietet und gleichzeitig die vielseitigen Operationen unterstützt, die dynamische Sprachen bieten. Diese Lösung unterstützt die bereits existierenden Techniken, Collections effizient im Speicher abzulegen. Wir bewerten unsere Arbeit in TruffleRuby, einer hochmodernen, leistungsstarken Implementierung der Programmiersprache Ruby. Wir zeigen, dass unsere threadsicheren Objekte und Collections keinen Overhead verursachen, wenn sie nur von einem einzigen Thread erreichbar sind. Unsere Experimente zeigen, dass unser Ansatz linear für Objekt-, Array- und Dictionary-Zugriffe skaliert. Die Lösung erreicht die gleiche Skalierbarkeit wie statisch typisierte Sprachen für klassische parallele Algorithmen, und skaliert besser als andere Ruby-Implementierungen auf Ruby-Workloads.

PhD thesis, Johannes Kepler University Linz, October 2019