A real-time garbage collector based on the lifetimes of objects
Communications of the ACMPublished 1 June 1983Open access
Henry Lieberman, Carl Hewitt
Citations572
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents a garbage collection algorithm that makes storage for short-lived objects cheaper than storage for long-livedObjects, that operates in real time, increases locality of reference, for better virtual memory performance, and works well with multiple processors and a large address space.
Abstract
In previous heap storage systems, the cost of creating objects and garbage collection is independent of the lifetime of the object. Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector to reclaim storage for these objects more quickly. The garbage collector should spend proportionately less effort reclaiming objects with longer lifetimes. We present a garbage collection algorithm that (1) makes storage for short-lived objects cheaper than storage for long-lived objects, (2) that operates in real time—object creation and access times are bounded, (3) increases locality of reference, for better virtual memory performance, (4) works well with multiple processors and a large address space.
Keywords
Computer Science
Journal of the ACMA Transformation System for Developing Recursive Programs
1,316 Citations1977R. M. Burstall, John Darlington
A system of rules for transforming programs, with the programs in the form of recursion equations, are described, with an initially very simple, lucid, and hopefully correct program transformed into a more efficient one by altering the recursion structure.
Artificial IntelligenceViewing control structures as patterns of passing messages
1,161 Citations1977Carl Hewitt
A light sensing apparatus is described which employs a GaAsP MOS light-receiving element to which a potential is applied for creating a depletion region.
Communications of the ACMList processing in real time on a serial computer
592 Citations1978Henry G. Baker
A real-time list processing system is presented which continuously reclaims garbage, including directed cycles, while linearizing and compacting the accessible cells into contiguous locations to avoid fragmenting the free storage pool.
Communications of the ACMOn-the-fly garbage collection
559 Citations1978Edsger W. Dijkstra, Leslie Lamport +3 more
As an example of cooperation between sequential processes with very little mutual interference despite frequent manipulations of a large shared data space, a technique is developed which allows nearly all of the activity needed for garbage detection and collection to be performed by an additional processor operating concurrently with the processor devoted to the computation proper.
The Smalltalk-76 programming system design and implementation
273 Citations1978Daniel H. H. Ingalls
This paper describes a programming system based on the metaphor of communicating objects which provides flexibility, modularity and compactness, and a corresponding virtual memory is described which offers dense utilization of resident space.
Communications of the ACMAn efficient, incremental, automatic garbage collector
256 Citations1976L. Peter Deutsch, Daniel G. Bobrow
A new way of solving the storage reclamation problem for a system such as Lisp that allocates storage automatically from a heap, and does not require the programmer to give any indication that particular items are no longer useful or accessible is described.
ACM SIGART BulletinThe Lisp Machine manual
195 Citations1981Daniel Weinreb, David Moon
This 471-page, softcover manual describes the programming language and software environment of the Lisp Machine developed at M.I.T.'s Artificial Intelligence Laboratory over the past 8 years.
Compilation and delayed evaluation in APL
116 Citations1978Leo J. Guibas, Douglas K. Wyatt
An algorithm for incorporating the selector operators into the accessors for the leaves of the expression tree and incorporating their effect into the leaf accessors is presented, which will be shown to be an integral part of delayed evaluation for APL.
DSpace@MIT (Massachusetts Institute of Technology)Computer Systems with a Very Large Address Space and Garbage Collection.
112 Citations1977Peter Boehler Bishop
This paper presents a meta-modelling system that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive process of computer programming called “hacking”.
ACM SIGSAM BulletinThe function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem
68 Citations1970Joel Moses
A problem common to many powerful programming languages arises when one has to determine what values to assign to free variables in functions and the argument is tried to couch the argument in ALGOL-like terms as much as possible.
The Apiary network architecture for knowledgeable systems
46 Citations1980Carl Hewitt
A great deal of work remains to be done in order to make the Apiary into a practical usable system, introducing important concepts and techniques such as Interest groups.
DSpace@MIT (Massachusetts Institute of Technology)ACTOR SYSTEMS FOR REAL-TIME COMPUTATION
45 Citations1978Henry G. Baker
This thesis explores several problems associated with implementing Actor theory as a basis for computer systems design and gives an operational semantics for this theory by exhibiting an interpreter which is mapping this conceptual system onto current hardware in such a way that simple primitive operations all take a (small) bounded amount of time.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)A Preview of Act 1
34 Citations1981Henry Lieberman
A model of computation based on the notion of an actor, an active object that communicates by message passing, is proposed, which blur the conventional distinction between data and procedures.
AMORD: A Deductive Procedure System
34 Citations1978Johan de Kleer, Jon Doyle +3 more
This research was conducted at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology with support from the Advanced Research Projects Agency of the Department of Defense and Office of Naval Research.
ACM SIGPLAN Lisp PointersAddress/memory management for a gigantic LISP environment or, GC considered harmful
33 Citations1987Jon L. White
Some scenarios are presented considering a variety of currently-available technologies, and of one speculative possibility --- videodisc --- by which a requisite compactifying GC would be done "overnight", or over the weekend.
National Conference on Artificial IntelligenceKnowledge embedding in the description system omega
33 Citations1980Carl Hewitt, Giuseppe Attardi +1 more
The techniques in Omega represent an important advance in the creation of self-describing systems without engendering the problems discovered by Russell.
ETHER: a parallel problem solving system
26 Citations1979William A. Kornfeld
Two uses for parallelism are discussed: parallel evaluation of subgoah and the use of opponents, concurrently running activities that attempt to show a subgoal is unattainable.
A LISP machine
4 Citations1980Richard D. Greenblatt, Thomas F. Knight +2 more
The implementation is based on a powerful microprogrammed processor designed specifically for LISP, which manipulates items which have a built-in data-type field and incorporates the personal computer philosophy.