Re: MPS: weak hash tables

["Gerd Möllmann" <gerd.moellmann@gmail.com>]

Pip Cet <pipcet@protonmail.com> writes:

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

Thanks for the overview.

>
>> > 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 :-)

I have read it, as far as I can read patches which I'm not good at. And
I find it ugly and one could encapsulate things so nicely in C++,
but I digress :-).

Maybe this will surprise you, but probably not: I'd say put it in if you
decide you want to after sleeping over it.

I hate giving advice (and I'm sometimes lying), but in this case I can
only say follow your ideas and have fun. Don't wait until you're 70. If
my MPS experiment was good only for that purpose, it was worth it for
me.

Honesty demands that I add that that would also be good for me: I said
right from the start that I won't maintain _anything_ and lately that I
really really feel I need to have a break from this MPS stuff, so I'd
love if you could take over and realize yoiur ideas.

As usual my 2 cents. Thanks for your work!