[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: hash tables and GC
- To: barmar@Think.COM
- Subject: Re: hash tables and GC
- From: David L. Andre <DLA@JASPER.SCRC.Symbolics.COM>
- Date: Wed, 31 Aug 88 22:49 EDT
- Cc: firstname.lastname@example.org, email@example.com
- In-reply-to: <19880901014745.2.BARMAR@OCCAM.THINK.COM>
Date: Wed, 31 Aug 88 21:47 EDT
From: Barry Margolin <barmar@Think.COM>
There's actually an even more trivial solution: don't implement them if
you don't want to!
The difference between weak tables and ordinary tables is that the
implementation is ALLOWED to GC entries in weak tables. However, just
as Common Lisp never actually says that an implementation MUST have a
GC, it can't REQUIRE an implementation to GC entries in a weak table.
So, if your GC is not easily extended to support weak tables, you can
simply ignore the :WEAK (or whatever) option. The only invalid way to
implement weak tables is to implement them in such a way that they GC
entries that they shouldn't; remembering too much should never bother a
valid CL program (unless it runs out of memory, but that's outside the
language spec). (Hmm, this argument would justify a Lisp implementation
that used only a reference-count GC, but I expect that there would be
far fewer weak tables than circular structures, so the argument doesn't
really scale up.)
By the way, I assume that David meant that only key fields of tables
should be skipped. Otherwise you could end up with keys whose values
have been GCed.
I can think of applications for weak-key, weak-value, and
weak-key-and-value hash tables. Certainly weak-key is the most
By the way, here is how I think weak tables could be implemented in a
mark-sweep GC (are there any of those around any more?):
During the mark phase, don't recurse through the keys of any weak
tables. Before the sweep phase, make another pass, deleting any weak
table entries whose keys are not marked.
The added passes of both the copying and mark/sweep GCs would be sped up
significantly if the implementation maintained a list of all weak tables
(or it could cons up such a list during the first pass), so that it
wouldn't have to make a full pass through memory to find them.
Sounds reasonable given 10 seconds of thought.