Lazy garbage collection

This paper describes a variation on the reference count method of garbage collection which can be particularly effective for the implemention of modern, truly functional languages. This method gives a high degree of control over the collection process and an increase in efficiency for many systems, particularly those with small, fast memories local to the central processor, such as a stack or an addressable cache.     

On-the-fly garbage collection for several mutators

Summary An algorithm is given for on-the-fly garbage collection in the presence of several mutators. It uses two colours and is a generalization of Ben-Ari's algorithm (1984). The correctness proof is based on the lexical orderings of several tuples of state space functions. It is shown that in a certain sense the algorithm is optimal. Three variations of the algorithm are given and proved correct. In the case that there is only one mutator one of these variations closely resembles a well-known incorrect algorithm. Jan E. Jonker was born in 1943. He received his Master's degree in Theoretical Physics in 1968 and his Master's degree in Computing Science in 1989, both from the University of Groningen. From 1968 until 1976 he did research on the electronic structure of dilute impurities in iron. From 1976 until 1989 he did research on the medical aspects of road accidents. Currently, he is assistant professor at the University of Groningen. His main research interests are programming methodology, parallel computations and delay-insensitive circuit design.     

Simple generational garbage collection and fast allocation

Generational garbage collection algorithms achieve efficiency because newer records point to older records; the only way an older record can point to a newer record is by a store operation to a previously created record, and such operations are rare in many languages. A garbage collector that concentrates just on recently allocated records can take advantage of this fact. Such a garbage collector can be so efficient that the allocation of records costs more than their disposal. A scheme for quick record allocation attacks this bottleneck. Many garbage-collected environments do not know when to ask the operating system for more memory. A robust heuristic solves this problem. This paper presents a simple, efficient, low-overhead version of generational garbage collection with fast allocation, suitable for implementation in a Unix environment.     

An incremental garbage collection algorithm for multi-mutator systems

An elementary correctness proof for Ben-Ari's algorithm (1984) for incremental garbage collection is given. We give a new algorithm for systems in which there are multiple mutators and a proof of its correctness, which is a minor modification of the previous proof. Finally, we remark upon a way to implement these algorithms that may increase their performance on certain architectures. Carl Pixley holds B.S., M.S. and Ph.D. degrees in mathematics from the University of Omaha, Rutgers-The State University, and the State University of New York at Binghamton, respectively. His principal contributions are the Pixley-Roy construction of set-theoretic topology, a example in the selection theory of infinite-dimensional spaces, a decomposition theorem (with W. Eaton) in geometric topology, and the design and implementation of demanddriven arithmetic in a functional programming language. He is now a member of the technical staff of the VLSI Computer Aided Design Program of Microelectronics and Computer Technology Corporation (MCC) in Austin Texas, where he is investigating mathematical methods in the verification of hardware.     

The measured cost of conservative garbage collection

Because dynamic memory management is an important part of a large class of computer programs, high-performance algorithms for dynamic memory management have been, and will continue to be, of considerable interest. Experience indicates that for many programs, dynamic storage allocation is so important that programmers feel compelled to write and use their own domain-specific allocators to avoid the overhead of system libraries. As an alternative to explicit storage management techniques, conservative garbage collection has been suggested as an important algorithm for dynamic storage management in C programs. In this paper, I evaluate the costs of different dynamic storage management algorithms, including domain-specific allocators, widely-used general-purpose allocators, and a publicly available conservative garbage collection algorithm. Surprisingly, I find that programmer enhancements often have little effect on program performance. I also find that the true cost of conservative garbage collection is not the CPU overhead, but the memory system overhead of the algorithm. I conclude that conservative garbage collection is a promising alternative to explicit storage management and that the performance of conservative collection is likely to improve in the future. C programmers should now seriously consider using conservative garbage collection instead of explicitly calling free in programs they write.     

A garbage collection algorithm for shared memory parallel processors

This paper describes a technique for adapting the Morris sliding garbage collection algorithm to execute on parallel machines with shared memory. The algorithm is described within the framework of an implementation of the parallel logic language Parlog. However, the algorithm is a general one and can easily be adapted to parallel Prolog systems and to other languages. The performance of the algorithm executing a few simple Parlog benchmarks is analyzed. Finally, it is shown how the technique for parallelizing the sequential algorithm can be adapted for a semi-space copying algorithm.     

Global garbage collection for distributed heap storage systems

We present a garbage-collection algorithm, suitable for loosely-coupled multiprocessor systems, in which the processing elements (PEs) share only the communication medium. The algorithm is global, i.e., it involves all the PEs in the system. It allows space compaction, and it uses a system-wide marking phase to mark all accessible objects where a combination of parallel breadth-first/depth-first strategies is used for tracing the object-graphs according to a decentralized credit mechanism that regulates the number of garbage collection messages in the system. The credit mechanism is crucial for determining the space requirement of the garbage-collection messages. Also a variation of this algorithm is presented for systems with high locality of reference. It allows each PE to perform first its local garbage collection and only invokes the global garbage collection when the freed space by the local collector is insufficient.     

FeGC: An efficient garbage collection scheme for flash memory based storage systems

NAND flash memory is a promising storage media that provides low-power consumption, high density, high performance, and shock resistance. Due to these versatile features, NAND flash memory is anticipated to be used as storage in enterprise-scale systems as well as small embedded devices. However, unlike traditional hard disks, flash memory should perform garbage collection that consists of a series of erase operations. The erase operation is time-consuming and it usually degrades the performance of storage systems seriously. Moreover, the number of erase operations allowed to each flash memory block is limited. This paper presents a new garbage collection scheme for flash memory based storage systems that focuses on reducing garbage collection overhead, and improving the endurance of flash memory. The scheme also reduces the energy consumption of storage systems significantly. Trace-driven simulations show that the proposed scheme performs better than various existing garbage collection schemes in terms of the garbage collection time, the number of erase operations, the energy consumption, and the endurance of flash memory.     

Performance of garbage collection algorithms for flash-based solid state drives with hot/cold data

To avoid a poor random write performance, flash-based solid state drives typically rely on an internal log-structure. This log-structure reduces the write amplification and thereby improves the write throughput and extends the drive’s lifespan. In this paper, we analyze the performance of the log-structure combined with the d$d$-choices garbage collection algorithm, which repeatedly selects the block with the fewest number of valid pages out of a set of d$d$ randomly chosen blocks, and consider non-uniform random write workloads. Using a mean field model, we show that the write amplification worsens as the hot data gets hotter.     

A simple generational real-time garbage collection scheme

This paper presents and empirically evaluates a generational real-time garbage collection scheme, which is based on combining Baker’s real-time scheme with a simple generational scheme by Andrew W. Appel. Real World Computing Partnership. Khayri A. M. Ali, Ph.D.: He currently works as Dean of the Faculty of Computer Science at October University for Modern Sciences and Arts, Egypt. He received his B. Sc. (1970) in Electronics, his M. Sc. (1977) in Automatic Control, both from Egypt. He received his Ph.D. in Computer Systems from the Royal Institute of Technology, Stockholm, in 1984. His research interests are in developing parallel and distributed logic, functional, object-oriented, and constraints programming systems.     

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.     

Storage management for an implementation of SNOBOL4

The implementation of the SNOBOL4 programming language requires some scheme for dynamic allocation and reclamation of storage. This paper describes the method used in a machine-dependent implementation of SNOBOL4 called SITBOL. Available storage is divided into two regions: one for the allocation of storage for permanent or immovable objects and one for objects that are subject to reclamation. Reclamation is accomplished by a four-phase algorithm, which includes marking, address adjustment and compaction. The reclamation process is supplemented by several heuristics that reduce the cost of reclamation and increase the amount of storage reclaimed. The storage overhead of the technique is analysed and compared with an alternate method. Some empirical measurements of actual SNOBOL4 programs are given that substantiate the results of the analysis.     

全程优化的固态硬盘垃圾回收方法

由于NAND闪存的固有限制,写前擦除和擦除粒度较大,基于NAND Flash的固态硬盘（SSD）需要执行垃圾回收以重用失效页。然而垃圾回收带来的高开销会显著降低SSD的性能,也会直接影响SSD的寿命。特别是对于频繁使用的有数据碎片的SSD,垃圾回收带来的性能下降问题将更为严重,现有的垃圾回收（GC）算法各自侧重垃圾回收操作的某个步骤,并没有给出全面考虑各步骤对整体影响的综合方案。针对该问题,在详细剖析垃圾回收过程的基础上,提出了一种全程优化的垃圾回收方法WPO-GC,在数据初始放置、垃圾回收目标块的选择、有效数据的迁移、触发回收的时间点以及中断处理方式上,尽可能全面地考虑各步骤对SSD正常读写请求和寿命的影响。通过开源模拟器SSDsim上的WPO-GC的有效性验证表明,同典型GC算法相比,WPO-GC可以减少SSD读请求延迟20%~40%和写请求延迟17%~40%,均衡磨损近30%。     

Implementation and analysis of compile-time gargage collection

We have proposed a method to detect the generation of garbage cells, by analyzing a source text of functional programming languages.¹⁵⁾ The garbage cells whose generation is expected are reclaimed immediately with very little overhead at the execution time. We call this methodcompile-time GC. To investigate the effects of the compile-time GC, an experimental LISP interpreter has been implemented, and several sample programs are executed. We knew that for most programs, many of the garbage cells are detected and reclaimed by the compile-time GC. Programming techniques to improve the reclaimability are also studied.     

Fixing some space leaks with a garbage collector

Some functional programs may use more space than would be expected. A modification to the garbage collector is suggested which solves this problem in some cases. Related work is discussed.     

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.