Effect handlers and dynamic wind provide mechanisms for implementing language constructs, such as generators and dynamically scoped variables, as libraries or embedded domain-specific languages (EDSLs). This paper presents a library implementation of dynamic wind in OCaml that is composable with effect handlers in OCaml. Their composition is challenging, especially when a delimited continuation captured by an effect handler escapes the handler's scope. Indeed, a straightforward retrofitting of Voigt's dynamic wind, originally implemented in Effekt, does not behave intuitively. In particular, it fails to implement dynamically scoped variables when a generator created within a dynamic wind scope resumes outside that scope. This is because Voigt's approach captures only the dynamic winds inside delimited continuations. Our key idea is to decorate delimited continuations with the dynamic winds enclosing the effect handler, i.e., the delimited continuation itself. We implement our dynamic wind library on top of OCaml's effect handlers and demonstrate that our design yields intuitive behavior.

Processing-in-memory (PIM) is a promising approach to overcome the performance bottleneck caused by the gap between CPU speed and memory speed, known as the memory wall problem. The UPMEM PIM-enabled memory is the first commercialized general-purpose PIM accelerator, to which the program running on the host CPU offloads computation kernels. Its DRAM Processing Units (DPUs) are general-purpose processors and have the flexibility to run various computation kernels. However, there is no support for programming in managed languages with garbage collection (GC). In this paper, we design GC for DPUs, which is a key component of managed runtimes. Our GC is a parallel generational GC, whose young space is in scratch pad memory (SPM). The GC updates pointers in promoting objects before copying them to old space in DRAM to reduce DRAM accesses. It also determines class information needed for minor GC of each computation kernel at compile time and caches them in SPM. The major GC routines are compiled in a separate binary so that the binaries of computation kernels fit in 24 KB of program memory. The evaluation results using a micro benchmark showed that our proposed techniques reduced up to 85.9% DRAM accesses and improved performance by 46.2% for our benchmark. The GC scaled up to 11 threads, and the remaining code size for the GC routine was only 4.3 KB after separating 6.9 KB of major GC.

This paper presents a managed memory system for micro controllers with only a small amount of memory but with NOR flash memory. This system is targeted at a device such as Raspberry Pi Pico, which is equipped with ARM Coretex M0+, on-chip 264KB SRAM, and 2MB flash memory. To extend an available memory space for user programs, this system provides virtual memory by using NOR flash memory as a backing store. Since writing data to the flash memory is slow and the number of writes is limited during its lifetime, this system cooperates language-level memory management to mitigate these drawbacks. It runs a garbage collector that may move objects aggressively when a memory page is paged-out to flash memory. This paper also proposes a technique named a forwarding bit to efficiently implement the movement of objects stored in flash memory. According to experiments using a prototype of this system implemented for the mruby language on Raspberry Pi Pico, when the available SRAM size is small, this system successfully reduces the number of erasures in flash memory to an average of less than 10% and even improves execution speed by an average of 4 times faster despite overhead of moving objects.

Orthogonal persistence implemented with non-volatile memory (NVM) allows the programmers to easily create persistent containers, which are container data-structures preserved even after the process terminations due to a system crash. However, the state-of-the-art technique of its implementation in multithreaded languages rely on the instruction, which limits out-of-order execution. This overhead is applied regardless of the use of persistent objects. We propose a technique that does not disturb out-of-order execution. Instead, we let the thread that is attempting to make an object persistent synchronize with all the other threads by handshaking. Furthermore, we propose a technique to eliminate the redundancy of that synchronization by a novel static analysis called persistence-aware escape analysis. We implemented both the proposed techniques in RBP (replication based persistency) implemented in the HotSpot VM of OpenJDK. As a result of our evaluation, we observed that the execution speed was faster than RBP by 23.0objects, and it was only 10.6which does not support orthogonal persistence. When a program used persistent objects, execution speed was almost the same as RBP. These results demonstrate that orthogonal persistence using NVM can be implemented in a practical way.

Non-volatile memory (NVM) is attractive because it enables us to make in-memory data structures persistent without serialization overhead. To implement persistent data structures durable against crashes, periodic checkpointing in NVM has been well studied. A remarkable technique that takes advantage of both DRAM and NVM (i.e., hybrid memory) for periodic checkpointing is mirroring with epoch-based write-address tracking. Its straightforward adoption, however, results in user thread blocking to checkpoint data structures mirrored in DRAM into NVM, from which applications suffer in throughput and responsiveness. To resolve this problem, we incorporate epoch-based versioning into this mirroring technique. The proposed method enables us to delegate checkpointing of data structures mirrored in DRAM into NVM to dedicated background threads that do not block user threads. We develop a system based on our method and evaluate it through experiments with memcached. Our system achieved +13% better throughput than an existing synchronous counterpart and such responsiveness that more than 50% of the performance of the original memcached kept for any time window of 0.5 ms in 99.83% of the entire execution.

A growing number of libraries written in managed languages, such as Python and JavaScript, are bringing about new demand for a foreign language interface (FFI) between two managed languages. Such an FFI allows a host-language program to seamlessly call a library function written in a foreign language and exchange objects. It is often implemented by a user-level library but such implementation cannot reclaim cyclic garbage, or a group of objects with circular references, across the language boundary. This paper proposes Refgraph GC , which enables FFI implementation that can reclaim cyclic garbage. Refgraph GC coordinates the garbage collectors of two languages and it needs to modify the managed runtime of one language only. It does not modify that of the other language. This paper discusses the soundness and completeness of the proposed algorithm and also shows the results of the experiments with our implementation of FFI with Refgraph GC. This FFI allows a Ruby program to access a JavaScript library.

The emergence of non-volatile memory (NVM) presents opportunities for making in-memory data of application programs persistent at a small cost. An adequate abstraction is required for programming languages to be able to utilize NVM. Here, persistence by reachability is a suitable abstraction for managed languages. In this abstraction, all objects are volatile when they are created and become persistent later depending on their reachability from the predefined roots. The state-of-the-art in the implementations of persistence by reachability creates objects in DRAM and moves them to NVM when they become persistent. This implementation has two inefficiencies. One is the read barriers to get the current location of objects; the other is to read values of persistent objects from NVM, which is slower than DRAM.

Jonkers's threaded compaction is attractive in the context of memory-constrained embedded systems because of its space efficiency. However, it cannot be applied to a heap where ordinary objects and meta-objects are intermingled for the following reason. It requires the object layout information, which is often stored in meta-objects, to update pointer fields inside objects correctly. Because Jonkers's threaded compaction reverses pointer directions during garbage collection (GC), it cannot follow the pointers to obtain the object layout. This paper proposes Fusuma, a double-ended threaded compaction that allows ordinary objects and meta-objects to be allocated in the same heap. Its key idea is to segregate ordinary objects at one end of the monolithic heap and meta-objects at the other to make it possible to separate the phases of threading pointers in ordinary objects and meta-objects. Much like Jonkers's threaded compaction, Fusuma does not require any additional space for each object. We implemented it in eJSVM, a JavaScript virtual machine for embedded systems, and compared its performance with eJSVM using mark-sweep GC. As a result, compaction enabled an IoT-oriented benchmark program to run in a 28-KiB heap, which is 20 KiB smaller than mark-sweep GC. We also confirmed that the GC overhead of Fusuma was less than 2.50x that of mark-sweep GC.

Constructing a high-performance garbage collector is hard. Constructing a fully concurrent ‘on-the-fly’ compacting collector is much more so. We describe our experience of implementing the Sapphire algorithm as the first on-the-fly, parallel, replication copying, garbage collector for the Jikes RVM Java virtual machine (JVM). In part, we explain our innovations such as copying with hardware and software transactions, on-the-fly management of Java’s reference types, and simple, yet correct, lock-free management of volatile fields in a replicating collector. We fully evaluate, for the first time, and using realistic benchmarks, Sapphire’s performance and suitability as a low latency collector. An important contribution of this work is a detailed description of our experience of building an on-the-fly copying collector for a complete JVM with some assurance that it is correct. A key aspect of this is model checking of critical components of this complicated and highly concurrent system.

Modern concurrent copying garbage collection (GC), in particular, real-time GC, uses fine-grained synchronizations with a mutator, which is the application program that mutates memory, when it moves objects in its copy phase. It resolves a data race using a concurrent copying protocol, which is implemented as interactions between the collector threads and the read and write barriers that the mutator threads execute. The behavioral effects of the concurrent copying protocol rely on the memory model of the CPUs and the programming languages in which the GC is implemented. It is difficult, however, to formally investigate the behavioral properties of concurrent copying protocols against various memory models. To address this problem, we studied the feasibility of the bounded model checking of concurrent copying protocols with memory models. We investigated a correctness-related behavioral property of copying protocols of various concurrent copying GC algorithms, including real-time GC Stopless, Clover, Chicken, Staccato, and Schism against six memory models, total store ordering (TSO), partial store ordering (PSO), relaxed memory ordering (RMO), and their variants, in addition to sequential consistency (SC) using bounded model checking. For each combination of a protocol and memory model, we conducted model checking with a model of a mutator. In this wide range of case studies, we found faults in two GC algorithms, one of which is relevant to the memory model. We fixed these faults with the great help of counterexamples. We also modified some protocols so that they work under some memory models weaker than those for which the original protocols were designed, and checked them using model checking. We believe that bounded model checking is a feasible approach to investigate behavioral properties of concurrent copying protocols under weak memory models.

Intel's latest processor microarchitecture, Haswell, adds support for a restricted form of transactional memory to the x86 programming model. We explore how this can be applied to three garbage collection scenarios in Jikes RVM: parallel copying, concurrent copying and bitmap marking. We demonstrate gains in concurrent copying speed over traditional synchronisation mechanisms of 48-101%. We also show how similar but portable performance gains can be achieved through software transactional memory techniques. We identify the architectural overhead of capturing sufficient work for transactional execution as a major stumbling block to the effective use of transactions in the other scenarios.

Most proposals for on-the-fly garbage collection ignore the question of Java's weak and other reference types. However, we show that reference types are heavily used in DaCapo benchmarks. Of the few collectors that do address this issue, most block mutators, either globally or individually, while processing reference types. We introduce a new framework for processing reference types on-the-fly in Jikes RVM. Our framework supports both insertion and deletion write barriers. We have model checked our algorithm and incorporated it in our new implementation of the Sapphire on-the-fly collector. Using a deletion barrier, we process references while mutators are running in less than three times the time that previous approaches take while mutators are halted; our overall execution times are no worse, and often better.

Mark-compact garbage collection helps long-running programs avoid fragmentation. The Lisp2 mark-compact collector is a classic but still widely-used compaction algorithm. It sequentially scans the entire heap to compact all live objects at one end of the heap while preserving their order of addresses. Since the heap is generally large, this scanning takes a long time. Although some collectors adopt a separate bitmap into which mark bits of objects are stored to reduce the scanning time, we observed that scanning the bitmap can take longer than scanning the heap if objects are densely located. We propose a new scanning method from this observation, which adaptively alternates methods of scanning depending on heap usage; it scans those parts of the heap where live objects are densely located whereas it scans the bitmap for the remaining parts. We implemented this scanning method in the Lisp2 collector of Jikes RVM.

The growing complexity of underlying systems such as memory hierarchies and speculation mechanisms are making it difficult to perform proper performance evaluations. This is a serious problem especially when we want to know the overheads of adding new functionality to existing languages (or systems/applications), or to know small changes in performance caused by small changes to programs. A problem is that equivalent executable programs, which only differ in their instruction addresses (code placement), often exhibit significantly different performance. This difference can be explained by the fact that code placement affects the underlying branch predictors and instruction cache subsystems. By taking into account such code placement effects, this paper proposes a proper evaluation scheme that cancels accidental factors in code placement by statistically summarizing the performance of a sufficient number of artificial programs that differ from the evaluation target program (almost) only in their code placement. We developed a system, called Code Shaker, that supports performance evaluations based on the proposed scheme.

To rewrite a sequential program into a concurrent one, the programmer has to enforce atomic execution of a sequence of accesses to shared memory to avoid unexpected inconsistency. There are two means of enforcing this atomicity: one is the use of lock-based synchronization and the other is the use of software transactional memory (STM). However, it is difficult to predict which one is more suitable for an application than the other without trying both mechanisms because their performance heavily depends on the application. We have developed a system named SAW that decouples the synchronization mechanism from the application logic of a Java program and enables the programmer to statically select a suitable synchronization mechanism from a lock or an STM. We introduce annotations to specify critical sections and shared objects. In accordance with the annotated source program and the programmer's choice of a synchronization mechanism, SAW generates aspects representing the synchronization processing. By comparing the rewriting cost using SAW and that using individual synchronization mechanism directly, we show that SAW relieves the programmer's burden. Through several benchmarks, we demonstrate that SAW is an effective way of switching synchronization mechanisms according to the characteristics of each application.

We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem of fragmentation in allocating objects larger than the page size. We solve this problem by using the replication-based incremental compaction. The compactor evacuates all objects in one area, the evacuation area, of the heap, thereby creating a large chunk of free space. We developed an algorithm for choosing the evacuation area that effectively cures fragmentation. The compactor does not use any read-barriers. Instead, it uses a technique similar to the replication-based incremental copying collection. This needs forwarding pointers for all evacuated objects. Rather than introducing an extra field for each object, we use a hash table to store forwarding pointers.

Our society depend on embedded and ubiquitous computing and the reliability of embedded software becomes more and more important. We have conducted a five years project with industries to develop software for realizing highly reliable embedded systems. We have tackled reliability issues from the following aspects. (1)Design environment: we have developed a UML design verification tool that apply model checking techniques to improve the design quality of application software. (2)Operating environment: we have developed operating system supports that realize multiple execution of real-time operating systems and also developed operating systems with enhanced resource management. Both technologies contribute the realization of robust run-time environment. (3) Real-time environment: we have developed real-time garbage collection techniques for Jave. They prevent the suspension of applications that violates the correct behavior of real-time applications. Also, they reduce the effort of application programmers to avoid garbage-collection during important execution timing. We have obtained fruitful results from these three research themes, and some of them are actually used in industries. Furthermore, we have integrated the results to make synergetic effect of them. In order to demonstrate the effectiveness, we have conduct an experiment. In this paper, we introduce the project and its results.

We propose an incremental compaction algorithm. Our compactor selects a continuous area of the heap and evacuates it by incrementally copying all objects in the area to the rest of the heap. After all objects have been copied, our compactor incrementally updates pointers pointing into the evacuated area. During these processes, each original object and its copy are kept consistent. We implemented the compactor together with a snapshot garbage collector in the KVM. Our measurements show that (1) the largest free chunk is almost always more than 20% as large as the entire heap when the heap is twice as large as the maximum amount of live objects, (2) the runtime overhead is less than 20%, and (3) the maximum pause time caused by the compactor is comparable to that caused by the snapshot collector.