Re: MPS: weak hash tables

[Pip Cet <pipcet@protonmail.com>]

On Tuesday, July 2nd, 2024 at 06:55, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> > On Tuesday, July 2nd, 2024 at 05:47, Gerd Möllmann gerd.moellmann@gmail.com wrote:
> > 
> > > Pip Cet pipcet@protonmail.com writes:
> > > 
> > > > Also, any opinions on :weakness 'key-or-value? Can we just not support it and use strong hash tables instead?
> > > 
> > > So, after some more reading, I think I have an opinion. Let me read what
> > > it is :-)
> > > 
> > > The design supports 1 vector of weak references, and 1 vector of
> > > strong references. So either keys or values can be weak but not both.
> > 
> > Why not? I may be missing something obvious, but the scan method is
> > allowed to modify the scanned object, right? We're doing that in the
> > weak-key case anyway.
> 
> I may be missing something as well, as usual :-). And yes, we have
> exclusive access to the object while it is being scanned.

So this is what I think the current branch is doing. Please tell me if I'm totally missing something.

* weak-key and weak-value tables are allocated as you describe
* if weakness is Key_And_Value (and I'm not sure that's correct, but it matches the source code comment), the strong part contains the hash values, next table, and index table, and the weak part contains both the keys and the values, in a single array of length 2 * size. Rather than adjusting the stride and keeping things in a single cache line in this (slow, anyway) case, we store all keys in weak->entries[0..table_size], and all values in weak->entries[table_size..2*table_size].
* when MPS splats a key, we (not MPS) splat the value before it is scanned
* when MPS splats a value, we splat the key after it has been scanned 
* it appears to work:

(setq table (make-hash-table :weakness 'key-and-value))

(puthash t (cons 1 2) table)
(puthash (cons 3 4) t table)
(puthash (cons 5 6) (cons 7 8) table)

(hash-table-count table) ;; => 3

(igc--collect)

(hash-table-count table) ;; => 1

(setq values nil)

(igc--collect)

(hash-table-count table) ;; => 0


What confused me was the "after it has been scanned" part. I believe that means we keep the objects alive until we scan again, but as splatting isn't perfectly eager anyway, that should rarely become a problem. Maybe we need to call igc--collect twice for a full full collection.

> > So what I'm currently doing is creating a single vector containing all
> > keys, then all values, for key-and-value hash tables. If the key gets
> > splatted, the value gets splatted right away and everything works as
> > it should. If the value gets splatted, we've already decided to keep
> > alive the key, but that's okay as it's only a weak reference.
> 
> 
> My understanding so far is that the strong part is always allocated with
> rank strong, right? The strong part contains one array of references,
> the entries, which are therefore also strong.

The strong part contains no references in the key-and-value case, just fixnums.

> The pointers to the
> entries for key/value are set up to refer to the entries arrays of
> either the strong part or the weak part, as needed. So my understanding
> is that one of them is always strong and other weak. The W predicate can
> then only be implemented in one of them.

No, they can both be weak.

> > > In Emacs itself, I see from git grep that :weakness key, value, and t
> > > are being used, where t means key-and-value. Haven't checked for which
> > > use cases t is used, though.
> > 
> > What surprised me is that there are plenty of hash tables that are
> > both weak and use equal as a predicate. That doesn't make much sense
> > to me...
> 
> Hm, maybe they are value weak? Key-weak would make no sense, I think,
> indeed.

emacs-lisp/macroexp.el:(defvar macroexp--warned (make-hash-table :test #'equal :weakness 'key))
emacs-lisp/map-ynp.el:(defconst read-answer-map--memoize (make-hash-table :weakness 'key :test 'equal))
emacs-lisp/pcase.el:;; (defconst pcase--memoize-2 (make-hash-table :weakness 'key :test 'equal))
org/org-macs.el:(defvar org-sxhash-hashes (make-hash-table :weakness 'key :test 'equal))

are key-weak...

> > > Anyway, we're better off than before :-).
> > 
> > On 64-bit systems. 32-bit systems are still broken, I'm afraid, and
> > while my patch fixes the crash I've seen on i386 Debian, Eli's crash
> > looked very different and may not be fixed by it.
> 
> From my POV, it's not a deal breaker if 32-bit systems don't work with
> igc, They still have the old GC, and 32-bit systems are kind of obsolete
> even Intel says and so on. It would be nice if we could that working of
> course.

My concern is that Ravenbrook may get around to implementing emulation for aarch64 or amd64.

> > Also, there's the whole caution thing about weak objects containing
> > only unaligned words or words pointing directly to a base object,
> > which is only relevant on Unix/i386, IIRC. (MPS emulates instructions
> > to simulate fine-grained barriers, which is a really cool idea; I'd
> > still like an option to turn it off though...). That would mean we
> > have to replace Lisp_Objects and use the ptr member of our union (and
> > that's the reason I'm using fixnums rather than plain integers for the
> > hash).
> 
> Yeah, that's another point I forgot about. The trickery MPS does on
> Windows and Linux with 32-bits. The consequences of which are another
> very good reason to declare 32-bit systems as not supproted, from my
> POV.

Oh, that's on Windows, too? I believe that might mean Eli might run into weird bugs...

Thanks again, and thanks for the asserts.

Pip