350 papers · page 15 of 18
Garbage collection for a multi-threaded program typically involves either stopping all threads while doing the collection or involves copious amounts of synchronization between threads. However, a lot of data is only ever visible to a single thread, and such data should ideally b…
Analytical models of memory object lifetimes are appealing because having them would enable mathematical analysis or fast simulation of the memory management behavior of programs. In this paper, we investigate models for object lifetimes drawn from programs in object-oriented lan…
Garbage collection tables for finding pointers on the stack can be represented in 20-25% of the space previously reported. Live pointer information is often the same at many call sites because there are few pointers live across most call sites. This allows live pointer informatio…
We consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive implementation may cause excessive and wasteful scanning of the cards and thus increase th…
The cost of accessing main memory is increasing. Machine designers have tried to mitigate the consequences of the processor and memory technology trends underlying this increasing gap with a variety of techniques to reduce or tolerate memory latency. These techniques, unfortunate…
Mark and sweep garbage collectors (GC) are classical but still very efficient automatic memory management systems. Although challenged by other kinds of systems, such as copying collectors, mark and sweep collectors remain among the best in terms of performance.This paper describ…
Tabling can be implemented in a Prolog system by means of SLG-WAM: consumers suspend by freezing the execution stacks. XSB is an implementation that does so. The memory model is quite complex and attempts to understand the notion of usefulness of data in XSB well enough to build …
This paper examines the design space for copying garbage collectors (GCs) in which "large objects" are managed in a separate, non-copy-collected space. We focus on two main issues:1. how to set the policy for classifying objects as "large"2. how to manage the large object spaceWe…
We describe a new incremental algorithm for the concurrent reclamation of a program's allocated, yet unreachable, data. Our algorithm is a variant of mark-&-sweep collection that---unlike prior designs---runs mutator, marker, and sweeper threads concurrently without explicit fine…
We show that for 8 real and varied C and C++ programs, several conventional dynamic storage allocators provide near-zero fragmentation, once we account for overheads due to implementation details such as headers, alignment, etc. This substantially strengthens our previous results…
Many useful programming language extensions and system support libraries require knowledge of the locations of fields within objects at run time. Examples include orthogonal persistent object stores, precise garbage collectors, data structure picklers, and parameter marshaling sc…
We present a new near-real-time compacting collector and its implementation in a production quality Scheme compiler (Gambit-C). Our goal is to use this system as a base for an implementation of Erlang for writing soft real-time telecommunication applications. We start with a desc…
Prior work on dynamic memory allocation has largely neglected long-running server applications, for example, web servers and mail servers. Their requirements differ from those of one-shot applications like compilers or text editors. We investigated how to build an allocator that …
Garbage collectors used in embedded systems such as PersonalJava and Inferno or in operating systems such as SPIN must operate with limited resources and minimize their impact on application performance. Consequently, they must maintain short real-time pauses, low overhead, and a…
Massively distributed computing is a challenging problem for garbage collection algorithm designers as it raises the issue of scalability. The high number of hosts involved in a computation can require large tables for reference listing, whereas the lack of information sharing be…
This paper demonstrates a unified and garbage-collector independent way to describe the information required for precise collection. Thereby it is possible to construct, a library that can be used with various garbage collectors, without modifying the code of the library or the c…
This paper presents a classification of barrier techniques for interleaving tracing with mutator operation during an incremental garbage collection. The two useful tricolour invariants are derived from more elementary considerations of graph traversal. Barrier techniques for main…
One of the biggest disadvantages of non-moving collectors compared to moving collectors has been their limited ability to deal with memory fragmentation. In this paper, we describe two techniques to reduce fragmentation without the need for moving live data. The first technique r…
Stoye's one-bit reference tagging scheme can be extended to local counts of two or more via two strategies. The first, suited to pure register transactions, is a cache of referents to two shared references. The analog of Deutsch's and Bobrow's multiple-reference table, this cache…
For Garbage Collection (GC) to be a generally accepted means of memory management it is required to prove its efficiency. This paper presents a scheme that guarantees that an incremental Garbage Collector will have completed its collection cycle before the system runs out of memo…