Managed Programming Languages and Runtimes 2022

Abstract of the opening session.

Abstract of the opening session.

In this talk we will look at a few interesting optimizations done in the .NET GC. One of the .NET GC’s principles is to separate mechanisms from policies which allows for much more dynamic tuning decisions. We will also use these optimizations to illustrate this principle. How does the .NET GC organize its objects on the heap when processing them during various GC phases? It groups adjacent live objects into what’s called plugs and uses dead objects inbetween them, called gaps, to store necessary info to facilitate relocation. Special handling is done for pinned objects. Dead spaces inbetween pinned plugs which are threaded onto a free list can get used sooner to satisfy allocation requests by a mechanism called demotion. And we can decide if we want to make them available sooner by separating mechanisms from policies. The GC can also make a decision whether it’s more productive to do a compacting or sweeping GC after calculating the relocation information (another example of separating mechanisms from policies). If it turns out to be a sweeping GC, the allocations done in the free list of the older generation will need to be repaired. We repair this by an UNDO field on each free list item and keeping a count on the original free list item we took off for allocation, and we only need to repair that many when threading back the items whose UNDO field was touched.

JavaScript is particularly difficult to implement efficiently because most of its expressions have all sorts of different meanings that involve all sorts of different executions that are not distinguished by any syntactic or type annotation. The common intuition is that only JIT compilers can handle it efficiently because they can rely on heuristic-based strategies that require having the program and the data on hand. But static (AOT) compilers can speculate and use heuristics too! To demonstrate that, we propose Hopc, an AOT compiler for JavaScript, based on the following assumption The most likely data structure a program will use is the one for which the compiler is able to produce its best code. Thus, contrary to most AOT compilers, Hopc does not rely on complex static analyses to optimize programs. It simply tries to generate its best code that it protects with guards. In this presentation, I will present its main optimizations and an in-depth performance analysis.

Around 1978 I wrote my first garbage collector, in PDP-10 assembly code, for the Clu language being developed by Barbara Liskov's group at MIT. From the 1980s to the present I've been involved with garbage collection research as one of the main threads of my work. In these reflections I try to glean what patterns I can, with hope that younger generations of researchers may find something useful in them. While I formally retired in 2020, I continue to be active in research and will offer a few thoughts about the future as well as the past.

Abstract of the opening session.

Abstract of the opening session.

Abstract of the opening session.

Abstract of the opening session.

Abstract of the opening session.

Abstract of the opening session.

Today's huge memories make it possible to store and process large data structures in memory instead of in a database. Hence, accesses to this data should be optimized, which is normally relegated either to the runtimes and compilers or is left to the developers, who often lack the knowledge about optimization strategies. As arrays are often part of the language, developers frequently use them as an underlying storage mechanism. Thus, optimization of arrays may be vital to improve performance of data-intensive applications. While compilers can apply numerous optimizations to speed up accesses, it would also be beneficial to adapt the actual layout of the data in memory to improve cache utilization. However, runtimes and compilers typically do not perform such memory layout optimizations.
In this work, we present an approach to dynamically perform memory layout optimizations on arrays of objects to transform them into a columnar memory layout, a storage layout frequently used in analytical applications that enables faster processing of read-intensive workloads. By integration into a state-of-the-art JavaScript runtime, our approach can speed up queries for large workloads by up to 9x, where the initial transformation overhead is amortized over time.

How concurrent compacting collectors store and manage their forwarding information is crucial for their overall performance. In this work, we address a pathological case of the two most common techniques for storing forwarding information that can lead to an explosion in the amount of memory needed to store forwarding addresses, up to 100% of the managed heap.
We propose CFW, a representation technique for forwarding information that guarantees that forwarding information for an entire heap can be stored in at most 3.14% of its size. By providing such a guarantee, we simplify the task of deploying programs with respect to memory needs. This is important given how memory is typically the dominating factor in the cost model for cloud-based deployments.
We explore the design space of our technique through a prototype implementation on-top of ZGC. A rigorous performance evaluation shows promising results.

Debugging IoT applications is challenging due to the hardware constraints of IoT devices, making advanced techniques like record-replay debugging impractical. As a result, programmers often rely on manual resets, or inefficient and time-consuming debugging techniques such as printf. Although simulators can help in that regard, their applicability is limited because they fall short of accurately simulating and reproducing the runtime conditions where bugs appear.
In this work, we explore a novel debugging approach, called event-based out-of-place debugging in which developers can capture a remotely running program and debug it locally on a (more powerful) machine. Our approach provides rich debugging features (e.g., step-back) that normally would not run on the hardware restricted devices by leveraging the developer's machine.
Two different strategies are offered to deal with resources which cannot be easily transferred (e.g. sensors): pull-based (akin to remote debugging), or push-based (where data updates are pushed to developer's machine during the debug session). We present EDWARD, an event-based out-of-place debugger prototype, implemented by extending the WARduino WebAssembly microcontroller Virtual Machine, that has been integrated into Visual Studio Code. To validate our approach, we show how our debugger helps uncover IoT bugs representative of real-world applications through several use-case applications. Initial benchmarks show that event-based out-of-place debugging can drastically reduce debugging latency.

Compiler optimizations are often based on hand-crafted heuristics to guide the optimization process. These heuristics are designed to benefit the average program and are otherwise static or only customized by profiling information. We propose machine-learning-based self-optimizing compiler heuristics, a novel approach for fitting optimization decisions in a dynamic compiler to specific environments. This is done by updating a machine learning model with extracted performance data at run time. Related work—which primarily targets static compilers—has already shown that machine learning can outperform hand-crafted heuristics. Our approach is specifically designed for dynamic compilation and uses concepts such as deoptimization for transparently switching between generating data and performing machine learning decisions in single program runs. We implemented our approach in the GraalVM, a high-performance production VM for dynamic compilation. When evaluating our approach by replacing loop peeling heuristics with learned models we encountered speedups larger than 30% for several benchmarks and only few slowdowns of up to 7%.

Trusted execution environments (TEEs) gained significant traction in recent years. They have become the foundation of Confidential Computing in cloud services, where certain security properties can be guaranteed on untrusted servers. Despite this adoption, writing code to target TEEs remains challenging. The SDKs for popular TEE implementations, like Intel SGX, are aimed at low-level languages like C/C++. Previous research has introduced support for developing and running programs written in managed programming languages in a TEE environment. However, in these works, the language runtime is embedded into the TEE, increasing the Trusted Computing Base (TCB) and thus inherently reducing trust into the TEE itself. To solve this problem, we propose a new approach to integrate the development of TEE code in managed languages, without the need to embed the full language runtime inside the TEE. It allows developers to write the TEE logic as part of their program in a managed programming language. Using the existing compiler infrastructure, the TEE logic is extracted and passed to a source-to-source compiler that transforms it into a low-level unmanaged equivalent. The resulting low-level code is then compiled by the compiler toolchain targeting the TEE platform. This paper reports on the design and the first results of our work-in-progress implementation of SecSharp, a tool to enable TEE development in C#.

Garbage collectors provide memory safety, an important step toward program correctness. However, correctness of the collector itself can be challenging to establish, given both the style in which such systems are written and the weakly-ordered memory accesses of modern hardware. One way to maximize benefits is to use a framework in which effort can be focused on the correctness of small, modular critical components from which various collectors may be composed.
Full proof of correctness is likely impractical, so we propose to gain a degree of confidence in collector correctness by applying model checking to critical kernels within a garbage collection framework. We further aim for a model framework, paralleling the framework nature of the collector, in hope that it will be easy to create new models for new collectors.
We describe here a prototype model structure, and present results of model checking both stop-the-world and snapshot-at-the-beginning concurrent marking. We found useful regularities of model structure, and that models could be checked within possible time and space budgets on capable servers. This suggests that collectors built for the new framework might be model checked, and further that it may be worthwhile to develop a domain-specific language from which to generate those models.

The RISC-V Instruction Set Architecture (ISA) is an open-source, modular and extensible ISA. The ability to add new instructions into a dedicated core opens up perspectives to accelerate VM components or provide dedicated hardware IPs to applications running on top. However, the RISC-V ISA design is clashing on several aspects with other ISAs and therefore software historically built around them. Among them, the lack of condition codes and instruction expansion through simple instruction combination. In this paper we present the challenges of porting Cogit, the Pharo’s JIT compiler tightly linked to the x86 ISA, on RISC-V. We present concrete examples of them and the rationale behind their inclusion in the RISC-V ISA. We show how those mismatches are solved through design choices of the compilation process or through tools helping development: a VM simulation framework to keep the development in a high-level environment for the most part, an ISA-agnostic test harness covering main VM functionalities and a machine code debugger to explore and execute generated machine code. We also present a way to prototype custom instructions and execute them in the Pharo environment.

Sustainable computing needs energy-efficient software. This paper explores the potential of leveraging the nature of software written in managed languages: increasing energy efficiency by changing a program's memory management strategy without altering a single line of code. To this end, we perform comprehensive energy profiling of 35 Java applications across four benchmarks. In many cases, we find that it is possible to save energy by replacing the default G1 collector with another without sacrificing performance. Furthermore, potential energy gains can be even higher if performance regressions are permitted. Inspired by these results, we study what the most energy-efficient GCs are to help developers prune the search space for energy profiling at a low cost. Finally, we show that machine learning can be successfully applied to the problem of finding an energy-efficient GC configuration for an application, reducing the cost even further.

Automatic memory management relieves programmers of the burden of having to reason about object lifetimes in order to soundly reclaim allocated memory. However, this automation comes at a cost. The cost and benefits of garbage collection have been the subject of contention for a long time, and will likely remain so. However, until now, the question is surprisingly under-studied.
We examine the costs and benefits of garbage collection through four studies, exploring: (i) the space-overheads of garbage collection; (ii) the effects of garbage collection on the execution time of a mutator using a free list allocator; (iii) how proximity to garbage collection events affects mutator performance; and (iv) the effects of the delay in memory reuse on manually managed workloads. We conduct this study in a contemporary setting using recent CPU microarchitectures allowing us to shed new light on garbage collection overheads in a modern context.
We find that: (i) simple, fully-copying collectors such as SemiSpace have average space overheads of 1.70x, while Immix has an overhead of 1.13x a baseline approximating manual memory management; (ii) for the collection frequencies we evaluate, garbage collection has little impact on a mutator using an optimized free list allocator; (iii) the proximity of mutator work to the nearest collection has little impact on its performance, unless a free list allocator is used; and (iv) postponing the reuse of memory has only a modest effect in terms of time and space. The costs and benefits of garbage collection are likely to remain subject to contentious discussion. However, the methodologies and evaluations we present here provide a deeper understanding of the differences in costs between manual memory management and garbage collection.

Dynamic taint analysis is a popular analysis technique which tracks the propagation of specific values while a program executes. To this end, a taint label is attached to these values and is dynamically propagated to any values derived from them. Frequent application of this analysis technique in many fields has led to the development of general-purpose analysis platforms with taint propagation capabilities. However, these platforms generally limit analysis developers to a specific implementation language, to specific propagation semantics or to specific taint label representations.
In this paper we present label-defined dynamic taint analysis, a language-agnostic approach for specifying the properties of a dynamic taint analysis in terms of propagated taint labels. This approach enables analysis platforms to support arbitrary adaptations to these properties by delegating propagation decisions to propagated taint labels and thus to provide more flexibility to analysis developers than other analysis platforms. We implemented this approach in TruffleTaint, a GraalVM-based taint analysis platform, and integrated it with GraalVM's language interoperability and tooling support. We further integrated our approach with GraalVM's performance optimizations. Our performance evaluation shows that label-defined taint analysis can reach peak performance similar to that of equivalent engine-integrated taint analyses. In addition to supporting the convenient reimplementation of existing dynamic taint analyses, our approach enables new capabilities for these analyses. It also enabled us to implement a novel tooling infrastructure for analysis developers as well as tooling support for end users.

Abstract of the opening session.