[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

weak hash tables

From: Andy Wingo
Subject: weak hash tables
Date: Mon, 24 Oct 2011 19:19:21 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)


While doing the recent retagging work I realized that I really wanted to
kill weak pairs.  They look like pairs but you can't actually access
their fields using car and cdr -- terrible things.  To do that I had to
reimplement the weak hash tables, to make them not use them.  I did
that, reimplementing them as open-addressed hash tables, with robin hood
linear probing on collision.  It seems to work well.  Besides the
performance improvement you get with just scanning linearly through
memory, open-addressed hash tables aren't structurally perturbed by the
disappearing links.  It's a lot less messy, and uses less memory, and we
have space to encode the actual hash values in the table.  (However I
don't think our current hash functions are very good.)

The one nasty thing there was adapting to the old interfaces.  In
particular the hashx interface expects to be able to assoc down a list,
but there are no assoc lists in the new weak tables.  Guess what I do?
That's right, for weak hashx tables I make new association lists in the
equal? handler, then pass that alist to the user's assoc function.

Currently the new weak tables are only accessible under the old API.  I
don't know whether to publicise the new API, or make a different API, or
what.  If we hadn't coded the handle API into our hash tables I would
replace the regular (strong) hash table implementation too.  I might
still do that but it's not pressing.

Anyway, thoughts on the API are welcome.



ps.  The new weak tables are thread-safe.  Yay.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]