Re: weak hash tables

[Ludovic Courtès]

Hi Andy,

Andy Wingo <address@hidden> skribis:

> 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.

Agreed.  The reason was to keep the weak hash table API unchanged.

> 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,

Could you provide an executive summary ;-) of:

  - how good ol’ weak hash tables related to the new weak sets and weak
    tables?

  - what the deal is wrt. performance, linear probing, and rehashing?

> 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.

That’s definitely a huge improvement.  :-)

> 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.
> Gross.
>
> 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.

FWIW I would keep the new C API private.

Is there any advantage to using the new weak table API instead of the
old weak hash table API?  The names suggest that they’re not quite
equivalent, but maybe that’s just the names?

Thanks for this brave endeavor!  :-)

Ludo’.