Collecting cyclic distributed garbage by controlled migration

Summary.  Distributed systems with a large number of nodes use internode reference counting for timely and fault-tolerant garbage collection. However, this fails to collect cyclic garbage distributed across nodes. One fix is to migrate all objects on a garbage cycle to a single node, where they can be collected by the tracing-based local collector. Existing proposals based on this technique have practical problems due to unnecessary migration of objects. We propose a scheme that avoids migration of live objects, batches objects to avoid a cascade of migration messages, and short-cuts the migration path to avoid multiple migrations. We use simple estimates to detect objects that are highly likely to be cyclic garbage and to select a node to which such objects are migrated. The scheme collects all distributed cyclic garbage, has low overhead, and preserves the decentralized and fault-tolerant nature of distributed reference counting and migration. Received: August 1995 / Accepted: August 1996     

An efficient approach to cyclic reference counting based on a coarse-grained search

Reference counting is known to have problems working with cyclic structures. In this paper, we present an efficient approach to cyclic reference counting, consisting of two key components. The first is a coarse-grained cycle collection algorithm that essentially performs a coarser (lightweight) analysis of the computation graph and thus greatly reduces the tracing cost (in comparison with the algorithms based on trial deletion to detect cycles). Our new cycle collector relies on this algorithm to obtain efficiency. Second, a predefined backup algorithm is incorporated to eliminate a theoretical problem that appears in the coarse-grained algorithm, thereby making the collector more practical. In this regard, we develop a heuristic based on the runtime behavior of the cycle collection to help the collector determine when to trigger the backup one. We have implemented and evaluated the proposed cycle collector on the Jikes RVM, where the SPECjvm98 benchmarks were applied. The results demonstrate that the novel approach is efficient and practical, compared to a modern cycle collector based on trial deletion.     

Yama: a scalable generational garbage collector for Java in multiprocessor systems

The current state-of-the-art generational garbage collector pauses all the program threads when it performs young and old generation garbage collection. As the number of program threads increases, the delay due to garbage collection also increases, thus restricting the scalability of the collector. In order to improve the scalability and reduce the pause time, an on-the-fly generational garbage collector called Yama is proposed for multiprocessor systems. This uses the on-the-fly deferred reference counting in the young generation and the DLG (Doligez Leroy Gonthier) on-the-fly mark and sweep garbage collector in the old generation. We have proposed and experimented with two novel variations of the on-the-fly deferred reference counting called Chitragupt1 and Chitragupt2 in the young generation. Yama does not pause all the application threads simultaneously. An adaptive tenuring policy based on object reference count and survival rate is also proposed. Yama has been implemented in the IBM Jikes RVM (research virtual machine). The above claims are supported with experimental results for standard benchmark programs. The results show that Yama has an extremely low pause time in both the young and the old generation. The pause time reduction results in better response times for the user programs.     

An efficient approach to cyclic reference counting based on a coarse-grained search

Reference counting is known to have problems working with cyclic structures. In this paper, we present an efficient approach to cyclic reference counting, consisting of two key components. The first is a coarse-grained cycle collection algorithm that essentially performs a coarser (lightweight) analysis of the computation graph and thus greatly reduces the tracing cost (in comparison with the algorithms based on trial deletion to detect cycles). Our new cycle collector relies on this algorithm to obtain efficiency. Second, a predefined backup algorithm is incorporated to eliminate a theoretical problem that appears in the coarse-grained algorithm, thereby making the collector more practical. In this regard, we develop a heuristic based on the runtime behavior of the cycle collection to help the collector determine when to trigger the backup one. We have implemented and evaluated the proposed cycle collector on the Jikes RVM, where the SPECjvm98 benchmarks were applied. The results demonstrate that the novel approach is efficient and practical, compared to a modern cycle collector based on trial deletion.     

Cyclic reference counting by typed reference fields

Reference counting strategy is a natural choice for real-time garbage collection, but the cycle collection phase which is required to ensure the correctness for reference counting algorithms can introduce heavy scanning overheads. This degrades the efficiency and inflates the pause time required for garbage collection. In this paper, we present two schemes to improve the efficiency of reference counting algorithms. First, in order to make better use of the semantics of a given program, we introduce a novel classification model to predict the behavior of objects precisely. Second, in order to reduce the scanning overheads, we propose an enhancement for cyclic reference counting algorithms by utilizing strongly-typed reference features of the Java language. We implement our proposed algorithm in Jikes RVM and measure the performance over various Java benchmarks. Our results show that the number of scanned objects can be reduced by an average of 37.9% during cycle collection phase.     

A generational and conservative copying collector for hybrid object-oriented languages

A copying collector has two excellent properties: it compacts the heap, and the execution time depends solely on the number of live objects. Use of a copying collector is thought by some to be a more efficient way of managing the heap than explicit freeing of objects. This paper describes a high-performance copying collector for a hybrid object-oriented language. The collector is both conservative and generational. It relies on the overlying compiler to identify most true pointers, and on the underlying operating system to detect pointers to younger generations. The implementation described here uses a modified version of the compiler for a C-based object-oriented language, and the Mach operating system. The performance results have confirmed the author's expectation: the collector has been faster than explicit freeing.     

A mostly‐copying collector component for class templates

Class templates represent a difficulty for C++ garbage collectors since relevant information is available only very late, at instantiation time. Current collectors therefore either fail to work with class templates or have to run in a non‐optimized mode. This paper introduces the template garbage collector (TGC), the first mostly‐copying collector that can handle class templates. It discusses the design decisions that are suggested by the specifics of generic template programming and presents performance results and memory measurements of tests with MTL and GTL, two generic C++ libraries based on the Standard Template Library. The tests show that TGC substantially improves the run times of programs with many small objects with short lifetimes or large objects with long lifetimes. The memory usage at the same time is reasonable. Since TGC modifies the mostly‐copying technique, the heap sizes are in many cases considerably smaller than they are for traditional mostly‐copying collectors. The tests also show that TGC is competitive with the Boehm–Demers–Weiser collector, the most widely used collector for C++. Copyright © 2001 John Wiley & Sons, Ltd.     

Detecting memory leaks in managed languages with Cork

A memory leak in a managed language occurs when the program inadvertently maintains references to objects that it no longer needs. Memory leaks cause systematic heap growth that degrade performance and can result in program crashes after perhaps days or weeks of execution. Prior approaches for detecting memory leaks rely on heap differencing or detailed object statistics which store state proportional to the number of objects in the heap. These overheads preclude their use on the same processor for deployed long‐running applications. This paper introduces Cork as a tool that accurately identifies heap growth caused by leaks. It is space efficient (adding less than 1% to the heap) and time efficient (adding 2.3% on average to total execution time). We implement this approach of examining and summarizing the class of live objects during garbage collection in a class points‐from graph (CPFG). Each node in the CPFG represents a class and edges between nodes represent references between objects of the specific classes. Cork annotates nodes and edges with the corresponding volume of live objects. Cork identifies growing data structures across multiple collections and computes a class slice to identify leaks for the user. We experiment with two functions for identifying growth and show that Cork is accurate: it identifies systematic heap growth with no false positives in 4 of 15 benchmarks we tested. Cork's slice report enabled us to quickly identify and eliminate growing data structures in large and unfamiliar programs, something their developers had not previously done. Copyright © 2009 John Wiley & Sons, Ltd.     

Efficiently Adapting Java Binaries in Limited Memory Contexts

This paper presents a compilation framework that allows executable code to be shared across different Java Virtual Machine (JVM) instances. Current compliant JVMs for servers are burdened with large memory footprints (because of the size of the increasingly complicated compilers) and high startup costs, while compliant JVMs for embedded devices typically rely on interpretation. This paper describes a quasi-static approach that allows execution of a read-only version of the code, enabling compiled Java binaries to be embedded in ROM in an embedded environment or shared across multiple applications in a server environment. We have implemented this approach in the Quicksilver quasi-static compiler for the Jikes RVM (Jikes Research Virtual Machine). On the SPECjvm98 benchmark suite, our approach gives writable memory space savings of between 82–89% over that of our previous (non-sharable, non-ROMable) quasi-static approach, while delivering performance that is typically within 1–7% of that approach, and is competitive with the performance of the Jikes RVM adaptive optimization system.     

Compacting Garbage Collection can be Fast and Simple

Copying garbage collectors are now standard for the memory-management subsystems of functional and object-oriented programming languages. Compacting garbage collection has correspondingly fallen out of favor. We revitalize the case for compaction by demonstrating that a simple compacting collector, extended with the generational garbage collection heuristic, exhibits performance as effectively as or better than a well-designed generational copying collector on real programs running in real environments. The observation that compaction preserves allocation order across collections leads to a new generalization of the generational heuristic that reduces the movement of long-lived objects. We measure the effect of substituting our compacting generational collector for a copying collector in Standard ML of New Jersey.     

Dynamic analysis of Java program concepts for visualization and profiling

Concept assignment identifies units of source code that are functionally related, even if this is not apparent from a syntactic point of view. Until now, the results of concept assignment have only been used for static analysis, mostly of program source code. This paper investigates the possibility of using concept information within a framework for dynamic analysis of programs. The paper presents two case studies involving a small Java program used in a previous research exercise, and a large Java virtual machine (the popular Jikes RVM system). These studies investigate two applications of dynamic concept information: visualization and profiling. The paper demonstrates two different styles of concept visualization, which show the proportion of overall time spent in each concept and the sequence of concept execution, respectively. The profiling study concerns the interaction between runtime compilation and garbage collection in Jikes RVM. For some benchmark cases, we are able to obtain a significant reduction in garbage collection time. We discuss how this phenomenon might be harnessed to optimize the scheduling of garbage collection in Jikes RVM.     

Nonintrusive Cloning Garbage Collection with Stock Operating System Support

It is well accepted that automatic garbage collection simplifies programming, promotes modularity, and reduces development effort. However it is commonly believed that these advantages do not counteract the perceived price: excessive overheads, possible long pause times while garbage collections occur, and the need to modify existing code. Even though there are publically available garbage collector implementations that can be used in existing programs, they do not guarantee short pauses, and some modification of the application using them is still required. In this paper we describe a snapshot-at-beginning concurrent garbage collector algorithm and its implementation. This algorithm guarantees short pauses, and can be easily implemented on stock UNIX-like operating systems. Our results show that our collector performs comparable to other garbage collection implementations on uniprocessor machines and outperforms similar collectors on multiprocessor machines. We also show our collector to be competitive in performance with explicit deallocation. Our collector has the added advantage of being non-intrusive. Using a dynamic linking technique and effective root set inferencing, we have been able to successfully run our collector even in commercial programs where only the binary executable and no source code is available. In this paper we describe our algorithm, its implementation, and provide both an algorithmic and a performance comparison between our collector and other similar garbage collectors. ©1997 by John Wiley & Sons, Ltd.     

Jikes RVM动态编译技术分析与性能评测

随着Java语言的广泛应用,Java虚拟机的性能越来越受到人们重视,而虚拟机的动态编译技术是影响其性能的重要因素.Jikes RVM使用Java语言实现了一个Java虚拟机.首先分析了Jikes RVM的3个主要动态编译器的结构及其涉及的关键编译技术,包括基线编译、优化编译和自适应编译,然后利用SPECjvm Client98对Jikes RVM和Sun JVM的动态编译性能进行了测试和比较.测试结果显示,Jikes RVM的性能和Sun JVM性能基本相同,最后针对Jikes RVM的不足提出了改进Jikes RVM 编译器的方法.     

A customisable memory management framework for C++

Automatic garbage collection relieves programmers from the burden of managing memory themselves and several techniques have been developed that make garbage collection feasible in many situations, including real time applications or within traditional programming languages. However, optimal performance cannot always be achieved by a uniform general purpose solution. Sometimes an algorithm exhibits a predictable pattern of memory usage that could be better handled specifically, delaying as much as possible the intervention of the general purpose collector. This leads to the requirement for algorithm specific customisation of the collector strategies. We present a dynamic memory management framework which can be customised to the needs of an algorithm, while preserving the convenience of automatic collection in the normal case. The Customisable Memory Manager (CMM) organises memory in multiple heaps. Each heap is an instance of C++ class which abstracts and encapsulates a particular storage discipline. The default heap for collectable objects uses the technique of mostly copying garbage collection, providing good performance and memory compaction. Customisation of the collector is achieved exploiting object orientation by defining specialised versions of the collector methods for each heap class. The object-oriented interface to the collector enables coexistence and coordination among the various collectors as well as integration with traditional code unaware of garbage collection. The CMM is implemented in C++ without any special support in the language or the compiler. The techniques used in the CMM are general enough to be applicable also to other languages. The performance of the CMM is analysed and compared to other conservative collectors for C/C++ in various configurations. © 1998 John Wiley & Sons, Ltd.     

Selective sweeping

Traditional mark and sweep garbage collectors use time proportional to the heap size when sweeping memory, since all objects in the heap, dead or alive, must be traversed. Here we introduce a sweeping algorithm which traverses only the live objects. Since this sweeping algorithm is slower when the heap occupancy is high, we also discuss how to avoid this slowdown by using an adaptive algorithm. Copyright © 2004 John Wiley & Sons, Ltd.     

即时编译器辅助的垃圾收集中的插桩算法研究

即时编译器辅助的垃圾收集技术结合显式和自动内存管理的优点,在编译阶段由即时编译器分析应用程序并在其中插桩显式释放内存的指令,以便垃圾收集器及时回收死亡对象所占用的内存空间,从而减轻垃圾收集器的负担.提出一种应用于该项技术的插桩算法,它基于控制流中的支配关系并提供不同的插桩策略,保证插桩的正确性和灵活性;它能够主动获得域引用从而释放对象及其域引用的内存空间.实验表明基于该插桩算法的垃圾收集器能够回收大量的内存空间,提高Java程序的执行效率.     

基于关键引用验证的分布式实时垃圾搜集器*

提出了一种新的分布式垃圾搜集器（GC）机制,即基于关键引用验证的分布式GC。性能分析说明,与以往的分布式GC相比,该算法能以最短的时间延迟回收循环垃圾。尽管该算法为保留引用列表和验证过程需要额外的一些存储空间,但具有一定的实时性和较好的容错性,综合性能较好,适用于大规模分布式系统。     

Memory leak detection in Plumbr

Platforms with automatic memory management, such as the JVM, are usually considered free of memory leaks. However, memory leaks can happen in such environments, as the garbage collector cannot free objects, which are not used by the application anymore, but are still referenced. Such unused objects can eventually fill up the heap and crash the application. Although this problem has been studied extensively, nevertheless, there are still many rooms for improvement in this area. This paper describes the statistical approach for memory leak detection, as an alternative, along with a commercial tool, Plumbr, which is based on the method. The tool is later analyzed with three case studies of real applications and in the process also analyzes strengths and weaknesses of the statistical approach for memory leak detection. Copyright © 2014 John Wiley & Sons, Ltd.     

基于Java实现移动Agent强迁移的方法

对比分析了常见的移动Agent强迁移与弱迁移,提出一种基于Java实现移动Agent强迁移的方法.该方法基于IBMJikesRvm(Jikes research virtual machine(RVM))提供的RVM,利用OSR(on-stack replacement)捕捉运行堆栈的状态,实现了移动Agent强迁移.该方法不需要对源代码或字节码进行预处理,也不需要改变JVNI,具有很好的系统扩展性.     

A performance perspective on the Active Memory System

One major problem of using Java in real-time and embedded devices is the non-deterministic turnaround time of dynamic memory management systems (memory allocation and garbage collection). For the allocation, the non-determinism is often contributed by the time to perform searching, splitting, and coalescing. For the garbage collection, the turnaround time is usually determined by the size of the heap, the number of live objects, the number of object collected, and the amount of garbage collected. Even with the current state-of-the-art garbage collectors (generational and incremental schemes), they may or may not guarantee the worst-case latency. Moreover, such schemes often prolong overall garbage collection time.

In this paper, the performance analysis of the proposed Active Memory Module (AMM) for embedded systems is presented. Unlike the software counterparts, the AMM can perform a memory allocation in a predictable and bounded fashion (14 cycles). Moreover, it can also yield a bounded sweeping time regardless of the number of live objects or heap size. By utilizing the proposed system, the overall speedup can be as high as 23% compared to the garbage collection system of the JDK 1.2.2 running in classic mode.