[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
hash tables and GC
- To: firstname.lastname@example.org
- Subject: hash tables and GC
- From: Jon L White <email@example.com>
- Date: Fri, 22 Jul 88 04:42:47 PDT
- Cc: firstname.lastname@example.org, email@example.com, firstname.lastname@example.org
- In-reply-to: email@example.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
re: Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented). The
clever trick was that the incremental Reference Counting garbage collector
could be counted upon to tell you a likely candidate: if an entry for the
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it
is removeable; because the count of 1 means that that table entry points
to it and no one else does. A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).
But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable. And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.
At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly to implement the backwards-compatiblity feature of
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector. But then, the GC for Vax/NIL never got done. The best-laid
plans of mice and men go oftimes a-garbage-collecting.
-- JonL --