Hash-Consing Garbage Collection

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.