Managed Programming Languages and Runtimes 2022

Vector instructions are a class of processor instructions that allow data level parallelism by performing the same instruction on multiple pieces of data, instead of a single one as usual. On managed runtimes, special support from the virtual machine is required to generate vector instructions for the host machine’s architecture. There are two possible approaches to achieve this: add virtual machine intrinsics that use vector instructions, or extend the bytecode set with vector operations that are then mapped to processor vector instructions. Intrinsics are methods implemented at the VM level, using native code. They allow low-level control of the operations being performed and are generally used to build entire operations, such as sorting an array or adding two arrays together. Bytecode operations, on the other hand, are usually designed to be composable. For example, the operation of adding two arrays can be composed of bytecodes to load a part of an array into a vector register, one to add the vector registers, and one to store the result back into an array. We implemented both approaches in the Pharo VM and analyzed the impact of such safety checks on performance. We found that the most significant difference in performance between intrinsic methods and bytecode operations stems from the latter performing redundant type checking on bytecode's parameters, bounds checking on array accesses, and overflow tests on array iterators. These checks are necessary since bytecodes can be composed in arbitrary sequences, and so they need to prevent invalid ones from causing catastrophic errors. This requires setting up safety checks on each bytecode to ensure that each operates with valid parameters. However, once a bytecode sequence is formed, some of these checks could be removed without compromising the correctness of that sequence. We propose existing compiler optimizations than could be used to reduce the impact of these checks on performance, although we have not yet evaluated their effectiveness.

The Garbage Collector in PharoVM takes human perceivable pauses (~3 seconds) on big heaps (more than 4 GB). One of the reasons is that it must traverse the entire memory searching for collectable objects. However, lot of objects will almost never garbage collected, like classes, methods, literals. We are developing a Permanent Space for the generational Garbage Collector to allocate these kind of objects. Also, to be worth enough, we need to select a smart object graph to move to this space. We are making benchmarks over some possible scenarios and analysing the resulted object graph thru simulations in order to understand what are the best constraints to select these objects. We present preliminaries results and open questions from this work in progress.

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 that 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.

WebAssembly, known as Wasm, is an interpreted portable bytecode execution format that is growing in popularity. In this work, we perform a simple pair of characterizations of Wasm. Statically, we compare the instruction set to other portable bytecodes like JVM and PCODE, showing that Wasm operates at a lower abstraction level than JVM, similar to PCODE. Dynamically, we study the Wasm instruction mix for a set of common benchmark applications. This investigation reveals that, like JVM, data movement operations occur most frequently in instruction traces. We conclude by discussing possible future directions for optimizing Wasm execution.

Many garbage collectors move live objects to avoid fragmentation and as a way to free memory. When an object is moved, all its incoming pointers must be remapped to its new location. However, at the point when the object is moved, its incoming pointers are not known. Thus, garbage collectors must collect and manage forwarding information that allows remapping outdated addresses. Because of the relatively large sizes of pointers in 64-bit systems with large heaps, the amount of memory needed to store forwarding information can become theoretically as large as the heaps whose addresses they are remapping. While unlikely, the size of forwarding information needed at different times throughout the lifetime of a program is both hard to predict and completely beyond programmer control. In this work, we present a technique for compressing forwarding information that guarantees that the amount of memory needed to remap a heap is at most 3.14% of the size of the heap. We show that our technique can be applied to industry-grade ZGC in OpenJDK with negligible performance impact.

Performance is often critical in the context of large-scale web-applications. Achieving it is non-trivial, especially for applications written in dynamic languages such as Ruby, where it is common to use reflection and many small methods. For such languages, we need good just-in-time compilation, which in turn relies heavily on lookup caches, splitting, and inlining. We studied the impact of these optimisations on the call-site behaviour of 76 Ruby benchmarks. This poster presents our findings: we show that the combined use of lookup caches, splitting, and the elimination of targets in lookup caches leads to a quasi-complete monomorphisation of all the polymorphic call-sites of our benchmark set. Monomorphisation is beneficial for performance, as it enables fast call resolution, and other optimisations such as inlining. However, our analysis also suggests these call-site optimisations, notably splitting, are too aggressive, leading to unnecessarily cloning of methods, which increases the memory footprint and compilation overhead of the application. To address this issue, we suggest extending contextual dispatch [1] for the use in splitting heuristics for Ruby. Originally, contextual dispatch uses calling-context information to enable optimisations, notably by dispatching to compiled functions for a specific context. This improves both execution time and memory footprint, as the pre-specialized functions can be shared between call-sites with the same context signature. We present our idea of how to extend this logic to guide the splitting heuristics based on argument-types. We show the potential impact of such an approach on the program’s inner representation. This approach is yet-to-be implemented. In the future, we will also explore how richer contextual information, going beyond argument-types, such as specific object properties, or the call-chain structure, can further guide splitting decisions. [1] Flückiger, O., Chari, G., Yee, M. H., Ječmen, J., Hain, J., & Vitek, J. (2020). Contextual dispatch for function specialization. Proceedings of the ACM on Programming Languages, 4(OOPSLA), 1-24.

Debugging IoT applications is challenging due to the hardware constraints of IoT devices. This makes advanced techniques like record-replay debugging impractical. As a result, developers 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. This demonstration is aimed at participants interested in programming and debugging IoT applications. The demo introduces a new debugging approach for IoT applications through EDWARD, which is, a debugger that implements a novel IoT debugging technique called event-based out-of-place debugging within an existing WebAssembly VM for microcontrollers called WARDuino. With EDWARD developers can on-demand capture a remotely running IoT application and debug it locally at the developer's machine. As a result, developers can debug on a more powerful machine and benefit from low debugging interference as well as advanced debugging features such as step-back which normally would not run on hardware-restricted devices. To deal with the absence of device resources on the developer's machine (e.g., sensors, buttons, etc.), EDWARD implements two access strategies: (1) developers can issue a request of the value of the device resource (e.g., read from the temperature sensor plugged into the device), or (2) developers can register for notifications when changes happen at the resource so that the value is pushed to the developers (e.g., notifies of button presses on the device). We implemented our prototype debugger interface as a VSCode plugin that lets developers apply classical debugging operations (e.g., add breakpoint, step, etc.), gives fine-grained control over the access to the device resources, and lets developers commit source code changes (over the air) to the remote device after fixing a bug.

A significant portion of today’s applications use managed runtime languages like Java, and therefore, take advantage of automatic memory management, also commonly known as Garbage Collection (GC). GC is a key attribute in managed runtimes as it eliminates developers’ effort to manually allocate and deallocate the objects in memory, thus improving developer productivity. GC algorithms may significantly affect application performance goals, especially those dealing with large data (which may focus on throughput) and substantial transaction rates (which may focus on latency). However, there is still no tool to help users and developers to overcome the challenges of selecting a suitable GC solution for their applications. Several GC algorithms are available in different Java versions attempting to improve performance metrics like throughput, pause time, and memory footprint. As these performance metrics are the most common, we consider them to be the most critical metrics that highly affect the user’s applications. This study follows a simple yet effective methodology to evaluate four well-known production collectors considering throughput and pause time while the memory available to collectors changes. Then, we propose an approach to recommend a suitable collector for a user’s application while letting the user decide on his performance priority.

Picking the right data structure for the right job is one of the key challenges for every developer. However, especially in the realm of object-oriented programming, the memory layout of data structures is often still suboptimal for certain data access patterns, due to objects being scattered across the heap. Therefore, this work presents an approach for the automated transformation of arrays of objects into a contiguous format (called columnar arrays). At run time, we identify suitable arrays, perform the transformation and use a dynamic compiler to gain performance improvements. In the evaluation, we show that our approach can improve the performance of certain queries over large, uniform arrays.

The Truffle framework allows language implementations to reach state-of-the-art run time performance while only providing an abstract syntax tree (AST) interpreter; the AST is compiled to machine code using GraalVM's JIT compiler. However, it can take some time before this fully optimized code is generated and executed: startup performance is consequently tightly bound to interpreter performance, therefore reducing the execution time requires us to improve interpreter performance instead of solely focusing on the JIT compiler. Through the use of a novel technique called supernodes, we take steps towards improving the run-time performance of Truffle-based interpreters, aiming to reduce programs' overall execution time by improving interpreter performance. We take inspiration from a well-known bytecode interpreter optimization technique: superinstructions, which reduce the instruction dispatch overhead by concatenating existing instructions. In the case of supernodes, AST nodes are merged, creating a single entity which has the same behavior as the original tree. The main performance gain of supernodes comes from removing redundant node safety guards: for instance, regular nodes have to check the type of their input data through a type guard, even though it may have already been determined by another node which had no way of sharing this information. Supernodes avoid this problem through unifying the node contexts. Moreover, similarly to superinstructions, performance is also gained through reducing the node dispatch overhead as a result of using fewer nodes. So far, we have been relying on the research language TruffleSOM, a minimal Smalltalk dialect implemented using Truffle, and we are focusing on the Are We Fast Yet benchmark suite, which contains both micro- and macro- benchmarks. Initial results are promising, showing up to 42% run time reduction with the addition of 20 supernodes. Moreover, there are currently no performance regressions for any of our benchmarks compared to a baseline with no supernode candidates available. However, node trees that yield valuable supernodes are currently detected manually, and the process of generating supernodes from them is currently not automated. In the future, we aim to develop heuristics to identify potential supernode candidates: both at parsing time through static analysis, as well as later during run time through detection of frequently called nodes that could yield performance gains should they be merged together. The supernodes would then be generated based on the code of the selected AST nodes. In addition, we aim to port our technique to more complex Truffle implementations used in the industry, such as GraalPython or TruffleRuby.

Dynamic taint analysis assigns taint labels to sensitive data and tracks the propagation of such tainted data during program execution. This program analysis technique has been implemented in various analysis platforms targeting specific programming languages or program representations and it has been applied to diverse fields such as software security and debugging. While some of these platforms support customization of their taint analysis, this customization is typically limited to certain analysis properties or to predefined options. This limitation can require analysis developers to modify the analysis engine itself in order to adapt other analysis properties or to implement new taint analysis applications. We designed label-defined dynamic taint analysis as a new approach to specifying a dynamic taint analysis in terms of taint labels. This approach enables an analysis platform to allow analysis developers to adapt arbitrary analysis properties without modifying the platform itself. We implemented this approach in TruffleTaint, a GraalVM-based dynamic taint analysis platform targeting multiple programming languages. Our prototype supports implementing taint analyses in multiple programming languages and further provides tooling support for analysis development. In this tool demonstration we will present the capabilities of our prototype and demonstrate the implementation of label-defined dynamic taint analyses with common adaptations to various analysis properties.

The Pharo language is an object-oriented programming language based on Smalltalk [1] featuring a JIT compiler to mitigate the overhead of the virtual machine interpreting instructions. Currently, Pharo’s JIT compiler consists of handwritten machine code templates that correspond to bytecode instructions. These templates, however, duplicate the behaviour of the bytecode interpreter. To solve this code duplication, a compiler was recently introduced to compile these machine code templates based on the interpreter is in development. Such a JIT compiler compiler is called Druid and it's currently under development. In this poster, we present semantic-preserving optimizations added to Druid to eliminate redundant code. In particular, we introduce global value numbering (GVN) and investigate the effects it has when combined with other optimizations like Conditional Constant Propagation (SCCP) and Dead Code Elimination (DCE). We implement a GVN approach based on a dominator tree encoding dominator relationships in the control-flow graph that is used to determine what expressions will always be live in a given basic block. The motivation for implementing dominator-based value numbering (DNVT) is that it fully utilizes the intermediate representation Druid uses. More concretely, the existing control-flow graph allows for quickly computing the dominator tree and static single assignment (SSA) form is the key to assigning value numbers to every expression in the program without doing live analysis. We validated our approach by comparing the percentage of instructions being removed by DVNT with respect to other optimizations on basic operations such SCPP and DCE. Preliminary results show that DVNT removes a lot of instructions compared to DCE and SCCP. Moreover, combining multiple optimizations allows for more optimized code.

The Boehm-Demers-Weiser collector is a conservative garbage collection scheme generally used for C/C++ applications. In this demo, we will show the collector running with C benchmark programs on a new CHERI-style hardware capability platform, specifically the Arm Morello system.