Herve Touati

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-443

, 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-443.pdf

This report presents the design and evaluation of the garbage collector we designed for the Aquarius project. Our design is the result of an attempt to incorporate into Prolog implementations the ideas which made generation scavenging successful for Lisp and Smalltalk. The main challenge was to take advantage of generation scavenging without giving away the basic Prolog technique of memory recovery upon backtracking based on stack deallocation. We were able to do so with little extra overhead at run-time. Our main strategy consists in restricting the action of the garbage collector to a fixed amount of memory allocated at the top of the global stack. This strategy has several advantages: it improves the locality of the executing program by keeping the data structures compacted and by allocating new objects in a fixed part of the address space; it improves the locality and the predictability of the garbage collection, which can concentrate its efforts on the fixed size area where new objects are allocated; and it allows us to use simpler, time-efficient garbage collection algorithms. The performance of the algorithm is further enhanced by the use of copying algorithms whenever made possible by the deterministic nature of the executing program.

---

BibTeX citation:

@techreport{Touati:CSD-88-443,
    Author= {Touati, Herve},
    Title= {A Prolog Garbage Collector for Aquarius},
    Year= {1988},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5279.html},
    Number= {UCB/CSD-88-443},
    Abstract= {This report presents the design and evaluation of the garbage collector we designed for the Aquarius project. Our design is the result of an attempt to incorporate into Prolog implementations the ideas which made generation scavenging successful for Lisp and Smalltalk. The main challenge was to take advantage of generation scavenging without giving away the basic Prolog technique of memory recovery upon backtracking based on stack deallocation. We were able to do so with little extra overhead at run-time. Our main strategy consists in restricting the action of the garbage collector to a fixed amount of memory allocated at the top of the global stack. This strategy has several advantages: it improves the locality of the executing program by keeping the data structures compacted and by allocating new objects in a fixed part of the address space; it improves the locality and the predictability of the garbage collection, which can concentrate its efforts on the fixed size area where new objects are allocated; and it allows us to use simpler, time-efficient garbage collection algorithms. The performance of the algorithm is further enhanced by the use of copying algorithms whenever made possible by the deterministic nature of the executing program.},
}

EndNote citation:

%0 Report
%A Touati, Herve 
%T A Prolog Garbage Collector for Aquarius
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-443
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5279.html
%F Touati:CSD-88-443