Re: avl-trees vs. hashes

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> 
> I looked at weaks.[ch] in libguile but I still haven't a clue what weak
> hash tables are.
> 

I can't explain exactly how they are implemented because I don't know,
but here is what they do:

There are three classes of weak hash tables (plus weak vectors). The
weak hash table does not protect the "weak" part of any entry against
GC, and removes the entry if any part of it gets GCd. So to be more
specific:

1) A weak-key hash-table is a hash table where the keys are not
protected against GC, but the values are. If the key object ever gets
GC'd, the entry in the hash table corresponding to it goes away.

2) A weak-value hash-table is the other way around - it protects the
keys but not the values.

3) A doubly-weak hash-table is weak in both of these respects.

A weak-value hash-table is extremely useful for implementing certain
types of caches. If you have a function that maps certain keys,
e.g. strings, to objects that are expensive to create, cost a fair bit
of memory, but are safe to share, you can use a weak-value hash table
from the strings to the objects and always check it before using the
object constructor - if a copy of the object you want already exists,
you will get it back. If not you create a new one and put it in the
hash table. It will be referenced there only so long as some code is
using it, so sharing is maximized, but no space is wasted. I use this
technique for fonts, colors and images in scwm. Bascially, it's a
reference-counted cache, except you don't have to reference-count, GC
deals with it automatically.

A weak-key hash-table is somewhat but not entirely redudant with
object property lists. I think it is used to implement certain Guile
internals however.

I am not sure what doubly-weak hash tables are useful for.

If you are interested, I can try to figure out how Guile's weak hash
tables work and whether this can be generalized. As far as I can tell
from a cursory look, they implement non-protection of certain parts by
creating their vector with magical flag bits in the type tag which
tell the vector marker not to mark certain parts

 - Maciek