Hash-Consing Garbage Collection
Report ID: TR-412-93Author: Appel, Andrew W. / Goncalves, Marcelo Jose de Rezende
Date: 1993-02-00
Pages: 18
Download Formats: |Postscript|
Abstract:
We describe an implementation of hash-consing for the Standard ML of New Jersey compiler. Hash-consing can eliminate replication among heap-allocated data, which may allow the use of fast equality checking and may also improve the locality of reference of a program. The cost of a hash table lookup for each record allocated may, however, offset any gains from the elimination of replication. Our hash-consing scheme is integrated with a generational garbage collector. Only records that survive a garbage collection are ``hash-consed,'' thus avoiding the cost of a table lookup for short-lived records. We discuss some issues related with the implementation of this scheme and present a performance evaluation.