Re: MPS: weak hash tables

[Pip Cet]

On Thursday, July 4th, 2024 at 16:53, Gerd Möllmann <gerd.moellmann@gmail.com> 
wrote:
> Pip Cet pipcet@protonmail.com writes:
> > I believe we can make key-or-value tables work, and gain a potentially
> > useful debugging aid, by allowing struct igc_header to contain a
> > tagged pointer to an extended "header" structure which resides in
> > external (non-MPS) memory (a "remote reference" in MPS speak, which is
> > usually forbidden in AMC pools but appears to work if it's non-MPS
> > memory); we'd use the extended header instead of the header word to
> > determine object size, hash, and object type. That extended header
> > could then contain a Lisp_Object which would be scanned and kept alive
> > while the object belonging to the header is allocated, not just while
> > it's still reachable.
> 
> 
> Ah, I thought what you wrote in the other mail was related to the
> IA-32 software emulation shit^Wrequirement, sorry.

It's both:

1. change the IGC header to be a uint64_t, because bitfields don't always 
behave as expected.
2. use the low-order bits to distinguish extended external extra dependency 
headers from ordinary one-word headers. (This fixes the remaining IA32 bug)
3. keep track of an extra dependency (or a hash table thereof) in the exthdr
4. implement key-or-value weakness
5. implement two-stage finalization and get rid of SPLAT_PVEC
6. give all objects an IGC header (which is now just a struct { uint64_t }) and 
get rid of igc_has_header
7. use two-stage finalization to shrink weak hash tables which lose their 
contents

I've done (1)-(4) and (5) for bignums. It all seems to work, though two-stage 
finalization really is in two stages: you've got to collect several times until 
the bignums are actually freed.

I'll be honest, this is mostly to see (a) whether MPS can do it (it can!) and 
(b) for some Ideas I Have which probably won't ever come to fruition. The idea 
here is that every object (even conses) can keep alive an extra object (which, 
in turn, can keep alive other objects) while it is allocated (not just while it 
is reachable). No extra memory is used until the extra object actually becomes 
non-nil, which doesn't happen, for bignums, until they become unreachable. Once 
they're deallocated, the extra object possibly becomes unreachable, so it's 
queued for finalization, which it does by freeing the bignum PVEC's exthdr and 
the bignum data itself.

> > So if we (puthash a b key-or-value-hash), we'd make `a' keep alive` b'
> > and vice versa, but once they're no longer strongly reachable from
> > other objects, they'd be collected. (I've tried this, it works).
> > 
> > And we could finalize objects appearing in weak hash tables.
> > 
> > This would cause some memory fragmentation (xmalloc isn't moving), but
> > I don't think that's much of an issue: if you're using exotic weak
> > hashes, you're already creating unmovable allocations in
> > weak_hash_pool; if you're debugging, you probably don't care.
> > 
> > However, the functional gains are minimal and so far no one has
> > demanded key-or-value hashes...
> 
> This all gets rather complicated :-/. I'm depressed.

I do realize it's very complicated. As I said, it's about a Big Idea that I had 
a while ago, but which I couldn't implement back then because mark-and-sweep GC 
made it impossible. I'm still trying to think of a way to use the external 
header to find and store retaining paths...

I'm attaching the (ugly bit manipulation) code just in case I've convinced you, 
but I've got to admit I'm not fully convinced myself. I've got to sleep over 
it. Feel free, of course, not to read it :-)

Pip

0003-allow-IGC-to-keep-track-of-an-extra-dependency-in-th.patch
Description: Text Data

0005-finalize-bignums-later.-This-avoids-the-need-for-spl.patch
Description: Text Data

0004-implement-key-or-value-hash-tables.patch
Description: Text Data

0001-Ugly-hack-to-satisfy-MPS-single-access-rules.patch
Description: Text Data

0002-Allow-IGC-headers-to-be-pointers-to-an-external-exte.patch
Description: Text Data