Memory Mangement in the PoSSo Solver

A uniform general purpose garbage collector may not always provide optimal performance. Sometimes an algorithm exhibits a predictable pattern of memory usage that could be exploited, delaying as much as possible the intervention of the collector. This requires a collector whose strategy can be customized to the need of an algorithm. We present a dynamic memory management framework which allows such customization, while preserving the convenience of automatic collection in the normal case. The Customizable Memory Management (CMM) organizes memory in multiple heaps, each one encapsulating a particular storage discipline. The default heap for collectable objects uses the technique of mostly copying garbage collection, providing good performance and memory compaction. Customization of the collector is achieved through object orientation by specialising the collector methods for each heap class. We describe how the CMM has been exploited in the implementation of the Buchberger algorithm, by using a special heap for temporary objects created during polynomial reduction. The solution drastically reduces the overall cost of memory allocation in the algorithm.     

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.     

Accurate garbage collection in uncooperative environments revisited

Implementing a concurrent programming language such as Java by means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces development time—as many low‐level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on a wide range of platforms. For garbage‐collected languages, however, they are not a perfect match as no support is provided for accurately discovering pointers to heap‐allocated data on thread stacks. We evaluate several previously published techniques and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java‐to‐C/C++ compiler using GCC as a back‐end compiler. Our extensive experimental results confirm that lazy pointer stacks outperform existing approaches: we provide a speedup of 4.5% over Henderson's accurate collector with a 17% increase in code size. Accurate collection is essential in the context of real‐time systems, we thus validate our approach with the implementation of a real‐time concurrent garbage collection algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

一种基于栈式分配的JVM垃圾收集算法①

为了减少Java虚拟机垃圾收集器的开销,对Java栈帧进行改造使其支持对象的存储,在此基础上提出一种基于栈式内存分配的垃圾收集算法。算法首先在编译阶段通过对Java源代码进行分析确定栈式分配对象,并用扩展指令标识这些对象,程序运行时它们直接被分配到Java栈上,这些对象在程序离开其作用域时立即被释放,其它对象则分配到堆上,由垃圾收集器进行回收。实验结果表明,与传统基于堆式的垃圾收集算法相比,新算法内存分配和即时回收性能优,占用内存空间少。垃圾回收更及时,减轻了垃圾收集器的负担,提高了运行速度。     

一种基于栈式分配的JVM垃圾收集算法①

为了减少Java虚拟机垃圾收集器的开销,对Java栈帧进行改造使其支持对象的存储,在此基础上提出一种基于栈式内存分配的垃圾收集算法。算法首先在编译阶段通过对Java源代码进行分析确定栈式分配对象,并用扩展指令标识这些对象,程序运行时它们直接被分配到Java栈上,这些对象在程序离开其作用域时立即被释放,其它对象则分配到堆上,由垃圾收集器进行回收。实验结果表明,与传统基于堆式的垃圾收集算法相比,新算法内存分配和即时回收性能优,占用内存空间少,垃圾回收更及时,减轻了垃圾收集器的负担,提高了运行速度。     

一种高效的垃圾收集器CCone

为提高堆空间的利用率,许多垃圾收集器在标记扫描对象后加入"压缩"过程,主要有"标记-压缩"和"拷贝"两类垃圾收集器.垃圾收集时需要暂停程序的运行,为了减少这种时间开销,基于"拷贝"算法,垃圾收集器CCone在一次堆遍历中完成压缩过程和引用更新过程,而现有的算法至少需要两遍.此外,CCone基于"拷贝"算法充分利用多核和多线程技术,以页为单位,利用多线程启动多个垃圾收集器对堆空间进行垃圾回收.性能测试表明并行的CCone相比较传统的压缩垃圾收集器在吞吐量上有超过10%的提升,而由算法带来的开销可以忽略不计.     

Reference count garbage collection

A garbage collection algorithm that permits a reference count storage reclamation scheme to collect circularly linked inaccessible structures is presented. The algorithm requires no additional information beyond that required by a reference count scheme. In particular, it does not require the garbage collector to be able to find pointers outside the heap. The algorithm is most useful for augmenting reference count storage reclamation systems and for implementing storage management systems on top of languages that do not provide their own. It is, however, considerably less efficient in space and time than conventional garbage collection systems.     

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.     

Object resizing and reclamation through the use of hardware bit-maps

The memory intensive nature of object-oriented languages such as C++ and Java has created the need of a high-performance dynamic memory management. Object-oriented applications often generate higher memory intensity in the heap region. Thus, high-performance memory manager is needed to cope with such applications. As today's VLSI technology advances, it becomes more and more attractive to map software algorithms such as malloc(), free(), realloc(), and garbage collection into hardware.

This paper presents hardware designs of realloc function and sweeping function (for mark and sweep garbage collection) that fully utilize the advantages of combinational logic. In our scheme, the reallocation on the original block can be done in constant time. If the reallocation on the original block is not possible, the previously proposed malloc() and free() can be used to move the contents to a new location. For the sweeping function, the bit-sweeper can detect and sweep the garbage in constant time. Since the sweeping phase often consumes more time than the marking phase, the garbage collection time can be substantially improved. The hardware complexity of proposed scheme (i.e. X-Unit, RS-unit, ESG-unit, and bit-sweeper) is O(n), where n represents the size of bit-map.     

Garbage collection alternatives for icon

Copying garbage collectors are becoming the collectors of choice for very high-level languages and for functional and object-oriented languages. Copying collectors are particularly efficient for large storage regions because their execution time is proportional only to the amount of accessible data, and they identify and compact this data in one pass. In contrast, mark-and-sweep collectors execute in time proportional to the memory size and compacting collectors require another pass to compact accessible data. The performance of existing systems with old compacting mark-and-sweep collectors might be improved by replacing their collectors with copying collectors. This paper explores this possibility by describing the results of replacing the compacting mark-and-sweep collector in the Icon programming language with four alternative collectors, three of which are copying collectors. Copying collectors do indeed run faster than the original collector, but at a significant cost in space. An improved variant of the compacting mark-and-sweep collector ran even faster and used little additional space.     

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.     

Garbage collection in an uncooperative environment

We describe a technique for storage allocation and garbage collection in the absence of significant co-operation from the code using the allocator. This limits garbage collection overhead to the time actually required for garbage collection. In particular, application programs that rarely or never make use of the collector no longer encounter a substantial performance penalty. This approach greatly simplifies the implementation of languages supporting garbage collection. It further allows conventional compilers to be used with a garbage collector, either as the primary means of storage reclamation, or as a debugging tool. Our approach has two potential disadvantages. First, some garbage may fail to be reclaimed. Secondly, we use a ‘stop and collect’ approach, thus making the strategy unsuitable for applications with severe real-time constraints. We argue that the first problem is, to some extent, inherent in any garbage collection system. Furthermore, based on our experience, it is usually not significant in practice. In spite of the second problem, we have had favourable experiences with interactive applications, including some that use a heap of several megabytes.     

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.     

Evaluation of parallel copying garbage collection on ashared-memory multiprocessor

A parallel copying garbage collection algorithm for symbolic languages executing on shared-memory multiprocessors is proposed. The algorithm is an extension of Baker's sequential algorithm with a novel method of heap allocation to prevent fragmentation and facilitate load distribution during garbage collection. An implementation of the algorithm within a concurrent logic programming system, VPIM, has been evaluated and the results, for a wide selection of benchmarks, are analyzed here. The authors show 1) how much the algorithm reduces the contention for critical sections during garbage collection, 2) how well the load-balancing strategy works and its expected overheads, and 3) the expected speedup achieved by the algorithm     

A semi-incremental garbage collection algorithm

Lisp is restricted in application because of d the unpredictable delays introduced by garbage collection. Incremental garbage collectors eliminate the delays, but are less efficient overall. We present a semi-incremental algorithm that reduces the delays and is, moreover more efficient than the mark-scan algorithm from which it is derived. The mark-scan algorithm is explained it consists of a mark phase followed by a sweep phase. The sweep phase can be performed incrementally, but the mark phase cannot. If this modification is made, our semi-incremental algorithm is derived. Using the new algorithm the delay on garbage collection is proportional to the amount of heap actually in use, not the size of the heap. Allocating a cell takes a variable amount of time, depending on the proportion of the heap in use. Comparing the number of operations in the old and new algorithms, we see that the new algorithm is more efficient. The new algorithm was used as part of a Lisp implementation on an LSI-11/03 and found to behave well.     

Research Demonstration of a Hardware Reference-Counting Heap

A hardware self-managing heap memory (RCM) for languages like Lisp, Smalltalk, and Java has been designed, built, tested and benchmarked. On every pointer write from the processor, reference-counting transactions are performed in real time within this memory, and garbage cells are reused without processor cycles. A processor allocates new nodes simply by reading from a distinguished location in its address space. The memory hardware also incorporates support for off-line, multiprocessing, mark-sweep garbage collection.Performance statistics are presented from a partial implementation of Scheme over five different memory models and two garbage collection strategies, from main memory (no access to RCM) to a fully operational RCM installed on an external bus. The performance of the RCM memory is more than competitive with main memory.     

实时性环境中JVM垃圾收集算法

提出一种适用于实时性环境的Java虚拟机垃圾收集算法。该算法通过对增量式收集器中堆空间划分方式和引用跟踪进行改进,以减少垃圾收集时带来的不确定性暂停,并且该算法可以指定用户在一个时间段内进行垃圾收集,以便使应用程序暂停时间达到最短,从而适用于实时性环境。实验结果表明,该算法能有效减少垃圾收集时暂停的频率和时长。     

Java垃圾回收新算法刍探

由Java语言与C/C++对象在内存管理方式的不同,引出了Java语言的优势技术--垃圾处理技术.通过对GC工作原理的阐述及对一些传统的垃圾收集器的分析,提出了一种新的垃圾处理算法,一定程度上改善和提高了Java垃圾处理的性能.     

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.     

一种改进的增量式JVM垃圾收集算法

非增量式Java虚拟机(JVM)垃圾回收算法的内存开销较大。为此,提出一种基于栈式分配策略的JVM增量式垃圾收集算法。对Java栈帧进行改造使其支持存储对象,改进增量式收集器中堆空间的划分、引用跟踪方式,以减少垃圾收集带来的不确定性暂停。实验结果表明,该算法能有效减少暂停的频率和时长,提高运行速度。