MPS: weak hash tables

MPS: weak hash tables

[Gerd Möllmann]

Hi Pip,

I've begun to read the new code a little bit now, and I don't understand
the index vector allocation yet.

I see that the index_bits from compute_index_bits are passed to the
allocation functions in igc.c, but they don't seem to be used for
determining how much to allocate for the index.

I think that the index is given 2 * table_size room ATM, but I'm not
sure if I read that right, and it's late. Is it sure that that suffices?

Re: MPS: weak hash tables

[Pip Cet]

On Monday, July 1st, 2024 at 20:47, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Hi Pip,
> 
> I've begun to read the new code a little bit now, and I don't understand
> the index vector allocation yet.

It's currently a gross overallocation. The index starts at ret->strong->entries + 3 * size and ends at ret->strong->entries + 5 * size, giving us 2 * size entries. Index bits is elogb (size) + 1, so the actual index length is at most 2 * size for size > 1, as it is in our case because I force it to be at least 65.

> I see that the index_bits from compute_index_bits are passed to the
> allocation functions in igc.c, but they don't seem to be used for
> determining how much to allocate for the index.

That is correct.

> I think that the index is given 2 * table_size room ATM, but I'm not
> sure if I read that right, and it's late. Is it sure that that suffices?

I believe it is, but it needs fixing anyway. Will do that next.

Thanks for the heads-up!

Pip

Re: MPS: weak hash tables

[Pip Cet]

On Monday, July 1st, 2024 at 21:16, Pip Cet <pipcet@protonmail.com> wrote:
> On Monday, July 1st, 2024 at 20:47, Gerd Möllmann gerd.moellmann@gmail.com wrote:
> > I think that the index is given 2 * table_size room ATM, but I'm not
> > sure if I read that right, and it's late. Is it sure that that suffices?
> 
> I believe it is, but it needs fixing anyway. Will do that next.

Actually, I've run into another bug which needs to be fixed first: when the hash table's strong part is allocated from MPS but t->table_size is still Qnil, we sometimes end up scanning it (when trying to allocate the weak part), and then XFIXNUM (Qnil) dies, as it rightfully should, except it's in the middle of a scan so it dies quite horribly.

Is it correct that all IGC objects need to be scannable when they're still zeroed-out from allocation?

(I'm currently trying to simply delay setting the weak->strong and strong->weak pointers until the parts are initialized, and to turn the scan into a nop if they aren't. I'm not convinced that's sufficient to prevent the compiler from reordering the initialization so an invalid state becomes visible to the scan function, though...)

Also, any opinions on :weakness 'key-or-value? Can we just not support it and use strong hash tables instead?

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> Is it correct that all IGC objects need to be scannable when they're
> still zeroed-out from allocation?

I'm not 100% cure what you mean. One must arrange things so that the
objects are always scannable, that is so, from the moment on their
memory is commited with mps_commit.

> (I'm currently trying to simply delay setting the weak->strong and
> strong->weak pointers until the parts are initialized, and to turn the
> scan into a nop if they aren't. I'm not convinced that's sufficient to
> prevent the compiler from reordering the initialization so an invalid
> state becomes visible to the scan function, though...)

Hm, don't know. I didn't get that far when reading the code yesterday.

> Also, any opinions on :weakness 'key-or-value? Can we just not support
> it and use strong hash tables instead?

I'll try to come up with opinions today :-)

Re: MPS: weak hash tables

[Gerd Möllmann]

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.

Let's say that W(O) returns true when object O is references from weak
references only. AFAICT, the implementation of W in MPS requires
allocation with rank weak to get weak references.

key/value pairs are then removed from a hash table when

Weakness        Predicate
----------------------------------------
key             W(key)
value           W(value)
key-and-value   W(key) and W(value),
key-or-value    W(key) or W(value).

I'd say that neither key-and-value nor key-and-value can be
implemented because both require 2 weak parts for implementing W.

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.

It surprises me a bit that key-and-value is used, I must admit. Hm.
Also interesting could be what is used outside of Emacs, and for what,
of course.

I have currently no idea how to get from here to key-and/or-value.

Anyway, we're better off than before :-).

Re: MPS: weak hash tables

[Pip Cet]

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.

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.

> Let's say that W(O) returns true when object O is references from weak
> references only. AFAICT, the implementation of W in MPS requires
> allocation with rank weak to get weak references.

That's my understanding too.

> key/value pairs are then removed from a hash table when
> 
> Weakness Predicate
> ----------------------------------------
> key W(key)
> value W(value)
> key-and-value W(key) and W(value),
> key-or-value W(key) or W(value).

Hmm. I think I have key-and-value and key-or-value reversed, then...


> I'd say that neither key-and-value nor key-and-value can be
> implemented because both require 2 weak parts for implementing W.

Sorry, I still don't understand why.

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

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

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

Anyway, thanks a lot, so far. Sorry I'm being dense about the key-and-value thing.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

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

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

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

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

> Anyway, thanks a lot, so far. Sorry I'm being dense about the
> key-and-value thing.

Nicht dafür (something meaning with pleasure :-)).

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> Is it correct that all IGC objects need to be scannable when they're
> still zeroed-out from allocation?
>
> (I'm currently trying to simply delay setting the weak->strong and
> strong->weak pointers until the parts are initialized, and to turn the
> scan into a nop if they aren't. I'm not convinced that's sufficient to
> prevent the compiler from reordering the initialization so an invalid
> state becomes visible to the scan function, though...)

I have here fixes for that (I think) that I'll transfer to GNU in a few
minutes. I think with that we're good. Please have a look.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Pip Cet <pipcet@protonmail.com> writes:
>
>> Is it correct that all IGC objects need to be scannable when they're
>> still zeroed-out from allocation?
>>
>> (I'm currently trying to simply delay setting the weak->strong and
>> strong->weak pointers until the parts are initialized, and to turn the
>> scan into a nop if they aren't. I'm not convinced that's sufficient to
>> prevent the compiler from reordering the initialization so an invalid
>> state becomes visible to the scan function, though...)
>
> I have here fixes for that (I think) that I'll transfer to GNU in a few
> minutes. I think with that we're good. Please have a look.

You made a change meanwhile that I think also works, so I added only 2
asserts for what I thought was missing.

Re: MPS: weak hash tables

[Ihor Radchenko]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

>> I have here fixes for that (I think) that I'll transfer to GNU in a few
>> minutes. I think with that we're good. Please have a look.
>
> You made a change meanwhile that I think also works, so I added only 2
> asserts for what I thought was missing.

I am getting

Dumping under the name bootstrap-emacs.pdmp
Dumping fingerprint: 682fbe72dde493fa543cbf53733386cdb3498ca18fdaefc91fd4c41f0391e9e4
cold user data: 1a77f78
heap end: 1a7cb90

Error: error ("relocation target was not dumped: #s(hash-table test equal weakness value)")
  dump-emacs-portable("/home/yantar92/Git/emacs/src/bootstrap-emacs.pdmp")
  (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used))
  (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t))
  (unwind-protect (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t)) (unless success (ignore-errors (delete-file output))))
  (let (success) (unwind-protect (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t)) (unless success (ignore-errors (delete-file output)))))
  (let ((output (cond ((equal dump-mode "pdump") "emacs.pdmp") ((equal dump-mode "dump") "emacs") ((equal dump-mode "bootstrap") "emacs") ((equal dump-mode "pbootstrap") "bootstrap-emacs.pdmp") (t (error "Unrecognized dump mode %s" dump-mode))))) (when (and (featurep 'native-compile) (equal dump-mode "pdump")) (setq native-comp-enable-subr-trampolines t)) (message "Dumping under the name %s" output) (condition-case nil (delete-file output) (file-error nil)) (let (success) (unwind-protect (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t)) (unless success (ignore-errors (delete-file output))))) (if (not (or (eq system-type 'ms-dos) (eq system-type 'haiku) (or (featurep 'android) (eq system-type 'android)) (member dump-mode '("pbootstrap" "bootstrap")))) (let ((name (format "emacs-%s.%d" emacs-version emacs-build-number)) (exe (if (eq system-type 'windows-nt) ".exe" ""))) (while (string-match "[^-+_.a-zA-Z0-9]+" name) (setq name (concat (downcase (substring name 0 (match-beginning 0))) "-" (substring name (match-end 0))))) (message "Adding name %s" (concat name exe)) (add-name-to-file (expand-file-name (concat "emacs" exe) invocation-directory) (expand-file-name (concat name exe) invocation-directory) t) (when (equal dump-mode "pdump") (message "Adding name %s" (concat name ".pdmp")) (add-name-to-file (expand-file-name "emacs.pdmp" invocation-directory) (expand-file-name (concat name ".pdmp") invocation-directory) t)))) (kill-emacs))
  (if dump-mode (let ((output (cond ((equal dump-mode "pdump") "emacs.pdmp") ((equal dump-mode "dump") "emacs") ((equal dump-mode "bootstrap") "emacs") ((equal dump-mode "pbootstrap") "bootstrap-emacs.pdmp") (t (error "Unrecognized dump mode %s" dump-mode))))) (when (and (featurep 'native-compile) (equal dump-mode "pdump")) (setq native-comp-enable-subr-trampolines t)) (message "Dumping under the name %s" output) (condition-case nil (delete-file output) (file-error nil)) (let (success) (unwind-protect (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t)) (unless success (ignore-errors (delete-file output))))) (if (not (or (eq system-type 'ms-dos) (eq system-type 'haiku) (or (featurep 'android) (eq system-type 'android)) (member dump-mode '("pbootstrap" "bootstrap")))) (let ((name (format "emacs-%s.%d" emacs-version emacs-build-number)) (exe (if (eq system-type 'windows-nt) ".exe" ""))) (while (string-match "[^-+_.a-zA-Z0-9]+" name) (setq name (concat (downcase (substring name 0 (match-beginning 0))) "-" (substring name (match-end 0))))) (message "Adding name %s" (concat name exe)) (add-name-to-file (expand-file-name (concat "emacs" exe) invocation-directory) (expand-file-name (concat name exe) invocation-directory) t) (when (equal dump-mode "pdump") (message "Adding name %s" (concat name ".pdmp")) (add-name-to-file (expand-file-name "emacs.pdmp" invocation-directory) (expand-file-name (concat name ".pdmp") invocation-directory) t)))) (kill-emacs)))
  (if (and (eq system-type 'android) (featurep 'android)) (progn (when (not noninteractive) (let ((temp-dir (getenv "TEMP")) (dump-file-name (format "%semacs-%s.pdmp" (file-name-as-directory "~") pdumper-fingerprint)) (dump-temp-file-name (format "%s~emacs-%s.pdmp" (file-name-as-directory "~") pdumper-fingerprint))) (unless (pdumper-stats) (condition-case nil (progn (dump-emacs-portable dump-temp-file-name) (rename-file dump-temp-file-name dump-file-name) nil) (error nil)))))) (if dump-mode (let ((output (cond ((equal dump-mode "pdump") "emacs.pdmp") ((equal dump-mode "dump") "emacs") ((equal dump-mode "bootstrap") "emacs") ((equal dump-mode "pbootstrap") "bootstrap-emacs.pdmp") (t (error "Unrecognized dump mode %s" dump-mode))))) (when (and (featurep 'native-compile) (equal dump-mode "pdump")) (setq native-comp-enable-subr-trampolines t)) (message "Dumping under the name %s" output) (condition-case nil (delete-file output) (file-error nil)) (let (success) (unwind-protect (let ((tmp-dump-mode dump-mode) (dump-mode nil) (lexical-binding nil)) (if (member tmp-dump-mode '("pdump" "pbootstrap")) (dump-emacs-portable (expand-file-name output invocation-directory)) (dump-emacs output (if (eq system-type 'ms-dos) "temacs.exe" "temacs")) (message "%d pure bytes used" pure-bytes-used)) (setq success t)) (unless success (ignore-errors (delete-file output))))) (if (not (or (eq system-type 'ms-dos) (eq system-type 'haiku) (or (featurep 'android) (eq system-type 'android)) (member dump-mode '("pbootstrap" "bootstrap")))) (let ((name (format "emacs-%s.%d" emacs-version emacs-build-number)) (exe (if (eq system-type 'windows-nt) ".exe" ""))) (while (string-match "[^-+_.a-zA-Z0-9]+" name) (setq name (concat (downcase (substring name 0 (match-beginning 0))) "-" (substring name (match-end 0))))) (message "Adding name %s" (concat name exe)) (add-name-to-file (expand-file-name (concat "emacs" exe) invocation-directory) (expand-file-name (concat name exe) invocation-directory) t) (when (equal dump-mode "pdump") (message "Adding name %s" (concat name ".pdmp")) (add-name-to-file (expand-file-name "emacs.pdmp" invocation-directory) (expand-file-name (concat name ".pdmp") invocation-directory) t)))) (kill-emacs))))
  load("loadup.el")
relocation target was not dumped: #s(hash-table test equal weakness value)


-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: MPS: weak hash tables

[Gerd Möllmann]

Ihor Radchenko <yantar92@posteo.net> writes:

> Gerd Möllmann <gerd.moellmann@gmail.com> writes:
>
>>> I have here fixes for that (I think) that I'll transfer to GNU in a few
>>> minutes. I think with that we're good. Please have a look.
>>
>> You made a change meanwhile that I think also works, so I added only 2
>> asserts for what I thought was missing.
>
> I am getting
>
> Dumping under the name bootstrap-emacs.pdmp
> Dumping fingerprint: 682fbe72dde493fa543cbf53733386cdb3498ca18fdaefc91fd4c41f0391e9e4
> cold user data: 1a77f78
> heap end: 1a7cb90
>
> Error: error ("relocation target was not dumped: #s(hash-table test equal weakness value)")
>   dump-emacs-portable("/home/yantar92/Git/emacs/src/bootstrap-emacs.pdmp")
>   (if (member tmp-dump-mode '("pdump" "pbootstrap"))

Hm, for me it builds fine. As usual my build starts git clean -xdf, and
I built without native-comp. How did you build? 

Re: MPS: weak hash tables

[Pip Cet]

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

Re: MPS: weak hash tables

[Ihor Radchenko]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

>> Error: error ("relocation target was not dumped: #s(hash-table test equal weakness value)")
>>   dump-emacs-portable("/home/yantar92/Git/emacs/src/bootstrap-emacs.pdmp")
>>   (if (member tmp-dump-mode '("pdump" "pbootstrap"))
>
> Hm, for me it builds fine. As usual my build starts git clean -xdf, and
> I built without native-comp. How did you build? 

I did git clean, but I do use native-comp.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 826 bytes --]

On Tuesday, July 2nd, 2024 at 09:31, Ihor Radchenko <yantar92@posteo.net> wrote:
> Gerd Möllmann gerd.moellmann@gmail.com writes:
> 
> > > Error: error ("relocation target was not dumped: #s(hash-table test equal weakness value)")
> > > dump-emacs-portable("/home/yantar92/Git/emacs/src/bootstrap-emacs.pdmp")
> > > (if (member tmp-dump-mode '("pdump" "pbootstrap"))
> > 
> > Hm, for me it builds fine. As usual my build starts git clean -xdf, and
> > I built without native-comp. How did you build?
> 
> 
> I did git clean, but I do use native-comp.

Yes, it's native-comp creating a weak-value hash table and dumping it.

Can you try with this fix? Note that properly making that table weak again is still on the TODO list...

Sorry about that, I'd assumed I was building with nativecomp but wasn't.

Pip

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-MPS-native-comp-compilation.patch --]
[-- Type: text/x-patch; name=0001-Fix-MPS-native-comp-compilation.patch, Size: 1090 bytes --]

From b893473925f3f583687b75809f9e219e5a671cdd Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Tue, 2 Jul 2024 09:33:18 +0000
Subject: [PATCH] Fix MPS+native-comp compilation

* src/pdumper.c (decode_emacs_reloc): follow the dump redirection
pointer to a strong hash table.
---
 src/pdumper.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/src/pdumper.c b/src/pdumper.c
index 6ace914820b..dc1621b3cb9 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -4015,6 +4015,14 @@ decode_emacs_reloc (struct dump_context *ctx, Lisp_Object lreloc)
           {
 	    eassume (ctx); /* Pacify GCC 9.2.1 -O3 -Wnull-dereference.  */
             eassert (!dump_object_emacs_ptr (target_value));
+#ifdef HAVE_MPS
+	    if (WEAK_HASH_TABLE_P (target_value))
+	      {
+		strengthen_hash_table_for_dump (XWEAK_HASH_TABLE (target_value));
+		target_value = XWEAK_HASH_TABLE (target_value)->dump_replacement;
+	      }
+#endif
+
             reloc.u.dump_offset = dump_recall_object (ctx, target_value);
             if (reloc.u.dump_offset <= 0)
               {
-- 
2.45.2

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

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

See, I overlooked that! Then I think we're good :-). Thanks for
explaining this.

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

Agree.

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

Hm. What haopens is that some specific key K is stored in the hash table.
Lookup can use any key equal to K, but the splat happens only if K is no
longer referenced. Example maybe, K is stored in some object O, and we
want to lookup something related to K without always having access to O,
but we want the table to also tell us when O is no longer in use.
Something like that?

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

They are not very active anymore, and we could raise concerns and ask
them to make that opt-in :-).

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

I think they said somewhere it was done on Win32, but I can't find it at
the moment.

> Thanks again, and thanks for the asserts.

Thanks to you for your work!

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Pip Cet <pipcet@protonmail.com> writes:
>
>> 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.
>
> See, I overlooked that! Then I think we're good :-). Thanks for
> explaining this.

Ahh, that came with 62d7c958c831faf0e8e881e3847ff27a4b78be11 which I
didn't have yet transferred to my branch. That explains it, and I don't
feel so old anymore :-).

Re: MPS: weak hash tables

[Ihor Radchenko]

Pip Cet <pipcet@protonmail.com> writes:

>> I did git clean, but I do use native-comp.
>
> Yes, it's native-comp creating a weak-value hash table and dumping it.
>
> Can you try with this fix? Note that properly making that table weak again is still on the TODO list...

With your fix, the compilation finishes.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: MPS: weak hash tables

[Helmut Eller]

On Tue, Jul 02 2024, Pip Cet wrote:

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

Why do you think that the restriction only applies to 32-bit systems?
My interpretation of

  Section 7.4. Caution
  ...
  “Aligned pointer” means a word whose numeric value (that is, its value
  when treated as an unsigned integer) is a multiple of the size of a
  pointer. If you’re using a 64-bit architecture, that means that an
  aligned pointer is a multiple of 8 and its bottom three bits are zero.
  ...

is that it applies to 64-bit machines as well.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> I think they said somewhere it was done on Win32, but I can't find it at
> the moment.

Found it:

  Emulation of accesses to protected objects happens when all of the
  following are true:

  The object is a weak object allocated in an AWL pool.
  
  The MPS is running on Linux/IA-32 or Windows/IA-32. Extending this
  list to new (reasonable) operating systems should be tolerable (for
  example, macOS/IA-32). Extending this to new processor architectures
  requires more work.
  
  The processor instruction that is accessing the object is of a
  suitable simple form. The MPS doesn’t contain an emulator for all
  possible instructions that might access memory, so currently it only
  recognizes and emulates a simple MOV from memory to a register or
  vice-versa.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Eli Zaretskii <eliz@gnu.org>,  Helmut Eller <eller.helmut@gmail.com>,
>   Emacs Devel <emacs-devel@gnu.org>
> Date: Tue, 02 Jul 2024 08:55:11 +0200
> 
> > 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.

I don't share that view.  Supporting 32-bit builds in Emacs is a must
for years to come, and that's non-negotiable.

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Tue, 02 Jul 2024 09:15:44 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: Eli Zaretskii <eliz@gnu.org>, Helmut Eller <eller.helmut@gmail.com>, Emacs Devel <emacs-devel@gnu.org>
> 
> > 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...

So far, I had fewer weird bugs than on GNU/Linux.  Most probably
because there are no signals on Windows, only exceptions.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Eli Zaretskii <eliz@gnu.org>,  Helmut Eller <eller.helmut@gmail.com>,
>   Emacs Devel <emacs-devel@gnu.org>
> Date: Tue, 02 Jul 2024 13:36:38 +0200
> 
> Gerd Möllmann <gerd.moellmann@gmail.com> writes:
> 
> > I think they said somewhere it was done on Win32, but I can't find it at
> > the moment.
> 
> Found it:
> 
>   Emulation of accesses to protected objects happens when all of the
>   following are true:
> 
>   The object is a weak object allocated in an AWL pool.
>   
>   The MPS is running on Linux/IA-32 or Windows/IA-32. Extending this
>   list to new (reasonable) operating systems should be tolerable (for
>   example, macOS/IA-32). Extending this to new processor architectures
>   requires more work.
>   
>   The processor instruction that is accessing the object is of a
>   suitable simple form. The MPS doesn’t contain an emulator for all
>   possible instructions that might access memory, so currently it only
>   recognizes and emulates a simple MOV from memory to a register or
>   vice-versa.

Do we even use weak objects in Emacs on this branch?  If we do, what
do we use them for?

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

> Do we even use weak objects in Emacs on this branch?  If we do, what
> do we use them for?

Yes, Pip's weak hash tables, and vectors for BUF_MARKERS.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  emacs-devel@gnu.org
> Date: Tue, 02 Jul 2024 15:16:54 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Do we even use weak objects in Emacs on this branch?  If we do, what
> > do we use them for?
> 
> Yes, Pip's weak hash tables, and vectors for BUF_MARKERS.

So I guess they will work better in the 32-bit builds than in the
64-bit ones?  Because AFAIU what that text says is that they
implemented this feature only in the IA-32 builds, and in the other
cases the behavior is sub-optimal.

Re: MPS: weak hash tables

[Mattias Engdegård]

2 juli 2024 kl. 08.23 skrev Pip Cet <pipcet@protonmail.com>:

>> key/value pairs are then removed from a hash table when
>> 
>> Weakness Predicate
>> ----------------------------------------
>> key W(key)
>> value W(value)
>> key-and-value W(key) and W(value),
>> key-or-value W(key) or W(value).
> 
> Hmm. I think I have key-and-value and key-or-value reversed, then...

No, you are right and Gerd's table is wrong. See keep_entry_p in fns.c.
With `key-and-value`, entries are kept iff both key and value have strong references.

(I haven't followed the rest of the thread at all; this just caught my eye.)

Re: MPS: weak hash tables

[Pip Cet]

On Tuesday, July 2nd, 2024 at 13:42, Eli Zaretskii <eliz@gnu.org> wrote:
> > From: Gerd Möllmann gerd.moellmann@gmail.com
> 
> > Cc: pipcet@protonmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > Date: Tue, 02 Jul 2024 15:16:54 +0200
> > 
> > Eli Zaretskii eliz@gnu.org writes:
> > 
> > > Do we even use weak objects in Emacs on this branch? If we do, what
> > > do we use them for?
> > 
> > Yes, Pip's weak hash tables, and vectors for BUF_MARKERS.
> 
> So I guess they will work better in the 32-bit builds than in the
> 64-bit ones? Because AFAIU what that text says is that they
> implemented this feature only in the IA-32 builds, and in the other
> cases the behavior is sub-optimal.

The code needs fixing for IA-32, and will conceivably be a little faster on those machines than it is on 64-bit machines. This will probably be noticeable only for very large hash tables, but may be noticeable for normal numbers of markers in a buffer.

Having looked at the MPS code, and sorry for being verbose:

* all this is relevant to large objects, which MPS's design doesn't really favor. For strong references, you scan an entire object or none of it. This is a potential problem since Emacs can have very large objects.
* For weak references, it's even worse, because when you scan an entire object to satisfy a client request to it (which triggered a protection signal), MPS uses a "strong" scan and doesn't splat any references.
* so, only for weak references, and only when certain CPU instructions are used, and only on 32-bit x86 machines (there's some code for x86-64 and aarch64, as well as macOS, but not enough to actually do anything) on Windows and Linux, there's a special optimization which avoids scanning the entire object: a machine instruction is simulated.
* Since the point is to avoid calling the scan function for the entire object, MPS needs a different algorithm to decide whether the word is a weak (exact) reference, or plain old data that doesn't refer to anything.
* They decided to treat all multiple-of-four values (except for 0) as references, and all with a remainder when divided by four as non-references. That clashes with our usual Lisp_Object convention, but miraculously works out for fixnums, whose integer value is congruent to 2 modulo 4. No, I don't know why they didn't use a special sub-scan function which takes a range into the object (possibly they don't remember object starts at all?)

That means we must do one of the following:

1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
2. not use 32-bit x86 machines
3. modify MPS
4. throw caution to the wind and just hope it works

I started implementing (1) (which is why the hashes are now fixnums rather than uint32_t), then realized I was doing (2). I looked at MPS and the modifications to disable this code, while trivial, cannot be performed without rebuilding the library. And, yes, I'm afraid on 32-bit x86 we're currently using option (4), which is very annoying.

I'm not at all sure what the right thing to do is in our present situation. I'm not opposed to mangling Lisp_Objects, provided we can revise struct igc_header to contain the three Emacs tag bits directly. However, performance of large weak hash tables will be poor on all machines.

Any advice would be appreciated.

Pip

Re: MPS: weak hash tables

[Helmut Eller]

On Tue, Jul 02 2024, Pip Cet wrote:

> Any advice would be appreciated.

You could store a reference as two cells: the untagged pointer in the
first and the tag encoded as fixnum in the second.  Or pack the tag into
one of the parallel arrays.

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Tue, 02 Jul 2024 15:03:44 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: Gerd Möllmann <gerd.moellmann@gmail.com>, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> That means we must do one of the following:
> 
> 1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
> 2. not use 32-bit x86 machines
> 3. modify MPS
> 4. throw caution to the wind and just hope it works

I don't understand why (1) is needed.  Lisp objects are already
pointers in disguise, so what exactly is the problem here?

I also don't understand how come an _optimization_ turned out to do us
some harm.

Re: MPS: weak hash tables

[Pip Cet]

On Tuesday, July 2nd, 2024 at 15:35, Eli Zaretskii <eliz@gnu.org> wrote:
> > Date: Tue, 02 Jul 2024 15:03:44 +0000
> 
> > From: Pip Cet pipcet@protonmail.com
> > Cc: Gerd Möllmann gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > 
> > That means we must do one of the following:
> > 
> > 1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
> > 2. not use 32-bit x86 machines
> > 3. modify MPS
> > 4. throw caution to the wind and just hope it works
> I don't understand why (1) is needed. Lisp objects are already
> pointers in disguise, so what exactly is the problem here?

They need to be aligned for MPS to understand they're pointers; they're unaligned, except for symbols which aren't pointers in the first place.  In essence, MPS was focusing on the wrong language (for us).

> I also don't understand how come an optimization turned out to do us
> some harm.

Isn't that quite common, really?

That said, I really like Helmut's idea, though I'm trying to simplify it further to dumb it down to my level.

Is it okay if I install the changes for Ihor's bugs first, then fix IA32? I still need to do some work to make sure they build without any unnecessary overhead in the !HAVE_MPS case.

Pip

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Tue, 02 Jul 2024 16:34:40 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> > > 1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
> > > 2. not use 32-bit x86 machines
> > > 3. modify MPS
> > > 4. throw caution to the wind and just hope it works
> > I don't understand why (1) is needed. Lisp objects are already
> > pointers in disguise, so what exactly is the problem here?
> 
> They need to be aligned for MPS to understand they're pointers; they're unaligned, except for symbols which aren't pointers in the first place.  In essence, MPS was focusing on the wrong language (for us).

The pointers we hide in Lisp objects are already aligned.  Why cannot
we use them directly?

> > I also don't understand how come an optimization turned out to do us
> > some harm.
> 
> Isn't that quite common, really?

Not in my book, no.

> Is it okay if I install the changes for Ihor's bugs first, then fix IA32? I still need to do some work to make sure they build without any unnecessary overhead in the !HAVE_MPS case.

It doesn't matter in what order things are fixed as long as they are
fixed.

Re: MPS: weak hash tables

[Pip Cet]

On Tuesday, July 2nd, 2024 at 18:20, Eli Zaretskii <eliz@gnu.org> wrote:
> > Date: Tue, 02 Jul 2024 16:34:40 +0000
> 
> > From: Pip Cet pipcet@protonmail.com
> > Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > 
> > > > 1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
> > > > 2. not use 32-bit x86 machines
> > > > 3. modify MPS
> > > > 4. throw caution to the wind and just hope it works
> > > > I don't understand why (1) is needed. Lisp objects are already
> > > > pointers in disguise, so what exactly is the problem here?
> > 
> > They need to be aligned for MPS to understand they're pointers; they're unaligned, except for symbols which aren't pointers in the first place. In essence, MPS was focusing on the wrong language (for us).
> 
> The pointers we hide in Lisp objects are already aligned. Why cannot
> we use them directly?

We need to store the tag somewhere, and I'm not entirely sure it's okay for the pointer to be anything but an MPS base pointer, which is a struct igc_header *, not, say, a struct Lisp_Cons *. I'll go check the docs again.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Tue, Jul 02 2024, Pip Cet wrote:
>
>> 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).
>
> Why do you think that the restriction only applies to 32-bit systems?
> My interpretation of
>
>   Section 7.4. Caution
>   ...
>   “Aligned pointer” means a word whose numeric value (that is, its value
>   when treated as an unsigned integer) is a multiple of the size of a
>   pointer. If you’re using a 64-bit architecture, that means that an
>   aligned pointer is a multiple of 8 and its bottom three bits are zero.
>   ...
>
> is that it applies to 64-bit machines as well.

OTOH, when I see this in a bit broader context, namely

  7.3
  ...
  
  Emulation of accesses to protected objects happens when all of the
  following are true:

  The object is a weak object allocated in an AWL pool.
  
  The MPS is running on Linux/IA-32 or Windows/IA-32. Extending this
  list to new (reasonable) operating systems should be tolerable (for
  example, macOS/IA-32). Extending this to new processor architectures
  requires more work.
  
  The processor instruction that is accessing the object is of a
  suitable simple form. The MPS doesn’t contain an emulator for all
  possible instructions that might access memory, so currently it only
  recognizes and emulates a simple MOV from memory to a register or
  vice-versa.
  
  Contact us if you need emulation of access to weak references for new
  operating systems, processor architectures, or memory access
  instructions.

  7.4. Caution

  Because of the instruction emulation described in Protection faults
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  above, AWL places the following restriction on the format of objects
  allocated in it:

  Each slot in an object must either be a valid word-aligned reference,
  or else the bottom bits of the word must be non-zero so that it does
  not look like an aligned pointer.

  “Aligned pointer” means...

I'd bet that these restrictions don't matter when emulation is not done,
which is the case for 64 bit processors, not IA32 etc. And indeed, on my
machine with arm64 splatting in the marker vectors works just fine.

I can understand that Ravenbrook documents these restrictions, for
future (payed) developments and so on, but, you know... implementing
them gets pretty ugly pretty quickly. (And I wonder if the emulation
brings enough to warrant the effort.)

It would be nice if the ugliness could be encapsulated so that one
doesn't have to see it all the time, as far as that it possible in C
:-). Or conditionalized, maybe, because with Helmut's idea (which I find
the right one), we're using and additional word for weak references.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> Date: Tue, 02 Jul 2024 16:34:40 +0000
>> From: Pip Cet <pipcet@protonmail.com>
>> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
>> 
>> > > 1. mangle all Lisp_Objects to pointers or fixnums when storing them in a weak hash table, and unmangle them upon retrieval
>> > > 2. not use 32-bit x86 machines
>> > > 3. modify MPS
>> > > 4. throw caution to the wind and just hope it works
>> > I don't understand why (1) is needed. Lisp objects are already
>> > pointers in disguise, so what exactly is the problem here?
>> 
>> They need to be aligned for MPS to understand they're pointers;
>> they're unaligned, except for symbols which aren't pointers in the
>> first place. In essence, MPS was focusing on the wrong language (for
>> us).
>
> The pointers we hide in Lisp objects are already aligned.  Why cannot
> we use them directly?

Please read

  https://memory-pool-system.readthedocs.io/en/latest/pool/awl.html#

Chapter 7.3 Software emulation, and 7.4 Cautions.

Re: MPS: weak hash tables

[Pip Cet]

On Wednesday, July 3rd, 2024 at 06:11, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Helmut Eller eller.helmut@gmail.com writes:
> > On Tue, Jul 02 2024, Pip Cet wrote:
> > 
> > > 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).
> > 
> > Why do you think that the restriction only applies to 32-bit systems?
> > My interpretation of
> > 
> > Section 7.4. Caution
> > ...
> > “Aligned pointer” means a word whose numeric value (that is, its value
> > when treated as an unsigned integer) is a multiple of the size of a
> > pointer. If you’re using a 64-bit architecture, that means that an
> > aligned pointer is a multiple of 8 and its bottom three bits are zero.
> > ...
> > 
> > is that it applies to 64-bit machines as well.
> 
> 
> OTOH, when I see this in a bit broader context, namely
> 
> 7.3
> ...
> 
> Emulation of accesses to protected objects happens when all of the
> following are true:
> 
> The object is a weak object allocated in an AWL pool.
> 
> The MPS is running on Linux/IA-32 or Windows/IA-32. Extending this
> list to new (reasonable) operating systems should be tolerable (for
> example, macOS/IA-32). Extending this to new processor architectures
> requires more work.
> 
> The processor instruction that is accessing the object is of a
> suitable simple form. The MPS doesn’t contain an emulator for all
> possible instructions that might access memory, so currently it only
> recognizes and emulates a simple MOV from memory to a register or
> vice-versa.
> 
> Contact us if you need emulation of access to weak references for new
> operating systems, processor architectures, or memory access
> instructions.
> 
> 7.4. Caution
> 
> Because of the instruction emulation described in Protection faults
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> above, AWL places the following restriction on the format of objects
> allocated in it:
> 
> Each slot in an object must either be a valid word-aligned reference,
> or else the bottom bits of the word must be non-zero so that it does
> not look like an aligned pointer.
> 
> “Aligned pointer” means...
> 
> I'd bet that these restrictions don't matter when emulation is not done,
> which is the case for 64 bit processors, not IA32 etc. And indeed, on my
> machine with arm64 splatting in the marker vectors works just fine.
> 
> I can understand that Ravenbrook documents these restrictions, for
> future (payed) developments and so on, but, you know... implementing
> them gets pretty ugly pretty quickly. (And I wonder if the emulation
> brings enough to warrant the effort.)

Frankly, I wonder how they'd feel about a patch to make emulation optional on all architectures, so the restrictions would be optional as well. I'm playing with a qemu IA32 environment, but haven't been able to trigger the emulation code yet (even on IA32, only some very simple instructions are emulated).

I've run into another issue: finalization. MPS's take on that is rather unusual, in that an object can be "finalized" while weak references to it still exist (and destruction can be vetoed by the finalization code creating a new strong reference to it, IIUC). The upshot of this is that this code:

(setq bignum (1+ most-positive-fixnum))
(setq table (make-hash-table :test 'eq :weakness 'key))
(puthash bignum t table)
table
(setq bignum nil)
(setq values nil)
(igc--collect)
table

produces a table with a nonsensical/random bignum as key, because the memory has been freed and reused for something else.

I have a patch here which "splats" finalized pvecs so they become PVEC_FREE, ignores such objects during iteration, and gets rid of the "count" element, instead counting the elements for (hash-table-count weak-table). I'll install it after some more testing, unless a better solution occurs to someone.

> It would be nice if the ugliness could be encapsulated so that one
> doesn't have to see it all the time, as far as that it possible in C
> :-). Or conditionalized, maybe, because with Helmut's idea (which I find
> the right one), we're using and additional word for weak references.

How hard would it be to "just" add struct igc_headers to the remaining non-headered objects? I don't really want to reopen the "get rid of pure space" discussion again, but that's probably the hard part?

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> I can understand that Ravenbrook documents these restrictions, for
>> future (payed) developments and so on, but, you know... implementing
>> them gets pretty ugly pretty quickly. (And I wonder if the emulation
>> brings enough to warrant the effort.)
>
> Frankly, I wonder how they'd feel about a patch to make emulation
> optional on all architectures, so the restrictions would be optional
> as well. I'm playing with a qemu IA32 environment, but haven't been
> able to trigger the emulation code yet (even on IA32, only some very
> simple instructions are emulated).

Right, they say themselves that only simple instructions are handled.

Hm, one could try. Maybe you could submit an issue for that on their
github project? The only "problem" is see is that they are not very
responsive. Not that they aren't very friendly and so on, it just takes
them some time to react, and sometimes they don't.

(When I sent a mail to info@ravenbrook.com some months ago to make them
aware that something in Emacs is going on wrt MPS and to thank them for
MPS (couldn't find another address), someone told me that Ravenbrook
isn't that large anymore, or something like that. My guess is that they
are getting old, too. I think MPS had its first release, commercial,
in 1997.)

> I've run into another issue: finalization. MPS's take on that is
> rather unusual, in that an object can be "finalized" while weak
> references to it still exist (and destruction can be vetoed by the
> finalization code creating a new strong reference to it, IIUC). The
> upshot of this is that this code:
>
> (setq bignum (1+ most-positive-fixnum))
> (setq table (make-hash-table :test 'eq :weakness 'key))
> (puthash bignum t table)
> table
> (setq bignum nil)
> (setq values nil)
> (igc--collect)
> table
>
> produces a table with a nonsensical/random bignum as key, because the
> memory has been freed and reused for something else.
>
> I have a patch here which "splats" finalized pvecs so they become
> PVEC_FREE, ignores such objects during iteration, and gets rid of the
> "count" element, instead counting the elements for (hash-table-count
> weak-table). I'll install it after some more testing, unless a better
> solution occurs to someone.

I have a vague memory that the docs say somewhere that a finalizer can
decline finalization by creating a strong reference, but I can't find it
anymore, as usual. Could we use that somehow, maybe?

>
>> It would be nice if the ugliness could be encapsulated so that one
>> doesn't have to see it all the time, as far as that it possible in C
>> :-). Or conditionalized, maybe, because with Helmut's idea (which I find
>> the right one), we're using and additional word for weak references.
>
> How hard would it be to "just" add struct igc_headers to the remaining
> non-headered objects? I don't really want to reopen the "get rid of
> pure space" discussion again, but that's probably the hard part?

I'd say it's not hard to add the headers to pure space. (Let me briefly
sprinkle in that pure space should die :-)). There is a function
pure_alloc that is used to allocate objects in pure space, AFAIK.

For lispsym, main_threads, and subrs (DEFUN etc.), one would have to
create static structs with an igc_header member. That's probably also
not really difficult but could result in a lot of work.

And of course igc_header would have to be made visible everywhere, and
so on. A lot of work...

Re: MPS: weak hash tables

[Helmut Eller]

On Wed, Jul 03 2024, Gerd Möllmann wrote:

> Hm, one could try. Maybe you could submit an issue for that on their
> github project? The only "problem" is see is that they are not very
> responsive. Not that they aren't very friendly and so on, it just takes
> them some time to react, and sometimes they don't.

Or ask on the mailing list.  Just to see how responsive that is.

https://mailman.ravenbrook.com/mailman/listinfo/mps-discussion

Re: MPS: weak hash tables

[Pip Cet]

On Wednesday, July 3rd, 2024 at 07:04, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > > I can understand that Ravenbrook documents these restrictions, for
> > > future (payed) developments and so on, but, you know... implementing
> > > them gets pretty ugly pretty quickly. (And I wonder if the emulation
> > > brings enough to warrant the effort.)
> > 
> > Frankly, I wonder how they'd feel about a patch to make emulation
> > optional on all architectures, so the restrictions would be optional
> > as well. I'm playing with a qemu IA32 environment, but haven't been
> > able to trigger the emulation code yet (even on IA32, only some very
> > simple instructions are emulated).
> 
> Right, they say themselves that only simple instructions are handled.
> 
> Hm, one could try. Maybe you could submit an issue for that on their
> github project? The only "problem" is see is that they are not very
> responsive. Not that they aren't very friendly and so on, it just takes
> them some time to react, and sometimes they don't.

I believe we should leave our options open as far as modifying MPS goes: my understanding is we could, if we really wanted to (but IANAL), but I'd strongly prefer to discuss that only if and when scratch/igc is merged. Everything else is premature.

> (When I sent a mail to info@ravenbrook.com some months ago to make them
> aware that something in Emacs is going on wrt MPS and to thank them for
> MPS (couldn't find another address), someone told me that Ravenbrook
> isn't that large anymore, or something like that. My guess is that they
> are getting old, too. I think MPS had its first release, commercial,
> in 1997.)
> 
> > I've run into another issue: finalization. MPS's take on that is
> > rather unusual, in that an object can be "finalized" while weak
> > references to it still exist (and destruction can be vetoed by the
> > finalization code creating a new strong reference to it, IIUC). The
> > upshot of this is that this code:
> > 
> > (setq bignum (1+ most-positive-fixnum))
> > (setq table (make-hash-table :test 'eq :weakness 'key))
> > (puthash bignum t table)
> > table
> > (setq bignum nil)
> > (setq values nil)
> > (igc--collect)
> > table
> > 
> > produces a table with a nonsensical/random bignum as key, because the
> > memory has been freed and reused for something else.
> > 
> > I have a patch here which "splats" finalized pvecs so they become
> > PVEC_FREE, ignores such objects during iteration, and gets rid of the
> > "count" element, instead counting the elements for (hash-table-count
> > weak-table). I'll install it after some more testing, unless a better
> > solution occurs to someone.
> 
> I have a vague memory that the docs say somewhere that a finalizer can
> decline finalization by creating a strong reference, but I can't find it
> anymore, as usual. Could we use that somehow, maybe?

https://memory-pool-system.readthedocs.io/en/latest/topic/finalization.html#topic-finalization:

The client program may choose to keep the finalized block alive by keeping a strong reference to the finalized object after discarding the finalization message.

This process is known as resurrection and in some finalization systems requires special handling, but in the MPS this just is just the usual result of the rule that strong references keep objects alive.


We could use that for key-or-value hash tables, but those aren't really my priority.

I don't see a way to use it for the more usual weak hash tables, but maybe I'm missing something.

> > > It would be nice if the ugliness could be encapsulated so that one
> > > doesn't have to see it all the time, as far as that it possible in C
> > > :-). Or conditionalized, maybe, because with Helmut's idea (which I find
> > > the right one), we're using and additional word for weak references.
> > 
> > How hard would it be to "just" add struct igc_headers to the remaining
> > non-headered objects? I don't really want to reopen the "get rid of
> > pure space" discussion again, but that's probably the hard part?
> 
> I'd say it's not hard to add the headers to pure space. (Let me briefly
> sprinkle in that pure space should die :-)). There is a function
> pure_alloc that is used to allocate objects in pure space, AFAIK.

git merge scratch/no-purespace :-)

> For lispsym, main_threads, and subrs (DEFUN etc.), one would have to
> create static structs with an igc_header member. That's probably also
> not really difficult but could result in a lot of work.
> 
> And of course igc_header would have to be made visible everywhere, and
> so on. A lot of work...

You're right. I think Helmut's idea is great, actually, and I don't mind the extra cost for now. Large weak hash tables are expensive, and memory is the least of that problem.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> I believe we should leave our options open as far as modifying MPS
> goes: my understanding is we could, if we really wanted to (but
> IANAL),

IANAL either, but I think one could:

 This is the license under which the Memory Pool System Kit is made
 available by Ravenbrook Limited. This license is generally known as
 the `BSD 2-clause license`_.  It is `GPL compatible`_ and
 `OSI approved`_.

> but I'd strongly prefer to discuss that only if and when scratch/igc
> is merged. Everything else is premature.

Ok.

>> I have a vague memory that the docs say somewhere that a finalizer can
>> decline finalization by creating a strong reference, but I can't find it
>> anymore, as usual. Could we use that somehow, maybe?
>
> https://memory-pool-system.readthedocs.io/en/latest/topic/finalization.html#topic-finalization:
>
> The client program may choose to keep the finalized block alive by keeping a strong reference to the finalized object after discarding the finalization message.
>
> This process is known as resurrection and in some finalization systems
> requires special handling, but in the MPS this just is just the usual
> result of the rule that strong references keep objects alive.

Thanks.

> We could use that for key-or-value hash tables, but those aren't
> really my priority.
>
> I don't see a way to use it for the more usual weak hash tables, but
> maybe I'm missing something.

Ok, maybe if we let it ripe a bit, an idea emerges.

>> > > It would be nice if the ugliness could be encapsulated so that one
>> > > doesn't have to see it all the time, as far as that it possible in C
>> > > :-). Or conditionalized, maybe, because with Helmut's idea (which I find
>> > > the right one), we're using and additional word for weak references.
>> > 
>> > How hard would it be to "just" add struct igc_headers to the remaining
>> > non-headered objects? I don't really want to reopen the "get rid of
>> > pure space" discussion again, but that's probably the hard part?
>> 
>> I'd say it's not hard to add the headers to pure space. (Let me briefly
>> sprinkle in that pure space should die :-)). There is a function
>> pure_alloc that is used to allocate objects in pure space, AFAIK.
>
> git merge scratch/no-purespace :-)

Long done, in a repos lightyears away :-).

Re: MPS: weak hash tables

[Gerd Möllmann]

The PVEC_FREE lead to an abort, which I think I fixed. Please pull.

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 438 bytes --]

On Wednesday, July 3rd, 2024 at 08:26, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> The PVEC_FREE lead to an abort, which I think I fixed. Please pull.

Thanks, sorry for missing that!

So I've implemented Helmut's idea, but it's turned out uglier than I thought it would...

And of course the same needs to be done for the marker vector, right?

Just thinking about a different idea, but it's not quite there yet...

Pip

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Use-two-words-for-each-entry-in-a-weak-hash-table.patch --]
[-- Type: text/x-patch; name=0001-Use-two-words-for-each-entry-in-a-weak-hash-table.patch, Size: 15861 bytes --]

From 0e2b417953fc578c819f31ee9e5b911cf827ffbf Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Wed, 3 Jul 2024 09:22:03 +0000
Subject: [PATCH] Use two words for each entry in a weak hash table

---
 src/fns.c   |  36 ++++++++++--------
 src/igc.c   | 106 ++++++++++++++++++++++++++++++++++++++++++++++++----
 src/lisp.h  |  41 ++++++++++----------
 src/print.c |   2 +
 4 files changed, 142 insertions(+), 43 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 250cf6c3a7e..ad111dd6708 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -5415,19 +5415,19 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool remove_entries_p)
 set_weak_hash_next_slot (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  h->strong->next[idx].lisp_object = make_fixnum (val);
+  h->strong->next[idx] = make_weak_hash_table_entry (make_fixnum (val));
 }
 static void
 set_weak_hash_hash_slot (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx, hash_hash_t val)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  h->strong->hash[idx].lisp_object = make_fixnum (val);
+  h->strong->hash[idx] = make_weak_hash_table_entry (make_fixnum (val));
 }
 static void
 set_weak_hash_index_slot (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx, ptrdiff_t val)
 {
   eassert (idx >= 0 && idx < weak_hash_table_index_size (h));
-  h->strong->index[idx].lisp_object = make_fixnum (val);
+  h->strong->index[idx] = make_weak_hash_table_entry (make_fixnum (val));
 }
 
 static struct Lisp_Weak_Hash_Table *
@@ -5442,14 +5442,14 @@ check_maybe_weak_hash_table (Lisp_Object obj)
 WEAK_HASH_NEXT (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  return XFIXNUM (h->strong->next[idx].lisp_object);
+  return XFIXNUM (weak_hash_table_entry (h->strong->next[idx]));
 }
 
 static ptrdiff_t
 WEAK_HASH_INDEX (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 {
   eassert (idx >= 0 && idx < weak_hash_table_index_size (h));
-  return XFIXNUM (h->strong->index[idx].lisp_object);
+  return XFIXNUM (weak_hash_table_entry (h->strong->index[idx]));
 }
 
 static struct Lisp_Weak_Hash_Table *
@@ -5547,19 +5547,22 @@ make_weak_hash_table (const struct hash_table_test *test, EMACS_INT size,
     {
       for (ptrdiff_t i = 0; i < size; i++)
 	{
-	  h->strong->key[i].lisp_object = HASH_UNUSED_ENTRY_KEY;
-	  h->strong->value[i].ptr = 0;
+	  h->strong->key[i] =
+	    make_weak_hash_table_entry (HASH_UNUSED_ENTRY_KEY);
+	  h->strong->value[i] =
+	    make_weak_hash_table_entry (Qnil);
 	}
 
       for (ptrdiff_t i = 0; i < size - 1; i++)
-	h->strong->next[i].lisp_object = make_fixnum(i + 1);
-      h->strong->next[size - 1].lisp_object = make_fixnum(-1);
+	h->strong->next[i] = make_weak_hash_table_entry (make_fixnum(i + 1));
+      h->strong->next[size - 1] =
+	make_weak_hash_table_entry (make_fixnum(-1));
 
       int index_bits = compute_hash_index_bits (size);
       h->strong->index_bits = make_fixnum (index_bits);
       ptrdiff_t index_size = weak_hash_table_index_size (h);
       for (ptrdiff_t i = 0; i < index_size; i++)
-	h->strong->index[i].lisp_object = make_fixnum (-1);
+	h->strong->index[i] = make_weak_hash_table_entry (make_fixnum (-1));
 
       h->strong->next_free = make_fixnum (0);
     }
@@ -5626,18 +5629,19 @@ maybe_resize_weak_hash_table (struct Lisp_Weak_Hash_Table *h)
 	}
 
       for (ptrdiff_t i = 0; i < new_size - 1; i++)
-	strong->next[i].lisp_object = make_fixnum (i + 1);
-      strong->next[new_size - 1].lisp_object = make_fixnum (-1);
+	strong->next[i] = make_weak_hash_table_entry (make_fixnum (i + 1));
+      strong->next[new_size - 1] =
+	make_weak_hash_table_entry (make_fixnum (-1));
 
       for (ptrdiff_t i = 0; i < new_size; i++)
 	{
-	  strong->key[i].lisp_object = HASH_UNUSED_ENTRY_KEY;
-	  strong->value[i].lisp_object = Qnil;
+	  strong->key[i] = make_weak_hash_table_entry (HASH_UNUSED_ENTRY_KEY);
+	  strong->value[i] = make_weak_hash_table_entry (Qnil);
 	}
 
       ptrdiff_t index_size = (ptrdiff_t)1 << index_bits;
       for (ptrdiff_t i = 0; i < index_size; i++)
-	strong->index[i].lisp_object = make_fixnum (-1);
+	strong->index[i] = make_weak_hash_table_entry (make_fixnum (-1));
 
       strong->index_bits = make_fixnum (index_bits);
       strong->table_size = make_fixnum (new_size);
@@ -5801,7 +5805,7 @@ weak_hash_clear (struct Lisp_Weak_Hash_Table *h)
 
   ptrdiff_t index_size = weak_hash_table_index_size (h);
   for (ptrdiff_t i = 0; i < index_size; i++)
-    h->strong->index[i].lisp_object = make_fixnum (-1);
+    h->strong->index[i] = make_weak_hash_table_entry (make_fixnum (-1));
 
   h->strong->next_free = make_fixnum (0);
 }
diff --git a/src/igc.c b/src/igc.c
index 1b1e69ede5d..efb8106d139 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -281,6 +281,8 @@ is_builtin_subr (enum igc_obj_type type, void *client)
 static bool
 has_header (void *client, bool is_vector)
 {
+  if (client == NULL)
+    return false;
   if (is_vector && is_builtin_subr (IGC_OBJ_VECTOR, client))
     return false;
   if (c_symbol_p (client))
@@ -912,6 +914,28 @@ fix_raw (mps_ss_t ss, mps_addr_t *p)
   return MPS_RES_OK;
 }
 
+static mps_res_t
+fix_base (mps_ss_t ss, mps_addr_t *p)
+{
+  MPS_SCAN_BEGIN (ss)
+  {
+    mps_addr_t base = *p;
+    if (base == NULL)
+      return MPS_RES_OK;
+    if (is_aligned (base))
+      {
+	if (MPS_FIX1 (ss, base))
+	  {
+	    mps_res_t res = MPS_FIX2 (ss, p);
+	    if (res != MPS_RES_OK)
+	      return res;
+	  }
+      }
+  }
+  MPS_SCAN_END (ss);
+  return MPS_RES_OK;
+}
+
 #define IGC_FIX12_OBJ(ss, p)                           \
   do                                                   \
     {                                                  \
@@ -932,6 +956,16 @@ #define IGC_FIX12_RAW(ss, p)                                     \
     }                                                            \
   while (0)
 
+#define IGC_FIX12_BASE(ss, p)						\
+  do									\
+    {									\
+      mps_res_t res;							\
+      MPS_FIX_CALL (ss, res = fix_base (ss, (mps_addr_t *) (p)));	\
+      if (res != MPS_RES_OK)						\
+	return res;							\
+    }									\
+  while (0)
+
 #define IGC_FIX12_NOBJS(ss, a, n)                            \
   do                                                         \
     {                                                        \
@@ -1917,7 +1951,7 @@ fix_weak_hash_table_strong_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Strong
 	  }
 	for (ssize_t i = 2 * XFIXNUM (t->table_size); i < limit; i++)
 	  {
-	    IGC_FIX12_OBJ (ss, &t->entries[i].lisp_object);
+	    IGC_FIX12_BASE (ss, &t->entries[i].intptr);
 	  }
       }
   }
@@ -1953,9 +1987,9 @@ fix_weak_hash_table_weak_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Weak_Par
 
 	for (ssize_t i = 0; i < limit; i++)
 	  {
-	    bool was_nil = NILP (w->entries[i].lisp_object);
-	    IGC_FIX12_OBJ (ss, &w->entries[i].lisp_object);
-	    bool is_now_nil = NILP (w->entries[i].lisp_object);
+	    bool was_nil = w->entries[i].intptr == 0;
+	    IGC_FIX12_BASE (ss, &w->entries[i].intptr);
+	    bool is_now_nil = w->entries[i].intptr == 0;
 
 	    if (is_now_nil && !was_nil)
 	      {
@@ -3813,8 +3847,63 @@ igc_make_hash_table_vec (size_t n)
   return alloc (n * sizeof (Lisp_Object), IGC_OBJ_HASH_VEC);
 }
 
+Lisp_Object
+weak_hash_table_entry (struct Lisp_Weak_Hash_Table_Entry entry)
+{
+  intptr_t alignment = entry.intptr & 1;
+  mps_addr_t client;
+
+  if (alignment == 0)
+    {
+      client = base_to_client ((mps_addr_t)entry.intptr);
+    }
+  else
+    {
+      intptr_t real_ptr = entry.intptr ^ alignment;
+      client = (mps_addr_t)real_ptr;
+    }
+
+  switch (XFIXNUM (entry.fixnum))
+    {
+    case Lisp_Symbol:
+      return make_lisp_symbol (client);
+    case_Lisp_Int:
+      return make_fixnum (entry.intptr >> 1);
+    default:
+      return make_lisp_ptr (client, XFIXNUM (entry.fixnum));
+    }
+}
+
+struct Lisp_Weak_Hash_Table_Entry
+make_weak_hash_table_entry (Lisp_Object obj)
+{
+  struct Lisp_Weak_Hash_Table_Entry entry = { 0, };
+  mps_addr_t client;
+  entry.fixnum = make_fixnum (XTYPE (obj));
+
+  if (FIXNUMP (obj))
+    {
+      entry.intptr = (XFIXNUM (obj) << 1) + 1;
+      return entry;
+    }
+  else if (BARE_SYMBOL_P (obj))
+    client = XBARE_SYMBOL (obj);
+  else
+    client = XUNTAG (obj, XTYPE (obj), void);
+
+  if (has_header (client, VECTORLIKEP (obj)))
+    entry.intptr = (intptr_t)client_to_base (client);
+  else
+    {
+      entry.intptr = (intptr_t)client + 1;
+      eassert (entry.intptr & 1);
+    }
+  return entry;
+}
+
 struct Lisp_Weak_Hash_Table_Strong_Part *
-igc_alloc_weak_hash_table_strong_part (hash_table_weakness_t weak, size_t size, size_t index_bits)
+igc_alloc_weak_hash_table_strong_part (hash_table_weakness_t weak,
+				       size_t size, size_t index_bits)
 {
   size_t total_size;
   switch (weak)
@@ -3832,12 +3921,13 @@ igc_alloc_weak_hash_table_strong_part (hash_table_weakness_t weak, size_t size,
       emacs_abort ();
     }
   return alloc (sizeof (struct Lisp_Weak_Hash_Table_Strong_Part) +
-		total_size * sizeof (union Lisp_Weak_Hash_Table_Entry),
+		total_size * sizeof (struct Lisp_Weak_Hash_Table_Entry),
 		IGC_OBJ_WEAK_HASH_TABLE_STRONG_PART);
 }
 
 struct Lisp_Weak_Hash_Table_Weak_Part *
-igc_alloc_weak_hash_table_weak_part (hash_table_weakness_t weak, size_t size, size_t index_bits)
+igc_alloc_weak_hash_table_weak_part (hash_table_weakness_t weak,
+				     size_t size, size_t index_bits)
 {
   size_t total_size;
   switch (weak)
@@ -3855,7 +3945,7 @@ igc_alloc_weak_hash_table_weak_part (hash_table_weakness_t weak, size_t size, si
       emacs_abort ();
     }
   return alloc (sizeof (struct Lisp_Weak_Hash_Table_Weak_Part) +
-		total_size * sizeof (union Lisp_Weak_Hash_Table_Entry),
+		total_size * sizeof (struct Lisp_Weak_Hash_Table_Entry),
 		IGC_OBJ_WEAK_HASH_TABLE_WEAK_PART);
 }
 
diff --git a/src/lisp.h b/src/lisp.h
index 933441d3a7e..3fc55982d24 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2609,13 +2609,16 @@ #define DOOBARRAY(oa, it)					\
    (hash) indices.  It's signed and a subtype of ptrdiff_t.  */
 typedef int32_t hash_idx_t;
 
-/* The reason for this unusual union is an MPS peculiarity on 32-bit x86 systems. */
-union Lisp_Weak_Hash_Table_Entry
+/* The reason for this unusual structure is an MPS peculiarity on 32-bit x86 systems. */
+struct Lisp_Weak_Hash_Table_Entry
 {
-  void *ptr;
-  Lisp_Object lisp_object; /* must be a fixnum or HASH_UNUSED_ENTRY_KEY! */
+  intptr_t intptr; /* must be an MPS base pointer */
+  Lisp_Object fixnum; /* a fixnum indicating the tag, or just a fixnum */
 };
 
+extern Lisp_Object weak_hash_table_entry (struct Lisp_Weak_Hash_Table_Entry entry);
+extern struct Lisp_Weak_Hash_Table_Entry make_weak_hash_table_entry (Lisp_Object);
+
 struct Lisp_Weak_Hash_Table_Strong_Part
 {
   Lisp_Object index_bits;
@@ -2623,11 +2626,11 @@ #define DOOBARRAY(oa, it)					\
   Lisp_Object table_size;
   struct Lisp_Weak_Hash_Table_Weak_Part *weak;
   const struct hash_table_test *test;
-  union Lisp_Weak_Hash_Table_Entry *index; /* internal pointer */
-  union Lisp_Weak_Hash_Table_Entry *hash; /* either internal pointer or pointer to dependent object */
-  union Lisp_Weak_Hash_Table_Entry *key; /* either internal pointer or pointer to dependent object */
-  union Lisp_Weak_Hash_Table_Entry *value; /* either internal pointer or pointer to dependent object */
-  union Lisp_Weak_Hash_Table_Entry *next; /* internal pointer */
+  struct Lisp_Weak_Hash_Table_Entry *index; /* internal pointer to an all-fixnum array */
+  struct Lisp_Weak_Hash_Table_Entry *hash; /* internal pointer to an all-fixnum array */
+  struct Lisp_Weak_Hash_Table_Entry *next; /* internal pointer to an all-fixnum array */
+  struct Lisp_Weak_Hash_Table_Entry *key; /* either internal pointer or pointer to dependent object */
+  struct Lisp_Weak_Hash_Table_Entry *value; /* either internal pointer or pointer to dependent object */
   hash_table_weakness_t weakness : 3;
   hash_table_std_test_t frozen_test : 2;
 
@@ -2639,13 +2642,13 @@ #define DOOBARRAY(oa, it)					\
      pure tables are not, and while a table is being mutated it is
      immutable for recursive attempts to mutate it.  */
   bool_bf mutable : 1;
-  union Lisp_Weak_Hash_Table_Entry entries[FLEXIBLE_ARRAY_MEMBER];
+  struct Lisp_Weak_Hash_Table_Entry entries[FLEXIBLE_ARRAY_MEMBER];
 };
 
 struct Lisp_Weak_Hash_Table_Weak_Part
 {
   struct Lisp_Weak_Hash_Table_Strong_Part *strong;
-  union Lisp_Weak_Hash_Table_Entry entries[FLEXIBLE_ARRAY_MEMBER];
+  struct Lisp_Weak_Hash_Table_Entry entries[FLEXIBLE_ARRAY_MEMBER];
 };
 
 struct Lisp_Weak_Hash_Table
@@ -2860,13 +2863,13 @@ make_lisp_weak_hash_table (struct Lisp_Weak_Hash_Table *h)
 WEAK_HASH_KEY (const struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  return h->strong->key[idx].lisp_object;
+  return weak_hash_table_entry (h->strong->key[idx]);
 }
 
 INLINE Lisp_Object
 WEAK_HASH_VALUE (const struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 {
-  return h->strong->value[idx].lisp_object;
+  return weak_hash_table_entry (h->strong->value[idx]);
 }
 
 /* Value is the hash code computed for entry IDX in hash table H.  */
@@ -2874,7 +2877,7 @@ WEAK_HASH_VALUE (const struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 WEAK_HASH_HASH (const struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  return XFIXNUM (h->strong->hash[idx].lisp_object);
+  return XFIXNUM (weak_hash_table_entry (h->strong->hash[idx]));
 }
 
 /* Value is the size of hash table H.  */
@@ -2925,14 +2928,14 @@ weak_hash_from_key (struct Lisp_Weak_Hash_Table *h, Lisp_Object key)
    The body may remove the current entry or alter its value slot, but not
    mutate TABLE in any other way.  */
 # define DOHASH_WEAK(h, k, v)						\
-  for (union Lisp_Weak_Hash_Table_Entry *dohash_##k##_##v##_k = (h)->strong->key, \
+  for (struct Lisp_Weak_Hash_Table_Entry *dohash_##k##_##v##_k = (h)->strong->key, \
 	 *dohash_##k##_##v##_v = (h)->strong->value,			\
 	 *dohash_##k##_##v##_end = dohash_##k##_##v##_k			\
 	 + WEAK_HASH_TABLE_SIZE (h),					\
 	 *dohash_##k##_##v##_base = dohash_##k##_##v##_k;		\
        dohash_##k##_##v##_k < dohash_##k##_##v##_end			\
-	 && (k = dohash_##k##_##v##_k[0].lisp_object,			\
-	     v = dohash_##k##_##v##_v[0].lisp_object, /*maybe unused*/ (void)v,	\
+	 && (k = weak_hash_table_entry (dohash_##k##_##v##_k[0]),	\
+	     v = weak_hash_table_entry (dohash_##k##_##v##_v[0]),	\
            true);			                                \
        eassert (dohash_##k##_##v##_base == (h)->strong->key		\
 		&& dohash_##k##_##v##_end				\
@@ -4255,14 +4258,14 @@ set_hash_value_slot (struct Lisp_Hash_Table *h, ptrdiff_t idx, Lisp_Object val)
 set_weak_hash_key_slot (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx, Lisp_Object val)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size));
-  h->strong->key[idx].lisp_object = val;
+  h->strong->key[idx] = make_weak_hash_table_entry (val);
 }
 
 INLINE void
 set_weak_hash_value_slot (struct Lisp_Weak_Hash_Table *h, ptrdiff_t idx, Lisp_Object val)
 {
   eassert (idx >= 0 && idx < XFIXNUM (h->strong->table_size) );
-  h->strong->value[idx].lisp_object = val;
+  h->strong->value[idx] = make_weak_hash_table_entry (val);
 }
 #endif
 
diff --git a/src/print.c b/src/print.c
index fa71de8f2dd..8fd3473e5c2 100644
--- a/src/print.c
+++ b/src/print.c
@@ -2788,9 +2788,11 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
 		--print_depth;   /* Done with this.  */
 	      }
 	    goto next_obj;
+#ifdef HAVE_MPS
 	  strong_hash_table:
 	    h = XHASH_TABLE (obj);
 	    goto hash_table_data;
+#endif
 	  }
 
 #ifdef HAVE_MPS
-- 
2.45.2

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Wednesday, July 3rd, 2024 at 08:26, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> The PVEC_FREE lead to an abort, which I think I fixed. Please pull.
>
> Thanks, sorry for missing that!

Move fast and break things. Normal.

>
> So I've implemented Helmut's idea, but it's turned out uglier than I
> thought it would...

It meets my expections.

> And of course the same needs to be done for the marker vector, right?

Yep :-(.

Re: MPS: weak hash tables

[Pip Cet]

On Wednesday, July 3rd, 2024 at 10:22, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:

> 
> 
> Pip Cet pipcet@protonmail.com writes:
> 
> > On Wednesday, July 3rd, 2024 at 08:26, Gerd Möllmann gerd.moellmann@gmail.com wrote:
> > 
> > > The PVEC_FREE lead to an abort, which I think I fixed. Please pull.
> > 
> > Thanks, sorry for missing that!
> 
> 
> Move fast and break things. Normal.
> 
> > So I've implemented Helmut's idea, but it's turned out uglier than I
> > thought it would...
> 
> 
> It meets my expections.
> 
> > And of course the same needs to be done for the marker vector, right?
> 
> 
> Yep :-(.

What's somewhat irritating is how hard it is to actually make it produce an error. Only single-byte offset-mov is emulated, not mov without an offset, but that's what gcc -O0 produces...

On existing mps, we could just force AWLSegSALimit to 0 and AWLHaveSegSALimit to true, which would avoid the issue :-/

We can always go back to my weak-hash-table-for-BUF_MARKERS idea, that would reduce code duplication a little. Let me know if you'd prefer that.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> > And of course the same needs to be done for the marker vector, right?
>> 
>> 
>> Yep :-(.
>
> What's somewhat irritating is how hard it is to actually make it
> produce an error. Only single-byte offset-mov is emulated, not mov
> without an offset, but that's what gcc -O0 produces...
>
> On existing mps, we could just force AWLSegSALimit to 0 and
> AWLHaveSegSALimit to true, which would avoid the issue :-/
>
> We can always go back to my weak-hash-table-for-BUF_MARKERS idea, that
> would reduce code duplication a little. Let me know if you'd prefer
> that.

I don't think that would make much sense to get rid of the vector. At
the moment, with O(1) add/remove it's pretty optimal, even better than
unchain_marker which is O(N). And the marker stuff is used really often.

But I'm only speaking for myself. If it's easier to support IA32 that
way, please feel free. I'm fine with it, really, not the least because
I'm using some other Emacs :-).

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Pip Cet <pipcet@protonmail.com>,  eller.helmut@gmail.com,
>   emacs-devel@gnu.org
> Date: Wed, 03 Jul 2024 08:30:17 +0200
> 
> >> They need to be aligned for MPS to understand they're pointers;
> >> they're unaligned, except for symbols which aren't pointers in the
> >> first place. In essence, MPS was focusing on the wrong language (for
> >> us).
> >
> > The pointers we hide in Lisp objects are already aligned.  Why cannot
> > we use them directly?
> 
> Please read
> 
>   https://memory-pool-system.readthedocs.io/en/latest/pool/awl.html#
> 
> Chapter 7.3 Software emulation, and 7.4 Cautions.

Which part of it says something different from what I proposed above?

The text says:

     The bottom line is that references from an object in an AWL pool
     must be untagged and aligned, and integers must be tagged with a
     non-zero tag.

Isn't that what I asked about above?

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: Pip Cet <pipcet@protonmail.com>,  eller.helmut@gmail.com,
>>   emacs-devel@gnu.org
>> Date: Wed, 03 Jul 2024 08:30:17 +0200
>> 
>> >> They need to be aligned for MPS to understand they're pointers;
>> >> they're unaligned, except for symbols which aren't pointers in the
>> >> first place. In essence, MPS was focusing on the wrong language (for
>> >> us).
>> >
>> > The pointers we hide in Lisp objects are already aligned.  Why cannot
>> > we use them directly?
>> 
>> Please read
>> 
>>   https://memory-pool-system.readthedocs.io/en/latest/pool/awl.html#
>> 
>> Chapter 7.3 Software emulation, and 7.4 Cautions.
>
> Which part of it says something different from what I proposed above?
>
> The text says:
>
>      The bottom line is that references from an object in an AWL pool
>      must be untagged and aligned, and integers must be tagged with a
>      non-zero tag.
>
> Isn't that what I asked about above?

I've read that as "why can't we use the Lisp_Objects directly", sorry.
We're loosing the Lisp_Type then, of course.

Re: MPS: weak hash tables

[Pip Cet]

On Wednesday, July 3rd, 2024 at 10:22, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
>
> > On Wednesday, July 3rd, 2024 at 08:26, Gerd Möllmann gerd.moellmann@gmail.com wrote:
> >
> > > The PVEC_FREE lead to an abort, which I think I fixed. Please pull.
> >
> > Thanks, sorry for missing that!
>
>
> Move fast and break things. Normal.

I'm afraid I've continued to do so. After the last push, my TODO list is down to:

* fix bugs that slipped through (well, obviously)
* user-defined hash table tests for weak tables don't work
* key-or-value weakness doesn't work

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Wednesday, July 3rd, 2024 at 10:22, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> Pip Cet pipcet@protonmail.com writes:
>>
>> > On Wednesday, July 3rd, 2024 at 08:26, Gerd Möllmann gerd.moellmann@gmail.com wrote:
>> >
>> > > The PVEC_FREE lead to an abort, which I think I fixed. Please pull.
>> >
>> > Thanks, sorry for missing that!
>>
>>
>> Move fast and break things. Normal.
>
> I'm afraid I've continued to do so. After the last push, 

Did that too yesterday for --enable-checking. and had to revert now :-)

> my TODO list is down to:
>
> * fix bugs that slipped through (well, obviously)
> * user-defined hash table tests for weak tables don't work
> * key-or-value weakness doesn't work
>

I'm making another pass over C files in alpabetical order, trying to
find untraced references. At the source file I'm using (no Gtk and so
on). Now at buffer.c, and I think I see one.

Re: MPS: weak hash tables

[Helmut Eller]

On Wed, Jul 03 2024, Pip Cet wrote:

> And of course the same needs to be done for the marker vector, right?

It also needs to be done for the headers, right?  I mean, the last
significant bits of the igc_header must be non-zero.

Re: MPS: weak hash tables

[Pip Cet]

On Thursday, July 4th, 2024 at 07:17, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> > > Move fast and break things. Normal.
> > 
> > I'm afraid I've continued to do so. After the last push,
> 
> Did that too yesterday for --enable-checking. and had to revert now :-)

> > my TODO list is down to:
> > 
> > * fix bugs that slipped through (well, obviously)
> > * user-defined hash table tests for weak tables don't work
> > * key-or-value weakness doesn't work

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.

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

> I'm making another pass over C files in alpabetical order, trying to
> find untraced references. At the source file I'm using (no Gtk and so
> on). Now at buffer.c, and I think I see one.

Good luck!

Pip

Re: MPS: weak hash tables

[Pip Cet]

On Thursday, July 4th, 2024 at 15:22, Helmut Eller <eller.helmut@gmail.com> wrote:
> On Wed, Jul 03 2024, Pip Cet wrote:
> 
> > And of course the same needs to be done for the marker vector, right?
> 
> 
> It also needs to be done for the headers, right? I mean, the last
> significant bits of the igc_header must be non-zero.

Indeed (and IGC_OBJ_WEAK_HASH_TABLE_STRONG_PART is 32, oh no!) I just proposed turning the igc_header into a plain integer (rather than a bitfield) interpreted by igc code so I could put a tagged pointer there, but we'd also handle that. That would also make it easier to add igc_headers to all objects: we'd simply put an igc header into the structs or into pure space and fill it when we register the object.

I'm still not sure what happens when a weak object single access is emulated and finds an aligned non-reference. I was hoping for a crash, but I tried with gdb and it appears to silently be ignored.

I'm also not sure whether the strong->weak and weak->strong references need to be base pointers rather than client pointers. The documentation is somewhat unclear.

Thanks!

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Wed, Jul 03 2024, Pip Cet wrote:
>
>> And of course the same needs to be done for the marker vector, right?
>
> It also needs to be done for the headers, right?  I mean, the last
> significant bits of the igc_header must be non-zero.

Could be. Ohgottoogottogot :-(. I don't want that.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Thursday, July 4th, 2024 at 15:22, Helmut Eller <eller.helmut@gmail.com> wrote:
>> On Wed, Jul 03 2024, Pip Cet wrote:
>> 
>> > And of course the same needs to be done for the marker vector, right?
>> 
>> 
>> It also needs to be done for the headers, right? I mean, the last
>> significant bits of the igc_header must be non-zero.
>
> Indeed (and IGC_OBJ_WEAK_HASH_TABLE_STRONG_PART is 32, oh no!) I just
> proposed turning the igc_header into a plain integer (rather than a
> bitfield) interpreted by igc code so I could put a tagged pointer
> there, but we'd also handle that. That would also make it easier to
> add igc_headers to all objects: we'd simply put an igc header into the
> structs or into pure space and fill it when we register the object.

How ugly. And all because of software emulation of IA-32 :-(.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Thursday, July 4th, 2024 at 07:17, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> > > Move fast and break things. Normal.
>> > 
>> > I'm afraid I've continued to do so. After the last push,
>> 
>> Did that too yesterday for --enable-checking. and had to revert now :-)
>
>> > my TODO list is down to:
>> > 
>> > * fix bugs that slipped through (well, obviously)
>> > * user-defined hash table tests for weak tables don't work
>> > * key-or-value weakness doesn't work
>
> 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.

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

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 3669 bytes --]

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0003-allow-IGC-to-keep-track-of-an-extra-dependency-in-th.patch --]
[-- Type: text/x-patch; name=0003-allow-IGC-to-keep-track-of-an-extra-dependency-in-th.patch, Size: 3383 bytes --]

From cd229f8346300b435a24bdec86ee2aecf1f61ba0 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Thu, 4 Jul 2024 18:43:54 +0000
Subject: [PATCH 3/5] allow IGC to keep track of an extra dependency in the
 exthdr

---
 src/igc.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 78 insertions(+)

diff --git a/src/igc.c b/src/igc.c
index 9be30fcb3cf..bc697700bf7 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -542,6 +542,22 @@ igc_header_nwords (const struct igc_header *h)
   return IGC_HEADER_NWORDS (h);
 }
 
+static struct igc_exthdr *
+igc_external_header (struct igc_header *h)
+{
+  if (IGC_HEADER_TAG (h) != IGC_TAG_EXTHDR)
+    {
+      struct igc_exthdr *exthdr = xmalloc (sizeof *exthdr);
+      exthdr->nwords = IGC_HEADER_NWORDS (h);
+      exthdr->hash = IGC_HEADER_HASH (h);
+      exthdr->obj_type = IGC_HEADER_TYPE (h);
+      exthdr->extra_dependency = Qnil;
+      h->v = (intptr_t)exthdr + IGC_TAG_EXTHDR;
+    }
+
+  return IGC_HEADER_EXTHDR (h);
+}
+
 /* Value is the size in bytes of the object described by header H.
    This includes the header itself. */
 
@@ -1667,6 +1683,12 @@ dflt_scan_obj (mps_ss_t ss, mps_addr_t base_start, mps_addr_t base_limit,
 	  }
       }
 
+    if (IGC_HEADER_TAG (header) == IGC_TAG_EXTHDR)
+      {
+	struct igc_exthdr *exthdr = IGC_HEADER_EXTHDR (header);
+	IGC_FIX12_OBJ (ss, &exthdr->extra_dependency);
+      }
+
     switch (igc_header_type (header))
       {
       case IGC_OBJ_INVALID:
@@ -4251,6 +4273,61 @@ DEFUN ("igc--roots", Figc__roots, Sigc__roots, 0, 0, 0, doc : /* */)
   return roots;
 }
 
+DEFUN ("igc-add-extra-dependency", Figc_add_extra_dependency,
+       Sigc_add_extra_dependency, 2, 2, 0, doc : /* */)
+  (Lisp_Object obj, Lisp_Object dependency)
+{
+  mps_word_t word = XLI (obj);
+  mps_word_t tag = word & IGC_TAG_MASK;
+  mps_addr_t client = NULL;
+  switch (tag)
+    {
+    case Lisp_Type_Unused0:
+      emacs_abort ();
+
+    case Lisp_Int0:
+    case Lisp_Int1:
+      return Qnil;
+
+    case Lisp_Symbol:
+      {
+	ptrdiff_t off = word ^ tag;
+	client = (mps_addr_t) ((char *) lispsym + off);
+      }
+      break;
+
+    case Lisp_String:
+    case Lisp_Vectorlike:
+    case Lisp_Cons:
+    case Lisp_Float:
+      client = (mps_addr_t) (word ^ tag);
+      break;
+    }
+
+  /* Objects in the the dump have igc_headers, too. */
+  if (!has_header (client, tag == Lisp_Vectorlike))
+    {
+      return Qnil;
+    }
+
+  struct igc_header *h = client_to_base (client);
+  struct igc_exthdr *exthdr = igc_external_header (h);
+  if (HASH_TABLE_P (exthdr->extra_dependency))
+    Fputhash (dependency, Qt, exthdr->extra_dependency);
+  else if (HASH_TABLE_P (dependency) || !NILP (exthdr->extra_dependency))
+    {
+      Lisp_Object hash = CALLN (Fmake_hash_table);
+      Fputhash (dependency, Qt, hash);
+      if (!NILP (exthdr->extra_dependency))
+	Fputhash (exthdr->extra_dependency, Qt, hash);
+      exthdr->extra_dependency = hash;
+    }
+  else
+    exthdr->extra_dependency = dependency;
+
+  return Qt;
+}
+
 static void
 make_arena (struct igc *gc)
 {
@@ -4678,6 +4755,7 @@ syms_of_igc (void)
   defsubr (&Sigc_info);
   defsubr (&Sigc__roots);
   defsubr (&Sigc__collect);
+  defsubr (&Sigc_add_extra_dependency);
   DEFSYM (Qambig, "ambig");
   DEFSYM (Qexact, "exact");
   Fprovide (intern_c_string ("mps"), Qnil);
-- 
2.45.2


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0005-finalize-bignums-later.-This-avoids-the-need-for-spl.patch --]
[-- Type: text/x-patch; name=0005-finalize-bignums-later.-This-avoids-the-need-for-spl.patch, Size: 3013 bytes --]

From 3a0d2b439dd91b569f7e03c52987bedd3034c38b Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Thu, 4 Jul 2024 19:14:57 +0000
Subject: [PATCH 5/5] finalize bignums later. This avoids the need for
 splatting PVECs.

---
 src/igc.c     | 21 ++++++++++++++++++++-
 src/lisp.h    |  1 +
 src/pdumper.c |  2 +-
 3 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/src/igc.c b/src/igc.c
index 7a42470f061..1640a490c6b 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -383,6 +383,7 @@ obj_type_name (enum igc_obj_type type)
   "PVEC_NORMAL_VECTOR",
   "PVEC_FREE",
   "PVEC_BIGNUM",
+  "PVEC_BIGNUM_FINALIZER",
   "PVEC_MARKER",
   "PVEC_OVERLAY",
   "PVEC_FINALIZER",
@@ -2448,6 +2449,9 @@ fix_vector (mps_ss_t ss, struct Lisp_Vector *v)
       case PVEC_BIGNUM:
 	break;
 
+      case PVEC_BIGNUM_FINALIZER:
+	break;
+
       case PVEC_NATIVE_COMP_UNIT:
 	IGC_FIX_CALL_FN (ss, struct Lisp_Native_Comp_Unit, v, fix_comp_unit);
 	break;
@@ -3101,6 +3105,15 @@ finalize_finalizer (struct Lisp_Finalizer *f)
 #define SPLAT_PVEC(v)				 \
   (((v)->header.size &= ~PVEC_TYPE_MASK), XSETPVECTYPE(v, PVEC_FREE))
 
+static Lisp_Object
+make_bignum_finalizer (struct Lisp_Bignum *n)
+{
+  struct Lisp_Bignum *b = ALLOCATE_PLAIN_PSEUDOVECTOR (struct Lisp_Bignum,
+						       PVEC_BIGNUM_FINALIZER);
+  memcpy (&b->value, &n->value, sizeof (b->value));
+  return make_lisp_ptr (b, Lisp_Vectorlike);
+}
+
 static void
 finalize_vector (mps_addr_t v)
 {
@@ -3111,6 +3124,12 @@ finalize_vector (mps_addr_t v)
       emacs_abort ();
 
     case PVEC_BIGNUM:
+      Figc_add_extra_dependency (make_lisp_ptr (vec, Lisp_Vectorlike),
+				 make_bignum_finalizer (v),
+				 Qt);
+      break;
+
+    case PVEC_BIGNUM_FINALIZER:
       finalize_bignum (v);
       break;
 
@@ -3201,7 +3220,6 @@ finalize_vector (mps_addr_t v)
       igc_assert (!"finalization not implemented");
       break;
     }
-  SPLAT_PVEC (vec);
 }
 
 static void
@@ -3262,6 +3280,7 @@ maybe_finalize (mps_addr_t client, enum pvec_type tag)
   switch (tag)
     {
     case PVEC_BIGNUM:
+    case PVEC_BIGNUM_FINALIZER:
     case PVEC_FONT:
     case PVEC_THREAD:
     case PVEC_MUTEX:
diff --git a/src/lisp.h b/src/lisp.h
index 34bf483b511..a7e11a43899 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -1027,6 +1027,7 @@ DEFINE_GDB_SYMBOL_END (PSEUDOVECTOR_FLAG)
   PVEC_NORMAL_VECTOR, /* Should be first, for sxhash_obj.  */
   PVEC_FREE,
   PVEC_BIGNUM,
+  PVEC_BIGNUM_FINALIZER,
   PVEC_MARKER,
   PVEC_OVERLAY,
   PVEC_FINALIZER,
diff --git a/src/pdumper.c b/src/pdumper.c
index 73719567f80..76c7cf7383d 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -3131,7 +3131,7 @@ dump_vectorlike (struct dump_context *ctx,
                  Lisp_Object lv,
                  dump_off offset)
 {
-#if CHECK_STRUCTS && !defined HASH_pvec_type_914166A3B4
+#if CHECK_STRUCTS && !defined HASH_pvec_type_5F7ABD3A67
 # error "pvec_type changed. See CHECK_STRUCTS comment in config.h."
 #endif
   const struct Lisp_Vector *v = XVECTOR (lv);
-- 
2.45.2


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0004-implement-key-or-value-hash-tables.patch --]
[-- Type: text/x-patch; name=0004-implement-key-or-value-hash-tables.patch, Size: 6764 bytes --]

From 289acb4a40595b7604b1c4e07242510d2537e214 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Thu, 4 Jul 2024 19:00:18 +0000
Subject: [PATCH 4/5] implement key-or-value hash tables

---
 src/fns.c | 21 ++++++++++++++++-
 src/igc.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 78 insertions(+), 10 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 221e239c639..4faa0cd51d8 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -5508,6 +5508,7 @@ allocate_weak_hash_table (hash_table_weakness_t weak, ssize_t size, ssize_t inde
       ret->strong->index = ret->strong->entries + 3 * size;
       break;
     case Weak_Key_And_Value:
+    case Weak_Key_Or_Value:
       ret->strong->key = ret->weak->entries;
       ret->strong->value = ret->weak->entries + size;
       ret->strong->index = ret->strong->entries + 2 * size;
@@ -5661,6 +5662,7 @@ maybe_resize_weak_hash_table (struct Lisp_Weak_Hash_Table *h)
 	  strong->index = strong->entries + 3 * new_size;
 	  break;
 	case Weak_Key_And_Value:
+	case Weak_Key_Or_Value:
 	  strong->key = weak->entries;
 	  strong->value = weak->entries + new_size;
 	  strong->index = strong->entries + 2 * new_size;
@@ -5742,6 +5744,11 @@ weak_hash_put (struct Lisp_Weak_Hash_Table *h, Lisp_Object key, Lisp_Object valu
   /* Increment count after resizing because resizing may fail.  */
   maybe_resize_weak_hash_table (h);
 
+  if (h->strong->weakness == Weak_Key_Or_Value)
+    {
+      Figc_add_extra_dependency (key, value, make_lisp_weak_hash_table (h));
+      Figc_add_extra_dependency (value, key, make_lisp_weak_hash_table (h));
+    }
   /* Store key/value in the key_and_value vector.  */
   ptrdiff_t i = XFIXNUM (h->strong->next_free);
   //eassert (hash_unused_entry_key_p (HASH_KEY (h, i)));
@@ -6546,7 +6553,19 @@ DEFUN ("puthash", Fputhash, Sputhash, 3, 3, 0,
       Lisp_Object hash = weak_hash_from_key (wh, key);
       ptrdiff_t i = weak_hash_lookup_with_hash (wh, key, hash);
       if (i >= 0)
-	set_weak_hash_value_slot (wh, i, value);
+	{
+	  if (wh->strong->weakness == Weak_Key_Or_Value)
+	    {
+	      Figc_remove_extra_dependency (key, table);
+	      Figc_remove_extra_dependency (value, table);
+	    }
+	  set_weak_hash_value_slot (wh, i, value);
+	  if (wh->strong->weakness == Weak_Key_Or_Value)
+	    {
+	      Figc_add_extra_dependency (key, value, table);
+	      Figc_add_extra_dependency (value, key, table);
+	    }
+	}
       else
 	weak_hash_put (wh, key, value, hash);
       return value;
diff --git a/src/igc.c b/src/igc.c
index bc697700bf7..7a42470f061 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -2019,6 +2019,7 @@ fix_weak_hash_table_strong_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Strong
 	    limit = 3 * XFIXNUM (t->table_size);
 	    break;
 	  case Weak_Key_And_Value:
+	  case Weak_Key_Or_Value:
 	    limit = 2 * XFIXNUM (t->table_size);
 	    break;
 	  default:
@@ -2054,6 +2055,7 @@ fix_weak_hash_table_weak_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Weak_Par
 	    limit = XFIXNUM (t->table_size);
 	    break;
 	  case Weak_Key_And_Value:
+	  case Weak_Key_Or_Value:
 	    limit = 2 * XFIXNUM (t->table_size);
 	    break;
 	  default:
@@ -2074,7 +2076,8 @@ fix_weak_hash_table_weak_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Weak_Par
 		    .weak = w,
 		  };
 		weak_hash_splat_from_table
-		  (&pseudo_h, ((t->weakness == Weak_Key_And_Value) ?
+		  (&pseudo_h, ((t->weakness == Weak_Key_And_Value ||
+				t->weakness == Weak_Key_Or_Value) ?
 			       (i % XFIXNUM (t->table_size)) : i));
 	      }
 	  }
@@ -3990,6 +3993,7 @@ igc_alloc_weak_hash_table_strong_part (hash_table_weakness_t weak,
       total_size = 3 * size + ((ptrdiff_t)1 << index_bits);
       break;
     case Weak_Key_And_Value:
+    case Weak_Key_Or_Value:
       total_size = 2 * size + ((ptrdiff_t)1 << index_bits);
       break;
     default:
@@ -4014,6 +4018,7 @@ igc_alloc_weak_hash_table_weak_part (hash_table_weakness_t weak,
       total_size = size;
       break;
     case Weak_Key_And_Value:
+    case Weak_Key_Or_Value:
       total_size = 2 * size;
       break;
     default:
@@ -4274,8 +4279,8 @@ DEFUN ("igc--roots", Figc__roots, Sigc__roots, 0, 0, 0, doc : /* */)
 }
 
 DEFUN ("igc-add-extra-dependency", Figc_add_extra_dependency,
-       Sigc_add_extra_dependency, 2, 2, 0, doc : /* */)
-  (Lisp_Object obj, Lisp_Object dependency)
+       Sigc_add_extra_dependency, 3, 3, 0, doc : /* */)
+  (Lisp_Object obj, Lisp_Object dependency, Lisp_Object key)
 {
   mps_word_t word = XLI (obj);
   mps_word_t tag = word & IGC_TAG_MASK;
@@ -4313,17 +4318,60 @@ DEFUN ("igc-add-extra-dependency", Figc_add_extra_dependency,
   struct igc_header *h = client_to_base (client);
   struct igc_exthdr *exthdr = igc_external_header (h);
   if (HASH_TABLE_P (exthdr->extra_dependency))
-    Fputhash (dependency, Qt, exthdr->extra_dependency);
-  else if (HASH_TABLE_P (dependency) || !NILP (exthdr->extra_dependency))
+    Fputhash (key, dependency, exthdr->extra_dependency);
+  else
     {
       Lisp_Object hash = CALLN (Fmake_hash_table);
-      Fputhash (dependency, Qt, hash);
-      if (!NILP (exthdr->extra_dependency))
-	Fputhash (exthdr->extra_dependency, Qt, hash);
+      Fputhash (key, dependency, hash);
       exthdr->extra_dependency = hash;
     }
+
+  return Qt;
+}
+
+DEFUN ("igc-remove-extra-dependency", Figc_remove_extra_dependency,
+       Sigc_remove_extra_dependency, 2, 2, 0, doc : /* */)
+  (Lisp_Object obj, Lisp_Object key)
+{
+  mps_word_t word = XLI (obj);
+  mps_word_t tag = word & IGC_TAG_MASK;
+  mps_addr_t client = NULL;
+  switch (tag)
+    {
+    case Lisp_Type_Unused0:
+      emacs_abort ();
+
+    case Lisp_Int0:
+    case Lisp_Int1:
+      return Qnil;
+
+    case Lisp_Symbol:
+      {
+	ptrdiff_t off = word ^ tag;
+	client = (mps_addr_t) ((char *) lispsym + off);
+      }
+      break;
+
+    case Lisp_String:
+    case Lisp_Vectorlike:
+    case Lisp_Cons:
+    case Lisp_Float:
+      client = (mps_addr_t) (word ^ tag);
+      break;
+    }
+
+  /* Objects in the the dump have igc_headers, too. */
+  if (!has_header (client, tag == Lisp_Vectorlike))
+    {
+      return Qnil;
+    }
+
+  struct igc_header *h = client_to_base (client);
+  struct igc_exthdr *exthdr = igc_external_header (h);
+  if (HASH_TABLE_P (exthdr->extra_dependency))
+    Fremhash (key, exthdr->extra_dependency);
   else
-    exthdr->extra_dependency = dependency;
+    return Qnil;
 
   return Qt;
 }
@@ -4756,6 +4804,7 @@ syms_of_igc (void)
   defsubr (&Sigc__roots);
   defsubr (&Sigc__collect);
   defsubr (&Sigc_add_extra_dependency);
+  defsubr (&Sigc_remove_extra_dependency);
   DEFSYM (Qambig, "ambig");
   DEFSYM (Qexact, "exact");
   Fprovide (intern_c_string ("mps"), Qnil);
-- 
2.45.2


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #5: 0001-Ugly-hack-to-satisfy-MPS-single-access-rules.patch --]
[-- Type: text/x-patch; name=0001-Ugly-hack-to-satisfy-MPS-single-access-rules.patch, Size: 7673 bytes --]

From a37c52f82ec89a8b9bd88c80b7801a7ed2329cbb Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Thu, 4 Jul 2024 18:17:16 +0000
Subject: [PATCH 1/5] Ugly hack to satisfy MPS single-access rules.

---
 src/igc.c | 89 ++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 59 insertions(+), 30 deletions(-)

diff --git a/src/igc.c b/src/igc.c
index 624bb31b2ed..b24ff19a137 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -459,21 +459,45 @@ pvec_type_name (enum pvec_type type)
 
 enum
 {
-  IGC_TYPE_BITS = 6,
-  IGC_HASH_BITS = 26,
-  IGC_SIZE_BITS = 32,
-  IGC_HASH_MASK = (1 << IGC_HASH_BITS) - 1,
+  IGC_HEADER_TAG_BITS = 2,
+  IGC_HEADER_TYPE_BITS = 6,
+  IGC_HEADER_HASH_BITS = 24,
+  IGC_HEADER_NWORDS_BITS = 32,
+  IGC_HEADER_TAG_MASK = (1LL << IGC_HEADER_TAG_BITS) - 1,
+  IGC_HEADER_TYPE_MASK = (1 << IGC_HEADER_TYPE_BITS) - 1,
+  IGC_HEADER_HASH_MASK = (1 << IGC_HEADER_HASH_BITS) - 1,
 };
 
-static_assert (IGC_OBJ_NUM_TYPES - 1 < (1 << IGC_TYPE_BITS));
+static_assert (IGC_OBJ_NUM_TYPES - 1 < (1 << IGC_HEADER_TYPE_BITS));
 
 struct igc_header
 {
-  enum igc_obj_type obj_type : IGC_TYPE_BITS;
-  mps_word_t hash : IGC_HASH_BITS;
-  mps_word_t nwords : IGC_SIZE_BITS;
+  uint64_t v;
 };
 
+#define IGC_HEADER_NWORDS(h) ((h)->v >> (64 - IGC_HEADER_NWORDS_BITS))
+#define IGC_HEADER_HASH(h) (((h)->v >> (IGC_HEADER_TYPE_BITS + IGC_HEADER_TAG_BITS)) & IGC_HEADER_HASH_MASK)
+#define IGC_HEADER_TYPE(h) (((h)->v >> IGC_HEADER_TAG_BITS) & IGC_HEADER_TYPE_MASK)
+#define IGC_HEADER_TAG(h) ((h)->v & IGC_HEADER_TAG_MASK)
+
+enum igc_tag
+{
+  IGC_TAG_NULL = 0, /* entire value must be 0 to avoid MPS issues */
+  IGC_TAG_OBJ = 1, /* IGC object */
+};
+
+static enum igc_obj_type
+igc_header_type (struct igc_header *h)
+{
+  return IGC_HEADER_TYPE (h);
+}
+
+static unsigned
+igc_header_hash (struct igc_header *h)
+{
+  return IGC_HEADER_HASH (h);
+}
+
 struct igc_fwd
 {
   struct igc_header header;
@@ -495,14 +519,20 @@ to_bytes (mps_word_t nwords)
   return nwords * sizeof (mps_word_t);
 }
 
+static size_t
+igc_header_nwords (const struct igc_header *h)
+{
+  return IGC_HEADER_NWORDS (h);
+}
+
 /* Value is the size in bytes of the object described by header H.
    This includes the header itself. */
 
 static mps_word_t
 obj_size (const struct igc_header *h)
 {
-  mps_word_t nbytes = to_bytes (h->nwords);
-  igc_assert (h->obj_type == IGC_OBJ_PAD || nbytes >= sizeof (struct igc_fwd));
+  mps_word_t nbytes = to_bytes (igc_header_nwords (h));
+  igc_assert (IGC_HEADER_TYPE (h) == IGC_OBJ_PAD || nbytes >= sizeof (struct igc_fwd));
   return nbytes;
 }
 
@@ -522,15 +552,14 @@ obj_client_size (const struct igc_header *h)
 set_header (struct igc_header *h, enum igc_obj_type type,
 	    mps_word_t nbytes, mps_word_t hash)
 {
-#if IGC_SIZE_BITS >= 32 && INTPTR_MAX > INT_MAX
+#if IGC_NWORDS_BITS >= 32 && INTPTR_MAX > INT_MAX
   /* On 32-bit architecture the assertion below is redundant and
      causes compiler warnings.  */
-  igc_assert (nbytes < ((size_t) 1 << IGC_SIZE_BITS));
+  igc_assert (nbytes < ((size_t) 1 << IGC_HEADER_NWORDS_BITS));
 #endif
   igc_assert (type == IGC_OBJ_PAD || nbytes >= sizeof (struct igc_fwd));
-  h->obj_type = type;
-  h->nwords = to_words (nbytes);
-  h->hash = hash;
+  h->v = (to_words (nbytes) << (64 - IGC_HEADER_NWORDS_BITS)) +
+    (hash << (IGC_HEADER_TAG_BITS + IGC_HEADER_TYPE_BITS)) + (type << IGC_HEADER_TAG_BITS) + IGC_TAG_OBJ;
 }
 
 /* Given a pointer to the client area of an object, CLIENT, return
@@ -587,7 +616,7 @@ alloc_size (size_t nbytes)
 alloc_hash (void)
 {
   static unsigned count = 0;
-  return count++;
+  return count++ & IGC_HEADER_HASH_MASK;
 }
 
 /* This runs in various places for --enable-checking=igc_check_fwd.  See
@@ -600,7 +629,7 @@ igc_check_fwd (void *client)
   if (has_header (client, true))
     {
       struct igc_header *h = client_to_base (client);
-      igc_assert (h->obj_type != IGC_OBJ_FWD);
+      igc_assert (IGC_HEADER_TYPE (h) != IGC_OBJ_FWD);
       igc_assert (obj_size (h) >= sizeof (struct igc_fwd));
     }
 }
@@ -1358,9 +1387,9 @@ dflt_fwd (mps_addr_t old_base_addr, mps_addr_t new_base_addr)
 {
   struct igc_header *h = old_base_addr;
   igc_assert (obj_size (h) >= sizeof (struct igc_fwd));
-  igc_assert (h->obj_type != IGC_OBJ_PAD);
+  igc_assert (IGC_HEADER_TYPE (h) != IGC_OBJ_PAD);
   struct igc_fwd *f = old_base_addr;
-  f->header.obj_type = IGC_OBJ_FWD;
+  set_header (&f->header, IGC_OBJ_FWD, to_bytes (IGC_HEADER_NWORDS (h)), 0);
   f->new_base_addr = new_base_addr;
 }
 
@@ -1368,7 +1397,7 @@ dflt_fwd (mps_addr_t old_base_addr, mps_addr_t new_base_addr)
 is_dflt_fwd (mps_addr_t base_addr)
 {
   struct igc_fwd *f = base_addr;
-  if (f->header.obj_type == IGC_OBJ_FWD)
+  if (IGC_HEADER_TYPE (&f->header) == IGC_OBJ_FWD)
     return f->new_base_addr;
   return NULL;
 }
@@ -1602,7 +1631,7 @@ dflt_scan_obj (mps_ss_t ss, mps_addr_t base_start, mps_addr_t base_limit,
     if (closure)
       {
 	struct igc_stats *st = closure;
-	mps_word_t obj_type = header->obj_type;
+	mps_word_t obj_type = igc_header_type (header);
 	igc_assert (obj_type < IGC_OBJ_NUM_TYPES);
 	size_t size = obj_size (header);
 	st->obj[obj_type].nbytes += size;
@@ -1621,7 +1650,7 @@ dflt_scan_obj (mps_ss_t ss, mps_addr_t base_start, mps_addr_t base_limit,
 	  }
       }
 
-    switch (header->obj_type)
+    switch (igc_header_type (header))
       {
       case IGC_OBJ_INVALID:
       case IGC_OBJ_BUILTIN_SYMBOL:
@@ -3138,7 +3167,7 @@ finalize (struct igc *gc, mps_addr_t base)
 {
   mps_addr_t client = base_to_client (base);
   struct igc_header *h = base;
-  switch (h->obj_type)
+  switch (igc_header_type (h))
     {
     case IGC_OBJ_INVALID:
     case IGC_OBJ_PAD:
@@ -3547,12 +3576,12 @@ igc_hash (Lisp_Object key)
       // The following assertion is very expensive.
       // igc_assert (mps_arena_has_addr (global_igc->arena, client));
       struct igc_header *h = client_to_base (client);
-      return h->hash;
+      return igc_header_hash (h);
     }
 
   /* Use a hash that would fit into igc_header::hash so that we
      can keep the hash once a non-MPS object is copied to MPS. */
-  return word & IGC_HASH_MASK;
+  return word & IGC_HEADER_HASH_MASK;
 }
 
 /* Allocate an object of client size SIZE and of type TYPE from
@@ -3827,7 +3856,7 @@ igc_alloc_lisp_obj_vec (size_t n)
 weak_hash_find_dependent (mps_addr_t base)
 {
   struct igc_header *h = base;
-  switch (h->obj_type)
+  switch (igc_header_type (h))
     {
     case IGC_OBJ_WEAK_HASH_TABLE_WEAK_PART:
       {
@@ -4408,7 +4437,7 @@ pure_obj_type_and_hash (size_t *hash_o, enum igc_obj_type type, void *client)
       return type;
 
     case IGC_OBJ_STRING_DATA:
-      *hash_o = (uintptr_t) client & IGC_HASH_MASK;
+      *hash_o = (uintptr_t) client & IGC_HEADER_HASH_MASK;
       return type;
 
     case IGC_OBJ_FLOAT:
@@ -4460,9 +4489,9 @@ igc_dump_finish_obj (void *client, enum igc_obj_type type,
       && !is_in_dump)
     {
       struct igc_header *h = client_to_base (client);
-      if (h->obj_type == IGC_OBJ_MARKER_VECTOR)
+      if (igc_header_type (h) == IGC_OBJ_MARKER_VECTOR)
 	igc_assert ((type == IGC_OBJ_VECTOR
-		     && h->obj_type == IGC_OBJ_MARKER_VECTOR)
+		     && igc_header_type (h) == IGC_OBJ_MARKER_VECTOR)
 		    || h->obj_type == type);
       igc_assert (base + obj_size (h) >= end);
       *out = *h;
@@ -4526,7 +4555,7 @@ check_dump (mps_addr_t start, mps_addr_t end)
     {
       eassert (p < end);
       struct igc_header *h = p;
-      if (h->obj_type != IGC_OBJ_PAD)
+      if (IGC_HEADER_TYPE (h) != IGC_OBJ_PAD)
 	{
 	  mps_addr_t obj = pdumper_next_object (&it);
 	  eassert (p == obj);
-- 
2.45.2


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #6: 0002-Allow-IGC-headers-to-be-pointers-to-an-external-exte.patch --]
[-- Type: text/x-patch; name=0002-Allow-IGC-headers-to-be-pointers-to-an-external-exte.patch, Size: 1719 bytes --]

From 87062f0c05a46a146d1bd63c631da83ac0a64463 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@protonmail.com>
Date: Thu, 4 Jul 2024 18:17:43 +0000
Subject: [PATCH 2/5] Allow IGC headers to be pointers to an external extended
 real header

---
 src/igc.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/src/igc.c b/src/igc.c
index b24ff19a137..9be30fcb3cf 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -480,21 +480,36 @@ #define IGC_HEADER_HASH(h) (((h)->v >> (IGC_HEADER_TYPE_BITS + IGC_HEADER_TAG_BI
 #define IGC_HEADER_TYPE(h) (((h)->v >> IGC_HEADER_TAG_BITS) & IGC_HEADER_TYPE_MASK)
 #define IGC_HEADER_TAG(h) ((h)->v & IGC_HEADER_TAG_MASK)
 
+struct igc_exthdr
+{
+  EMACS_UINT nwords;
+  EMACS_UINT hash;
+  enum igc_obj_type obj_type;
+  Lisp_Object extra_dependency;
+};
+
+#define IGC_HEADER_EXTHDR(h) ((struct igc_exthdr *)(intptr_t)((h)->v & ~IGC_HEADER_TAG_MASK))
+
 enum igc_tag
 {
   IGC_TAG_NULL = 0, /* entire value must be 0 to avoid MPS issues */
   IGC_TAG_OBJ = 1, /* IGC object */
+  IGC_TAG_EXTHDR = 2, /* pointer to aligned external header */
 };
 
 static enum igc_obj_type
 igc_header_type (struct igc_header *h)
 {
+  if (IGC_HEADER_TAG (h) == IGC_TAG_EXTHDR)
+    return IGC_HEADER_EXTHDR (h)->obj_type;
   return IGC_HEADER_TYPE (h);
 }
 
 static unsigned
 igc_header_hash (struct igc_header *h)
 {
+  if (IGC_HEADER_TAG (h) == IGC_TAG_EXTHDR)
+    return IGC_HEADER_EXTHDR (h)->hash;
   return IGC_HEADER_HASH (h);
 }
 
@@ -522,6 +537,8 @@ to_bytes (mps_word_t nwords)
 static size_t
 igc_header_nwords (const struct igc_header *h)
 {
+  if (IGC_HEADER_TAG (h) == IGC_TAG_EXTHDR)
+    return IGC_HEADER_EXTHDR (h)->nwords;
   return IGC_HEADER_NWORDS (h);
 }
 
-- 
2.45.2

Re: MPS: weak hash tables

[Gerd Möllmann]

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!

Re: MPS: weak hash tables

[Pip Cet]

On Friday, July 5th, 2024 at 03:50, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> 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)

Except that a uint64_t is two 32 bit words, and they both must be non-aligned. How horrible. At least we've excluded WIDE_EMACS_INT :-)

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

My priority would be getting the branch merged. If it isn't, it'll bit-rot, I'm afraid. I realize it's too soon to ask for a final decision on that (which would be made on merge day, presumably), but I've found myself using my IGC emacs -Q when my vanilla Emacs is stuck in GC, so it's not like it doesn't work at all. And, yes, I realize there's a lot of work to be done for that...

Feature/bug-wise, what's still missing? key-or-value weakness (haven't slept enough yet to decide whether to merge), sure, but is that essential? The signal handler stuff is fixable, I'm convinced. I've got a bug fix for what I hope to be the very last bug with the IA-32 stuff. There are two very minor bugs (there are Lisp_Objects in the wrong part of pure space, and igc_realloc_ambig doesn't park the arena--one-liners really). The two major fixmes concern native compilation and the byte code stack, right? I'm perfectly happy to leave unnecessarily ambiguous references ambiguous for now.

My next question would be: are there any planned big changes which would touch too many files on the master branch? The one I can think of is I would like to move the IGC header to live in struct Lisp_Cons/Lisp_String/Lisp_Symbol/Lisp_Float and in union vectorlike_header, and make client == base. I believe this would also make things easier for other GC approaches which would also need some sort of header. No real problem for non-native-comp builds: the problem with this is changing these structs requires adjusting comp.c, which rebuilds them in libgccjit calls. I don't think that's very hard to do either, but it's potentially subtle and I'm planning to write Andrea about it.

So, yes, I'd love that too, but I may be underestimating the difficulty of getting this merged.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Friday, July 5th, 2024 at 03:50, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> 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)
>
> Except that a uint64_t is two 32 bit words, and they both must be
> non-aligned.

Unbelievable. Was für ein Scheiß.

> How horrible. At least we've excluded WIDE_EMACS_INT :-)

:-)

>> 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.
>
> My priority would be getting the branch merged. If it isn't, it'll
> bit-rot, I'm afraid.

Could happen, yes.

> I realize it's too soon to ask for a final decision on that (which
> would be made on merge day, presumably), but I've found myself using
> my IGC emacs -Q when my vanilla Emacs is stuck in GC, so it's not like
> it doesn't work at all. And, yes, I realize there's a lot of work to
> be done for that...

(I'm using it all the time, too. I'm running an Emacs from cl-packages
(the branch from igc is branched) to run an Emacs from the igc branch
under LLDB. The igc Emacs is what I'm using all the time, and in that I
develop in yet another branch, which I merge/rebase back to igc.)

Wrt to the merge to master, I think the maintainers, mainly Eli
probably, have to cope with the situation as it is. As far as I'm
concerned, that's solely a GNU thing.

> Feature/bug-wise, what's still missing? key-or-value weakness (haven't
> slept enough yet to decide whether to merge), sure, but is that
> essential? The signal handler stuff is fixable, I'm convinced. I've
> got a bug fix for what I hope to be the very last bug with the IA-32
> stuff. There are two very minor bugs (there are Lisp_Objects in the
> wrong part of pure space, and igc_realloc_ambig doesn't park the
> arena--one-liners really). The two major fixmes concern native
> compilation and the byte code stack, right? I'm perfectly happy to
> leave unnecessarily ambiguous references ambiguous for now.

Curiously enough native compilation seems to work for me now on macOS. I
was never able to debug this deep enough to find the underlying cause
why it failed. It might be a new version fo GCC 14 that I got meanwhile,
the most recent merge from master, changes in igc, or anything else.

The scanning of the byte code stack is really ugly, right. The
computation of where it ends that is. Mattias mentioned that he might
make changes in the byte code stack so that it could be marked exactly.
One could just wait till that happens. It doesn't seem to cause
stability problems.

Other than that I have nothing left in my todo list once I've done the
n-th pass of scanning the source code for untraced references  Which
proceeds slowlym but I've reached the files starting with c now :-).

> My next question would be: are there any planned big changes which
> would touch too many files on the master branch? 

Not from my side. I'm through with my stuff. Helmut mentioned interest
in remove headers from conses, I think, but I guess he can tell what he
wants to do himself better than me :-).

(I'm not interested in that, FWIW, but I can understand why some want
it.)

> The one I can think of is I would like to move the IGC header to live
> in struct Lisp_Cons/Lisp_String/Lisp_Symbol/Lisp_Float and in union
> vectorlike_header, and make client == base. I believe this would also
> make things easier for other GC approaches which would also need some
> sort of header. No real problem for non-native-comp builds: the
> problem with this is changing these structs requires adjusting comp.c,
> which rebuilds them in libgccjit calls. I don't think that's very hard
> to do either, but it's potentially subtle and I'm planning to write
> Andrea about it.
>
> So, yes, I'd love that too, 

👍👍👍 :-). Thanks!

> but I may be underestimating the difficulty of getting this merged.

The administrative hurdles, you mean? Could be, no idea.

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Fri, 05 Jul 2024 12:08:55 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: Helmut Eller <eller.helmut@gmail.com>, Eli Zaretskii <eliz@gnu.org>, Emacs Devel <emacs-devel@gnu.org>
> 
> At least we've excluded WIDE_EMACS_INT :-)

Which is a pity, IMNSHO, and a major disappointment for me personally,
since I'm a happy user of that configuration for many years.

> Feature/bug-wise, what's still missing?

AFAIU, there are still several areas that were not tested on the
branch, and therefore we don't have a clear idea whether they work and
how well/stable.  Here's a list (note: not _the_ list) off the top of
my head:

  . Lisp threads
  . modules
  . finalizers (including their relation to modules)
  . TTY frames, including with C-g and Lisp threads

I'm sure there's more.

Re: MPS: weak hash tables

[Helmut Eller]

On Fri, Jul 05 2024, Pip Cet wrote:

> Feature/bug-wise, what's still missing?

ert-tests.el worries me the most.  There, MPS looks pretty bad compared
to the old GC.  (Who would have thought that printing backtraces
involves copying and rebalancing interval trees with thousands of nodes?
And why does it perform so poorly with a generational GC?)

It would be nice to have a way to set a "memory limit".  Preferably with
some "out of memory error".  Even aborting would be better than starting
to swap.

I also think that something needs to be done about the pidigits
benchmark.  It's not about the bignums (which I couldn't care less
about) but the problem that finalization messages are only processed
when Emacs is idle.

Re: MPS: weak hash tables

[Pip Cet]

On Friday, July 5th, 2024 at 18:14, Helmut Eller <eller.helmut@gmail.com> wrote:
> On Fri, Jul 05 2024, Pip Cet wrote:
> 
> > Feature/bug-wise, what's still missing?
> ert-tests.el worries me the most. There, MPS looks pretty bad compared
> to the old GC. (Who would have thought that printing backtraces
> involves copying and rebalancing interval trees with thousands of nodes?
> And why does it perform so poorly with a generational GC?)
> 
> It would be nice to have a way to set a "memory limit". Preferably with
> some "out of memory error". Even aborting would be better than starting
> to swap.
> 
> I also think that something needs to be done about the pidigits
> benchmark. It's not about the bignums (which I couldn't care less
> about) but the problem that finalization messages are only processed
> when Emacs is idle.

Thanks! My personal priorities are correctness first (well, obviously, I doubt it's different for you :-) ), then responsiveness, with "don't degrade batch performance too much" a distant third. I didn't know about the swapping problem, but from what I've understood about the MPS design I'd imagine it's pretty horrible.

What I'm doing right now is alternating usleep(10000) and igc_collect() in a secondary thread. That crashes somewhat reproducibly in interactive sessions.

Pip

Re: MPS: weak hash tables

[Pip Cet]

On Friday, July 5th, 2024 at 13:27, Eli Zaretskii <eliz@gnu.org> wrote:
> > Date: Fri, 05 Jul 2024 12:08:55 +0000
> 
> > From: Pip Cet pipcet@protonmail.com
> > Cc: Helmut Eller eller.helmut@gmail.com, Eli Zaretskii eliz@gnu.org, Emacs Devel emacs-devel@gnu.org
> > 
> > At least we've excluded WIDE_EMACS_INT :-)
> Which is a pity, IMNSHO, and a major disappointment for me personally,
> since I'm a happy user of that configuration for many years.

Interesting. It's not too hard to fit a 62-bit integer into two 32-bit integers which are not 4-bit aligned, of course. I'm not sure what else would go wrong though :-)

> > Feature/bug-wise, what's still missing?
> 
> 
> AFAIU, there are still several areas that were not tested on the
> branch, and therefore we don't have a clear idea whether they work and
> how well/stable. Here's a list (note: not the list) off the top of
> my head:
> 
> . Lisp threads
> . modules
> . finalizers (including their relation to modules)
> . TTY frames, including with C-g and Lisp threads

Thanks, that helps a lot! I've used emacs in a tty on my 32-bit KVM machine, but that hardly counts as testing.

> I'm sure there's more.

Most likely. Time to go through the feature list...

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Fri, Jul 05 2024, Pip Cet wrote:
>
>> Feature/bug-wise, what's still missing?
>
> ert-tests.el worries me the most.  There, MPS looks pretty bad compared
> to the old GC.  (Who would have thought that printing backtraces
> involves copying and rebalancing interval trees with thousands of nodes?
> And why does it perform so poorly with a generational GC?)

Hm, sounds almost like a bug to me. The bug being the copying. Why does
it do that, do you know?

> It would be nice to have a way to set a "memory limit".  Preferably with
> some "out of memory error".  Even aborting would be better than starting
> to swap.

There is

  MPS_KEY_COMMIT_LIMIT (type size_t) is the maximum amount of main memory,
  in bytes (1), that the MPS will obtain from the operating system. See
  mps_arena_commit_limit() for details. The default commit limit is the
  maximum value of the size_t type.

Never tried that. There are also functions to read/set the limit, so
maybe we could introduce a DEFVAR with variable watcher for playing with
it, or a function.

> I also think that something needs to be done about the pidigits
> benchmark.  It's not about the bignums (which I couldn't care less
> about) but the problem that finalization messages are only processed
> when Emacs is idle.

Hm, so this one didn't help.

  void
  garbage_collect (void)
  {
  #ifdef HAVE_MPS
    igc_process_messages ();
  #endif

Looks like it needs to be put somewhere else.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> What I'm doing right now is alternating usleep(10000) and
> igc_collect() in a secondary thread. That crashes somewhat
> reproducibly in interactive sessions.

Could you please make that available in some form?

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 721 bytes --]

On Saturday, July 6th, 2024 at 03:39, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > What I'm doing right now is alternating usleep(10000) and
> > igc_collect() in a secondary thread. That crashes somewhat
> > reproducibly in interactive sessions.
> 
> Could you please make that available in some form?

Sure. I was thinking about cleaning it up (usleep is non-standard) and committing it behind a stress-test option, actually.

Right now it's dying because specpdl is a union type and GC might hit while the main thread leaves it in a partially-initialized state. I vaguely recall turning it into a struct for that reason on another branch years ago...

Pip

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-igc-stress-test.patch --]
[-- Type: text/x-patch; name=0001-igc-stress-test.patch, Size: 748 bytes --]

diff --git a/src/igc.c b/src/igc.c
index f154a040a0e..be2b9fb719e 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -4820,6 +4820,16 @@ igc_busy_p (void)
   return mps_arena_busy (global_igc->arena);
 }
 
+static void *
+igc_thread_fun (void *addr)
+{
+  while (true)
+    {
+      usleep (5000);
+      igc_collect ();
+    }
+}
+
 /***********************************************************************
 				  Init
  ***********************************************************************/
@@ -4830,6 +4840,8 @@ init_igc (void)
   mps_lib_assert_fail_install (igc_assert_fail);
   global_igc = make_igc ();
   add_main_thread ();
+  pthread_t thr;
+  pthread_create (&thr, NULL, igc_thread_fun, global_igc);
   set_state (IGC_STATE_USABLE_PARKED);
 }
 

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Fri, 05 Jul 2024 20:35:34 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> > > At least we've excluded WIDE_EMACS_INT :-)
> > Which is a pity, IMNSHO, and a major disappointment for me personally,
> > since I'm a happy user of that configuration for many years.
> 
> Interesting. It's not too hard to fit a 62-bit integer into two 32-bit integers which are not 4-bit aligned, of course. I'm not sure what else would go wrong though :-)

The problem, AFAIU, is the MPS assumption that Lisp objects can fit
into a "word", which in their parlance means integral data type whose
width is the same as a pointer's.  And that is false in WIDE_EMACS_INT
builds, because Lisp objects are 64-bit wide, whereas pointers are
still 32-bit.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Saturday, July 6th, 2024 at 03:39, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> Pip Cet pipcet@protonmail.com writes:
>> 
>> > What I'm doing right now is alternating usleep(10000) and
>> > igc_collect() in a secondary thread. That crashes somewhat
>> > reproducibly in interactive sessions.
>> 
>> Could you please make that available in some form?
>
> Sure. I was thinking about cleaning it up (usleep is non-standard) and
> committing it behind a stress-test option, actually.

Thanks! If it's not too bad performance-wise, I was thinking of running
it in the Emacs I'm normally using, in parallel to the rest.
>
> Right now it's dying because specpdl is a union type and GC might hit
> while the main thread leaves it in a partially-initialized state. I
> vaguely recall turning it into a struct for that reason on another
> branch years ago...

Shit. That could mean that we have to scan specpdl amiguously.

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 06:20, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > On Saturday, July 6th, 2024 at 03:39, Gerd Möllmann gerd.moellmann@gmail.com wrote:
> > 
> > > Pip Cet pipcet@protonmail.com writes:
> > > 
> > > > What I'm doing right now is alternating usleep(10000) and
> > > > igc_collect() in a secondary thread. That crashes somewhat
> > > > reproducibly in interactive sessions.
> > > 
> > > Could you please make that available in some form?
> > 
> > Sure. I was thinking about cleaning it up (usleep is non-standard) and
> > committing it behind a stress-test option, actually.
> 
> Thanks! If it's not too bad performance-wise, I was thinking of running
> it in the Emacs I'm normally using, in parallel to the rest.

It is very bad since full GCs stop the main thread. However, running it once a second is enough to find some bugs and GCs are fairly fast...

(One thing I've noticed is that MPS handles failed scans gracefully; we might be able to get away with "interrupting" a scan if inputs or signals are pending, but correctness first...)

> > Right now it's dying because specpdl is a union type and GC might hit
> > while the main thread leaves it in a partially-initialized state. I
> > vaguely recall turning it into a struct for that reason on another
> > branch years ago...
> 
> Shit. That could mean that we have to scan specpdl amiguously.

I was hoping to avoid that. Maybe it's enough to just clear the pdl entries in between modifications, since the values we put in should be on the stack or in registers and be pinned.

Pip

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 06:10, Eli Zaretskii <eliz@gnu.org> wrote:
> > Date: Fri, 05 Jul 2024 20:35:34 +0000
> 
> > From: Pip Cet pipcet@protonmail.com
> > Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > 
> > > > At least we've excluded WIDE_EMACS_INT :-)
> > > > Which is a pity, IMNSHO, and a major disappointment for me personally,
> > > > since I'm a happy user of that configuration for many years.
> > 
> > Interesting. It's not too hard to fit a 62-bit integer into two 32-bit integers which are not 4-bit aligned, of course. I'm not sure what else would go wrong though :-)
> 
> The problem, AFAIU, is the MPS assumption that Lisp objects can fit
> into a "word", which in their parlance means integral data type whose
> width is the same as a pointer's. And that is false in WIDE_EMACS_INT
> builds, because Lisp objects are 64-bit wide, whereas pointers are
> still 32-bit.

I may be misunderstanding something. When talking about normal (strong) objects, MPS assumes very little about how the actual objects are represented, as long as they can be turned into references for tracing. I don't think that's going to be a problem. When dealing with weak options, the IA-32 problem does mean that pointers need to be aligned and non-pointers need to be non-aligned or 0, so we'd need to mangle big fixnums before storing them in what, to MPS, is two 32-bit words.

Pip

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Sat, 06 Jul 2024 05:58:19 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: Helmut Eller <eller.helmut@gmail.com>, Eli Zaretskii <eliz@gnu.org>, Emacs Devel <emacs-devel@gnu.org>
> 
> > > What I'm doing right now is alternating usleep(10000) and
> > > igc_collect() in a secondary thread. That crashes somewhat
> > > reproducibly in interactive sessions.
> > 
> > Could you please make that available in some form?
> 
> Sure. I was thinking about cleaning it up (usleep is non-standard) and committing it behind a stress-test option, actually.
> 
> Right now it's dying because specpdl is a union type and GC might hit while the main thread leaves it in a partially-initialized state. I vaguely recall turning it into a struct for that reason on another branch years ago...
> 
> Pip
> 
> diff --git a/src/igc.c b/src/igc.c
> index f154a040a0e..be2b9fb719e 100644
> --- a/src/igc.c
> +++ b/src/igc.c
> @@ -4820,6 +4820,16 @@ igc_busy_p (void)
>    return mps_arena_busy (global_igc->arena);
>  }
>  
> +static void *
> +igc_thread_fun (void *addr)
> +{
> +  while (true)
> +    {
> +      usleep (5000);
> +      igc_collect ();
> +    }
> +}
> +
>  /***********************************************************************
>  				  Init
>   ***********************************************************************/
> @@ -4830,6 +4840,8 @@ init_igc (void)
>    mps_lib_assert_fail_install (igc_assert_fail);
>    global_igc = make_igc ();
>    add_main_thread ();
> +  pthread_t thr;
> +  pthread_create (&thr, NULL, igc_thread_fun, global_igc);
>    set_state (IGC_STATE_USABLE_PARKED);
>  }

Thanks, but why is this important or interesting?  We are not going to
add native threads to Emacs.

Also, AFAIU, MPS docs says to register each thread with it, and your
code doesn't, AFAICT.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Saturday, July 6th, 2024 at 06:20, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> Pip Cet pipcet@protonmail.com writes:
>> 
>> > On Saturday, July 6th, 2024 at 03:39, Gerd Möllmann gerd.moellmann@gmail.com wrote:
>> > 
>> > > Pip Cet pipcet@protonmail.com writes:
>> > > 
>> > > > What I'm doing right now is alternating usleep(10000) and
>> > > > igc_collect() in a secondary thread. That crashes somewhat
>> > > > reproducibly in interactive sessions.
>> > > 
>> > > Could you please make that available in some form?
>> > 
>> > Sure. I was thinking about cleaning it up (usleep is non-standard) and
>> > committing it behind a stress-test option, actually.
>> 
>> Thanks! If it's not too bad performance-wise, I was thinking of running
>> it in the Emacs I'm normally using, in parallel to the rest.
>
> It is very bad since full GCs stop the main thread. However, running
> it once a second is enough to find some bugs and GCs are fairly
> fast...

Ok, thanks. I'll give it a spin when it's there. Alas, my Emacs is
already pretty slow because of of -O0 and
--enable-checking=all,igc_debug. Maybe I can trade something of that in
for the igc-collect.

> (One thing I've noticed is that MPS handles failed scans gracefully;
> we might be able to get away with "interrupting" a scan if inputs or
> signals are pending, but correctness first...)
>
>> > Right now it's dying because specpdl is a union type and GC might hit
>> > while the main thread leaves it in a partially-initialized state. I
>> > vaguely recall turning it into a struct for that reason on another
>> > branch years ago...
>> 
>> Shit. That could mean that we have to scan specpdl amiguously.
>
> I was hoping to avoid that. Maybe it's enough to just clear the pdl
> entries in between modifications, since the values we put in should be
> on the stack or in registers and be pinned.

I tried to do something in umbind_to already, which is not 100% safe I
think (there's a tiny window left, I guess).

But I find it more likely it happens in specbind, when we fill out a new
entry. Maybe we should memclr the entry there for the case that the
entry type is filled out before the rest is valid. Hm.

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Sat, 06 Jul 2024 06:31:14 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> On Saturday, July 6th, 2024 at 06:10, Eli Zaretskii <eliz@gnu.org> wrote:
> > > Date: Fri, 05 Jul 2024 20:35:34 +0000
> > 
> > > From: Pip Cet pipcet@protonmail.com
> > > Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > > 
> > > > > At least we've excluded WIDE_EMACS_INT :-)
> > > > > Which is a pity, IMNSHO, and a major disappointment for me personally,
> > > > > since I'm a happy user of that configuration for many years.
> > > 
> > > Interesting. It's not too hard to fit a 62-bit integer into two 32-bit integers which are not 4-bit aligned, of course. I'm not sure what else would go wrong though :-)
> > 
> > The problem, AFAIU, is the MPS assumption that Lisp objects can fit
> > into a "word", which in their parlance means integral data type whose
> > width is the same as a pointer's. And that is false in WIDE_EMACS_INT
> > builds, because Lisp objects are 64-bit wide, whereas pointers are
> > still 32-bit.
> 
> I may be misunderstanding something. When talking about normal (strong) objects, MPS assumes very little about how the actual objects are represented, as long as they can be turned into references for tracing. I don't think that's going to be a problem. When dealing with weak options, the IA-32 problem does mean that pointers need to be aligned and non-pointers need to be non-aligned or 0, so we'd need to mangle big fixnums before storing them in what, to MPS, is two 32-bit words.

I don't have a clue what you are saying here, sorry.  Too many
references to terminology I cannot relate to Emacs: "references for
tracing", "weak options".

Just by randomly picking keywords from the above, I can tell you that
we do make sure pointers are 8-byte aligned in the 32-bit builds
(which is not easy, at least on MS-Windows, but we succeed anyway).

The way the WIDE_EMACS_INT configuration works, most Lisp objects have
their high 30 bits (out of 64) cleared, the only exception being
fixnums.

Not sure this answers or refutes some of what you wrote.  At the time
Gerd flatly declined to invest any effort in the WIDE_EMACS_INT build,
or even explain what needs to be modified in igc.c and elsewhere to
make that work, so my build of 32-bit Emacs doesn't use that, because
I don't understand MPS innards well enough to do that on my own in
what little time I have to dedicate to this branch.  Just building MPS
with MinGW (a configuration it doesn't support) in a way that passes
its test suite was enough of an effort.  I will be much happier if the
WIDE_EMACS_INT would be supported on the branch.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

> Not sure this answers or refutes some of what you wrote.  At the time
> Gerd flatly declined to invest any effort in the WIDE_EMACS_INT build,
> or even explain what needs to be modified in igc.c and elsewhere to
> make that work, 

Yep. That's early frazzling out at the edges for me. Making nice to have
features essential. Similar for IA-32 -> sofware emulation -> having to
fulfill the MPS requirements Pip was talking about. No one looses
something compared to today when igc doesn't support IA-32, it's
optional.

My 2 cents of course.

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 07:00, Eli Zaretskii <eliz@gnu.org> wrote:
> > Date: Sat, 06 Jul 2024 06:31:14 +0000
> 
> > From: Pip Cet pipcet@protonmail.com
> > Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > 
> > On Saturday, July 6th, 2024 at 06:10, Eli Zaretskii eliz@gnu.org wrote:
> > 
> > > > Date: Fri, 05 Jul 2024 20:35:34 +0000
> > > 
> > > > From: Pip Cet pipcet@protonmail.com
> > > > Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> > > > 
> > > > > > At least we've excluded WIDE_EMACS_INT :-)
> > > > > > Which is a pity, IMNSHO, and a major disappointment for me personally,
> > > > > > since I'm a happy user of that configuration for many years.
> > > > 
> > > > Interesting. It's not too hard to fit a 62-bit integer into two 32-bit integers which are not 4-bit aligned, of course. I'm not sure what else would go wrong though :-)
> > > 
> > > The problem, AFAIU, is the MPS assumption that Lisp objects can fit
> > > into a "word", which in their parlance means integral data type whose
> > > width is the same as a pointer's. And that is false in WIDE_EMACS_INT
> > > builds, because Lisp objects are 64-bit wide, whereas pointers are
> > > still 32-bit.
> > 
> > I may be misunderstanding something. When talking about normal (strong) objects, MPS assumes very little about how the actual objects are represented, as long as they can be turned into references for tracing. I don't think that's going to be a problem. When dealing with weak options, the IA-32 problem does mean that pointers need to be aligned and non-pointers need to be non-aligned or 0, so we'd need to mangle big fixnums before storing them in what, to MPS, is two 32-bit words.
> 
> Just by randomly picking keywords from the above, I can tell you that
> we do make sure pointers are 8-byte aligned in the 32-bit builds
> (which is not easy, at least on MS-Windows, but we succeed anyway).
> 
> The way the WIDE_EMACS_INT configuration works, most Lisp objects have
> their high 30 bits (out of 64) cleared, the only exception being
> fixnums.

Oh. I must be doing something else then, because I'm seeing objects like this one:
(gdb) p/x key                                                                                                                                                   $1 = 0xc0000000a7b4e4e8                                                                                                                                         

IOW, MSB tags in the high 32 bits, a plain pointer in the low 32 bits.

Can you tell me more about your build configuration?

> Not sure this answers or refutes some of what you wrote. At the time
> Gerd flatly declined to invest any effort in the WIDE_EMACS_INT build,
> or even explain what needs to be modified in igc.c and elsewhere to
> make that work, so my build of 32-bit Emacs doesn't use that, because
> I don't understand MPS innards well enough to do that on my own in
> what little time I have to dedicate to this branch. Just building MPS
> with MinGW (a configuration it doesn't support) in a way that passes
> its test suite was enough of an effort. I will be much happier if the
> WIDE_EMACS_INT would be supported on the branch.

WIDE_EMACS_INT with LSB tags, which I don't think we currently support, might be possible. Using MSB tags would require some work, particularly for ambiguous scanning which might need to look at symbols, but I think it's also possible. Weak objects (not "options", sorry) require the whole non-alignment song and dance.

Pip

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 06:46, Eli Zaretskii <eliz@gnu.org> wrote:
> Thanks, but why is this important or interesting? We are not going to
> add native threads to Emacs.

We do want other threads to be able to access MPS-managed memory, don't we?

And the bugs it has caught so far were actual bugs. I believe this is true even for the specpdl thing, though we could avoid that by trusting our thread data more.

> Also, AFAIU, MPS docs says to register each thread with it, and your
> code doesn't, AFAICT.

It needs to be registered as a root if it is one. This one isn't. It also needs to be able to be suspended, but on pthreads that's handled automatically.

You're correct, though, that it's possible this will crash on code that can't actually crash without the extra thread. We need to look at each crash and decide whether it is.

Pip

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Gerd Möllmann wrote:

>> ert-tests.el worries me the most.  There, MPS looks pretty bad compared
>> to the old GC.  (Who would have thought that printing backtraces
>> involves copying and rebalancing interval trees with thousands of nodes?
>> And why does it perform so poorly with a generational GC?)
>
> Hm, sounds almost like a bug to me. The bug being the copying. Why does
> it do that, do you know?

One reason may be that something tries to remove invisible text with
buffer-substring.  That needs to copy part of the interval tree.  But
the copying happens for both, the MPS and the non-MPS version.

When I run

 perf record ../src/emacs -Q --batch -l lisp/emacs-lisp/ert-tests.el
 --eval '(ert-run-tests-batch-and-exit
 "ert-test-\\(parse\\|plist\\|record\\|run-tests-batch-exp\\)")'
 
then the top entries in the perf output for the MPS version looks like:

   9.55%  emacs    emacs                       [.] balance_an_interval
   5.46%  emacs    emacs                       [.] amcSegFix
   5.20%  emacs    emacs                       [.] exec_byte_code
   3.71%  emacs    emacs                       [.] _mps_fix2
   3.10%  emacs    emacs                       [.] fix_lisp_obj
   2.81%  emacs    emacs                       [.] SegSetGrey
   2.37%  emacs    emacs                       [.] shieldQueue
   2.29%  emacs    emacs                       [.] SegFix
   2.24%  emacs    emacs                       [.] is_dflt_fwd
   2.07%  emacs    emacs                       [.] alloc_impl
   2.02%  emacs    emacs                       [.] dflt_scan_obj.constprop.0

and the non-MPS version:

  19.63%  emacs    emacs                 [.] balance_an_interval
  10.22%  emacs    emacs                 [.] exec_byte_code
   9.73%  emacs    emacs                 [.] process_mark_stack
   3.04%  emacs    emacs                 [.] next_interval
   2.42%  emacs    emacs                 [.] sweep_intervals
   2.26%  emacs    emacs                 [.] Fmemq
   2.16%  emacs    emacs                 [.] find_interval
   2.05%  emacs    emacs                 [.] Fcons

So balance_an_interval is pretty high in both, but it seems that the GC
related part is quite a bit bigger for the MPS version.  Maybe it has
something to do with memory barriers.

>> It would be nice to have a way to set a "memory limit".  Preferably with
>> some "out of memory error".  Even aborting would be better than starting
>> to swap.
>
> There is
>
>   MPS_KEY_COMMIT_LIMIT (type size_t) is the maximum amount of main memory,
>   in bytes (1), that the MPS will obtain from the operating system. See
>   mps_arena_commit_limit() for details. The default commit limit is the
>   maximum value of the size_t type.
>
> Never tried that. There are also functions to read/set the limit, so
> maybe we could introduce a DEFVAR with variable watcher for playing with
> it, or a function.

When I add

  MPS_ARGS_ADD (args, MPS_KEY_COMMIT_LIMIT,  1 << 30);

to make_arena then

  make lisp/emacs-lisp/ert-tests

aborts with

  trace.c:1088: Emacs fatal error: assertion failed: band != RankWEAK || rank == band

This looks like a bug.

>> I also think that something needs to be done about the pidigits
>> benchmark.  It's not about the bignums (which I couldn't care less
>> about) but the problem that finalization messages are only processed
>> when Emacs is idle.
>
> Hm, so this one didn't help.
>
>   void
>   garbage_collect (void)
>   {
>   #ifdef HAVE_MPS
>     igc_process_messages ();
>   #endif
>
> Looks like it needs to be put somewhere else.

I think finalize_bignum is ever called for something like this:

 ./src/emacs -Q -batch -eval '
 (dotimes (_ 10000000) (set (quote foo) (ash most-positive-fixnum 10000)))'

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>
>>> ert-tests.el worries me the most.  There, MPS looks pretty bad compared
>>> to the old GC.  (Who would have thought that printing backtraces
>>> involves copying and rebalancing interval trees with thousands of nodes?
>>> And why does it perform so poorly with a generational GC?)
>>
>> Hm, sounds almost like a bug to me. The bug being the copying. Why does
>> it do that, do you know?
>
> One reason may be that something tries to remove invisible text with
> buffer-substring.  That needs to copy part of the interval tree.  But
> the copying happens for both, the MPS and the non-MPS version.

Hm, could be. Thanks!

> When I run
>
>  perf record ../src/emacs -Q --batch -l lisp/emacs-lisp/ert-tests.el
>  --eval '(ert-run-tests-batch-and-exit
>  "ert-test-\\(parse\\|plist\\|record\\|run-tests-batch-exp\\)")'
>  
> then the top entries in the perf output for the MPS version looks like:
>
>    9.55%  emacs    emacs                       [.] balance_an_interval
>    5.46%  emacs    emacs                       [.] amcSegFix
>    5.20%  emacs    emacs                       [.] exec_byte_code
>    3.71%  emacs    emacs                       [.] _mps_fix2
>    3.10%  emacs    emacs                       [.] fix_lisp_obj
>    2.81%  emacs    emacs                       [.] SegSetGrey
>    2.37%  emacs    emacs                       [.] shieldQueue
>    2.29%  emacs    emacs                       [.] SegFix
>    2.24%  emacs    emacs                       [.] is_dflt_fwd
>    2.07%  emacs    emacs                       [.] alloc_impl
>    2.02%  emacs    emacs                       [.] dflt_scan_obj.constprop.0
>
> and the non-MPS version:
>
>   19.63%  emacs    emacs                 [.] balance_an_interval
>   10.22%  emacs    emacs                 [.] exec_byte_code
>    9.73%  emacs    emacs                 [.] process_mark_stack
>    3.04%  emacs    emacs                 [.] next_interval
>    2.42%  emacs    emacs                 [.] sweep_intervals
>    2.26%  emacs    emacs                 [.] Fmemq
>    2.16%  emacs    emacs                 [.] find_interval
>    2.05%  emacs    emacs                 [.] Fcons
>
> So balance_an_interval is pretty high in both, but it seems that the GC
> related part is quite a bit bigger for the MPS version.  Maybe it has
> something to do with memory barriers.

That is_dflt_fwd is so high up in the list at least hints to fact the a
lot of GC work is going on. Hm, ja. I MPS copies a lot of objects during
that, maybe the barriers play a role, yes. Maybe one could park the
arena wile this copying is going on? Which doesn't remove the need to
GC at some point, but I guess it might be faster overall.

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Sat, 06 Jul 2024 09:13:04 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> On Saturday, July 6th, 2024 at 07:00, Eli Zaretskii <eliz@gnu.org> wrote:
> > > Date: Sat, 06 Jul 2024 06:31:14 +0000
> > 
> > The way the WIDE_EMACS_INT configuration works, most Lisp objects have
> > their high 30 bits (out of 64) cleared, the only exception being
> > fixnums.
> 
> Oh. I must be doing something else then, because I'm seeing objects like this one:
> (gdb) p/x key                                                                                                                                                   $1 = 0xc0000000a7b4e4e8                                                                                                                                         
> 
> IOW, MSB tags in the high 32 bits, a plain pointer in the low 32 bits.

Isn't that what I said?  Or do you mean my silly mistake of saying 30
instead of 28?

> Can you tell me more about your build configuration?

Just --with-wide-int, that's all.

> > Not sure this answers or refutes some of what you wrote. At the time
> > Gerd flatly declined to invest any effort in the WIDE_EMACS_INT build,
> > or even explain what needs to be modified in igc.c and elsewhere to
> > make that work, so my build of 32-bit Emacs doesn't use that, because
> > I don't understand MPS innards well enough to do that on my own in
> > what little time I have to dedicate to this branch. Just building MPS
> > with MinGW (a configuration it doesn't support) in a way that passes
> > its test suite was enough of an effort. I will be much happier if the
> > WIDE_EMACS_INT would be supported on the branch.
> 
> WIDE_EMACS_INT with LSB tags, which I don't think we currently support, might be possible. Using MSB tags would require some work, particularly for ambiguous scanning which might need to look at symbols, but I think it's also possible. Weak objects (not "options", sorry) require the whole non-alignment song and dance.

Why would we want to support WIDE_EMACS_INT with LSB tags?

Re: MPS: weak hash tables

[Eli Zaretskii]

> Date: Sat, 06 Jul 2024 09:23:27 +0000
> From: Pip Cet <pipcet@protonmail.com>
> Cc: gerd.moellmann@gmail.com, eller.helmut@gmail.com, emacs-devel@gnu.org
> 
> On Saturday, July 6th, 2024 at 06:46, Eli Zaretskii <eliz@gnu.org> wrote:
> > Thanks, but why is this important or interesting? We are not going to
> > add native threads to Emacs.
> 
> We do want other threads to be able to access MPS-managed memory, don't we?

We do?  Do you mean Lisp threads (created via make-thread)?  Those run
via a different machinery, and should be registered with MPS.

> And the bugs it has caught so far were actual bugs. I believe this is true even for the specpdl thing, though we could avoid that by trusting our thread data more.

You could easily be led astray with this code, since AFAIU it doesn't
work like Emacs should be working.

> > Also, AFAIU, MPS docs says to register each thread with it, and your
> > code doesn't, AFAICT.
> 
> It needs to be registered as a root if it is one. This one isn't. It also needs to be able to be suspended, but on pthreads that's handled automatically.

I have no idea what that means and why it is true, but then I don't
understand MPS well enough.

> You're correct, though, that it's possible this will crash on code that can't actually crash without the extra thread. We need to look at each crash and decide whether it is.

Why not try first the code that will definitely run in Emacs and
should work correctly?  Once that is solved, we can later go to more
exotic test cases.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Helmut Eller <eller.helmut@gmail.com>
> Cc: Pip Cet <pipcet@protonmail.com>,  Eli Zaretskii <eliz@gnu.org>,  Emacs
>  Devel <emacs-devel@gnu.org>
> Date: Sat, 06 Jul 2024 11:47:58 +0200
> 
> On Sat, Jul 06 2024, Gerd Möllmann wrote:
> 
> >> ert-tests.el worries me the most.  There, MPS looks pretty bad compared
> >> to the old GC.  (Who would have thought that printing backtraces
> >> involves copying and rebalancing interval trees with thousands of nodes?
> >> And why does it perform so poorly with a generational GC?)
> >
> > Hm, sounds almost like a bug to me. The bug being the copying. Why does
> > it do that, do you know?
> 
> One reason may be that something tries to remove invisible text with
> buffer-substring.  That needs to copy part of the interval tree.  But
> the copying happens for both, the MPS and the non-MPS version.
> 
> When I run
> 
>  perf record ../src/emacs -Q --batch -l lisp/emacs-lisp/ert-tests.el
>  --eval '(ert-run-tests-batch-and-exit
>  "ert-test-\\(parse\\|plist\\|record\\|run-tests-batch-exp\\)")'
>  
> then the top entries in the perf output for the MPS version looks like:
> 
>    9.55%  emacs    emacs                       [.] balance_an_interval
>    5.46%  emacs    emacs                       [.] amcSegFix
>    5.20%  emacs    emacs                       [.] exec_byte_code
>    3.71%  emacs    emacs                       [.] _mps_fix2
>    3.10%  emacs    emacs                       [.] fix_lisp_obj
>    2.81%  emacs    emacs                       [.] SegSetGrey
>    2.37%  emacs    emacs                       [.] shieldQueue
>    2.29%  emacs    emacs                       [.] SegFix
>    2.24%  emacs    emacs                       [.] is_dflt_fwd
>    2.07%  emacs    emacs                       [.] alloc_impl
>    2.02%  emacs    emacs                       [.] dflt_scan_obj.constprop.0
> 
> and the non-MPS version:
> 
>   19.63%  emacs    emacs                 [.] balance_an_interval
>   10.22%  emacs    emacs                 [.] exec_byte_code
>    9.73%  emacs    emacs                 [.] process_mark_stack
>    3.04%  emacs    emacs                 [.] next_interval
>    2.42%  emacs    emacs                 [.] sweep_intervals
>    2.26%  emacs    emacs                 [.] Fmemq
>    2.16%  emacs    emacs                 [.] find_interval
>    2.05%  emacs    emacs                 [.] Fcons
> 
> So balance_an_interval is pretty high in both, but it seems that the GC
> related part is quite a bit bigger for the MPS version.  Maybe it has
> something to do with memory barriers.

Isn't the call to balance_an_interval made from sweep_buffers and
sweep_strings?  We balance the intervals of the buffers and strings
that survived GC, to make accessing these trees faster.

How did you conclude that rebalancing interval trees is needed for
printing backtraces?

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 09:47, Helmut Eller <eller.helmut@gmail.com> wrote:
> I think finalize_bignum is ever called for something like this:
> 
> ./src/emacs -Q -batch -eval '
> (dotimes (_ 10000000) (set (quote foo) (ash most-positive-fixnum 10000)))'

maybe_garbage_collect() is a nop with MPS, we should probably change that. Needs to happen only some of the time, though, or we'll spend too much time polling for messages (I just tried that, takes forever to build but the code runs with apparently constant memory consumption).

Note that the need to finalize bignums could also be avoided by making GMP use MPS allocation and tracing the limbs. I don't think we should, though, because that'd be messing with GMP internals.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> When I add
>
>   MPS_ARGS_ADD (args, MPS_KEY_COMMIT_LIMIT,  1 << 30);
>
> to make_arena then
>
>   make lisp/emacs-lisp/ert-tests
>
> aborts with
>
>   trace.c:1088: Emacs fatal error: assertion failed: band != RankWEAK || rank == band
>
> This looks like a bug.

I see that too. With the following backtrace

* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 4.1
    frame #0: 0x000000010039d184 emacs`mps_lib_assert_fail(file="/Users/gerd/emacs/github/mps/code/trace.c", line=1088, condition="band != RankWEAK || rank == band") at mpsliban.c:87:3
  * frame #1: 0x00000001003f8538 emacs`traceFindGrey(segReturn=0x000000016fdf9408, rankReturn=0x000000016fdf9404, arena=0x0000000100cd4000, ti=0) at trace.c:1088:11
    frame #2: 0x00000001003d9bf4 emacs`TraceAdvance(trace=0x0000000100cd4b50) at trace.c:1726:9
    frame #3: 0x00000001003d8d44 emacs`TracePoll(workReturn=0x000000016fdf9500, collectWorldReturn=0x000000016fdf9514, globals=0x0000000100cd4008, collectWorldAllowed=1) at trace.c:1849:5
    frame #4: 0x00000001003a5cb0 emacs`ArenaPoll(globals=0x0000000100cd4008) at global.c:745:16
    frame #5: 0x00000001003a89e4 emacs`mps_ap_fill(p_o=0x000000016fdf96b0, mps_ap=0x00000001080018d8, size=24) at mpsi.c:1097:5
    frame #6: 0x00000001002ec0b0 emacs`alloc_impl(size=24, type=IGC_OBJ_CONS, ap=0x00000001080018d8) at igc.c:3578:20
    frame #7: 0x00000001002e68d4 emacs`alloc(size=16, type=IGC_OBJ_CONS) at igc.c:3606:10
    frame #8: 0x00000001002e6864 emacs`igc_make_cons(car=(struct Lisp_Symbol *) $0 = 0x0000000107db2060, cdr=(struct Lisp_Symbol *) $1 = 0x0000000100ab3090) at igc.c:3633:28
    frame #9: 0x00000001001f5e34 emacs`Fcons(car=(struct Lisp_Symbol *) $2 = 0x0000000107db2060, cdr=(struct Lisp_Symbol *) $3 = 0x0000000100ab3090) at alloc.c:2951:10
!gud 2951:10:/Users/gerd/emacs/github/tinker/src/alloc.c
    frame #10: 0x00000001002d1a40 emacs`add_properties(plist=(struct Lisp_Cons *) $4 = 0x000000015509a630, i=0x0000000153947a88, object=(struct Lisp_String *) $5 = 0x0000000107db2098, set_type=TEXT_PROPERTY_REPLACE, destructive=true) at textprop.c:450:40
    frame #11: 0x00000001002cc674 emacs`add_text_properties_1(start=(EMACS_INT) $6 = 0, end=(EMACS_INT) $7 = 3948495, properties=(struct Lisp_Cons *) $8 = 0x000000015509a630, object=(struct Lisp_String *) $9 = 0x0000000107db2098, set_type=TEXT_PROPERTY_REPLACE, destructive=true) at textprop.c:1289:19
    frame #12: 0x00000001002cbe98 emacs`Fadd_text_properties(start=(EMACS_INT) $10 = 0, end=(EMACS_INT) $11 = 3948495, properties=(struct Lisp_Cons *) $12 = 0x000000015509a630, object=(struct Lisp_String *) $13 = 0x0000000107db2098) at textprop.c:1308:10
    frame #13: 0x000000010021f7cc emacs`Fpropertize(nargs=3, args=(struct Lisp_Symbol *) $14 = 0x0000000248b93a90) at editfns.c:3277:3
    frame #14: 0x0000000100231ff4 emacs`funcall_subr(subr=0x0000000100a540e0, numargs=3, args=(struct Lisp_Symbol *) $15 = 0x0000000248b93a90) at eval.c:3258:9
    frame #15: 0x0000000100293450 emacs`exec_byte_code(fun=(struct Lisp_Vector *) $16 = 0x000000010b275460, args_template=256, nargs=0, args=(struct Lisp_Symbol *) $17 = 0x0000000248b93aa8) at bytecode.c:827:

And I have not the slightest idea what that means or how the commit
limit comes into play.

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

>> Hm, so this one didn't help.
>>
>>   void
>>   garbage_collect (void)
>>   {
>>   #ifdef HAVE_MPS
>>     igc_process_messages ();
>>   #endif
>>
>> Looks like it needs to be put somewhere else.
>
> I think finalize_bignum is ever called for something like this:
>
>  ./src/emacs -Q -batch -eval '
>  (dotimes (_ 10000000) (set (quote foo) (ash most-positive-fixnum 10000)))'

Well, turns out garbage_collect called exactly 0 times.

Which poses the question where can we put that igc_process_messages, so
that it doesn't get too expensive (if it is), but is regularly enough
called even if not idle.

Maybe_quit, maybe_gc, specbind? Any other ideas?

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Pip Cet <pipcet@protonmail.com>,  Eli Zaretskii <eliz@gnu.org>,  Emacs
>  Devel <emacs-devel@gnu.org>
> Date: Sat, 06 Jul 2024 13:57:52 +0200
> 
> Helmut Eller <eller.helmut@gmail.com> writes:
> 
> > I think finalize_bignum is ever called for something like this:
> >
> >  ./src/emacs -Q -batch -eval '
> >  (dotimes (_ 10000000) (set (quote foo) (ash most-positive-fixnum 10000)))'
> 
> Well, turns out garbage_collect called exactly 0 times.
> 
> Which poses the question where can we put that igc_process_messages, so
> that it doesn't get too expensive (if it is), but is regularly enough
> called even if not idle.
> 
> Maybe_quit, maybe_gc, specbind? Any other ideas?

maybe_gc, I'd say.  But the conditions for actually calling GC will
have to change, of course.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> Which poses the question where can we put that igc_process_messages, so
>> that it doesn't get too expensive (if it is), but is regularly enough
>> called even if not idle.
>> 
>> Maybe_quit, maybe_gc, specbind? Any other ideas?
>
> maybe_gc, I'd say.  But the conditions for actually calling GC will
> have to change, of course.

Or another idea:

We allocate bignums in igc. Every N bignum allocations, take some time to
process messages and thus finalize them. I have no idea what a good N
would be thpugh. We could try with 1000 and 0.1s, maybe.

This also assumes that only bignums are allocated frequently plus must
be finalized. Don't know if that's true.

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 12:16, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Eli Zaretskii eliz@gnu.org writes:
> 
> > > Which poses the question where can we put that igc_process_messages, so
> > > that it doesn't get too expensive (if it is), but is regularly enough
> > > called even if not idle.
> > > 
> > > Maybe_quit, maybe_gc, specbind? Any other ideas?
> > 
> > maybe_gc, I'd say. But the conditions for actually calling GC will
> > have to change, of course.
> 
> 
> Or another idea:
> 
> We allocate bignums in igc. Every N bignum allocations, take some time to
> process messages and thus finalize them. I have no idea what a good N
> would be thpugh. We could try with 1000 and 0.1s, maybe.
> 
> This also assumes that only bignums are allocated frequently plus must
> be finalized. Don't know if that's true.

I'd say maybe_garbage_collect (with suitable logic in maybe_gc to call it once in a while; but this is the fallback so calling it rarely is okay) plus maybe_finalize (calling it once per 1 MB of allocated finalizable objects would be what I'd try first, though that number may be low) plus the idle loop. That should catch all cases, I think :-)

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: eller.helmut@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 14:16:55 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> Which poses the question where can we put that igc_process_messages, so
> >> that it doesn't get too expensive (if it is), but is regularly enough
> >> called even if not idle.
> >> 
> >> Maybe_quit, maybe_gc, specbind? Any other ideas?
> >
> > maybe_gc, I'd say.  But the conditions for actually calling GC will
> > have to change, of course.
> 
> Or another idea:
> 
> We allocate bignums in igc. Every N bignum allocations, take some time to
> process messages and thus finalize them. I have no idea what a good N
> would be thpugh. We could try with 1000 and 0.1s, maybe.
> 
> This also assumes that only bignums are allocated frequently plus must
> be finalized. Don't know if that's true.

maybe_gc is already called from places which tend to allocate Lisp
objects, so I'd go with that.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>>> Which poses the question where can we put that igc_process_messages, so
>>> that it doesn't get too expensive (if it is), but is regularly enough
>>> called even if not idle.
>>>
>>> Maybe_quit, maybe_gc, specbind? Any other ideas?
>>
>> maybe_gc, I'd say.  But the conditions for actually calling GC will
>> have to change, of course.
>
> Or another idea:
>
> We allocate bignums in igc. Every N bignum allocations, take some time to
> process messages and thus finalize them. I have no idea what a good N
> would be thpugh. We could try with 1000 and 0.1s, maybe.
>
> This also assumes that only bignums are allocated frequently plus must
> be finalized. Don't know if that's true.

I've pushed that with 1000 and 0.1. Let's see.

Helmut, could you please see if that helps with the pi code?

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> Or another idea:
>> 
>> We allocate bignums in igc. Every N bignum allocations, take some time to
>> process messages and thus finalize them. I have no idea what a good N
>> would be thpugh. We could try with 1000 and 0.1s, maybe.
>> 
>> This also assumes that only bignums are allocated frequently plus must
>> be finalized. Don't know if that's true.
>
> I'd say maybe_garbage_collect (with suitable logic in maybe_gc to call
> it once in a while; but this is the fallback so calling it rarely is
> okay) plus maybe_finalize (calling it once per 1 MB of allocated
> finalizable objects would be what I'd try first, though that number
> may be low) plus the idle loop. That should catch all cases, I think
> :-)

Two guys one thought. I've done the maybe_finalize for now.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: eller.helmut@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
>> Date: Sat, 06 Jul 2024 14:16:55 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> Which poses the question where can we put that igc_process_messages, so
>> >> that it doesn't get too expensive (if it is), but is regularly enough
>> >> called even if not idle.
>> >> 
>> >> Maybe_quit, maybe_gc, specbind? Any other ideas?
>> >
>> > maybe_gc, I'd say.  But the conditions for actually calling GC will
>> > have to change, of course.
>> 
>> Or another idea:
>> 
>> We allocate bignums in igc. Every N bignum allocations, take some time to
>> process messages and thus finalize them. I have no idea what a good N
>> would be thpugh. We could try with 1000 and 0.1s, maybe.
>> 
>> This also assumes that only bignums are allocated frequently plus must
>> be finalized. Don't know if that's true.
>
> maybe_gc is already called from places which tend to allocate Lisp
> objects, so I'd go with that.

Right, but I have no good idea how often to call the message handling in
this case. How often is maybe_gc called, and every how many calls would
we then process messages. So, I've done the other thing first. Maybe we
get away wtih that, and that code at least has an idea if handling
messages might be necessary, or more often than usual.

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Eli Zaretskii wrote:

> Isn't the call to balance_an_interval made from sweep_buffers and
> sweep_strings?  We balance the intervals of the buffers and strings
> that survived GC, to make accessing these trees faster.

I don't know; I thought that the interval tree is a red-black tree that
is always balanced.

> How did you conclude that rebalancing interval trees is needed for
> printing backtraces?

What else could cause it in ert-test-run-tests-batch-expensive?

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: eller.helmut@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 14:43:43 +0200
> 
> >> We allocate bignums in igc. Every N bignum allocations, take some time to
> >> process messages and thus finalize them. I have no idea what a good N
> >> would be thpugh. We could try with 1000 and 0.1s, maybe.
> >> 
> >> This also assumes that only bignums are allocated frequently plus must
> >> be finalized. Don't know if that's true.
> >
> > maybe_gc is already called from places which tend to allocate Lisp
> > objects, so I'd go with that.
> 
> Right, but I have no good idea how often to call the message handling in
> this case. How often is maybe_gc called, and every how many calls would
> we then process messages.

maybe_gc is called from eval.c, where the Lisp evaluation happens.  It
is also called when we detect that we are idle (see keyboard.c).

> So, I've done the other thing first. Maybe we
> get away wtih that, and that code at least has an idea if handling
> messages might be necessary, or more often than usual.

I'm surprised that we need to invent solutions for issues that we
already have figured out, instead of simply reusing the wisdom we
already have.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Helmut Eller <eller.helmut@gmail.com>
> Cc: gerd.moellmann@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 15:50:59 +0200
> 
> On Sat, Jul 06 2024, Eli Zaretskii wrote:
> 
> > Isn't the call to balance_an_interval made from sweep_buffers and
> > sweep_strings?  We balance the intervals of the buffers and strings
> > that survived GC, to make accessing these trees faster.
> 
> I don't know; I thought that the interval tree is a red-black tree that
> is always balanced.

No, the interval tree is not a red-black tree.

> > How did you conclude that rebalancing interval trees is needed for
> > printing backtraces?
> 
> What else could cause it in ert-test-run-tests-batch-expensive?

I don't know, and I don't see why we should guess.  Run that under a
debugger with a breakpoint in balance_an_interval that shows the
backtrace, and you will see the answer very quickly.

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Gerd Möllmann wrote:

> Helmut, could you please see if that helps with the pi code?

Yes, it helps:

  ./src/emacs -Q -batch -l \
  ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
  '(elisp-benchmarks-run "pidigits" nil 1)'

finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
version.  And it uses something like 2.8 GB compared to 350 MB of the
non-MPS version (estimated by looking at the RES column in top).

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>
>> Helmut, could you please see if that helps with the pi code?
>
> Yes, it helps:
>
>   ./src/emacs -Q -batch -l \
>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
>   '(elisp-benchmarks-run "pidigits" nil 1)'
>
> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
> version.  And it uses something like 2.8 GB compared to 350 MB of the
> non-MPS version (estimated by looking at the RES column in top).

So 1000 is probably to high for that that use case, or 0.1s is too low,
especially in batch mode. Grmpf. Could you try with 100 instead of 1000?

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Helmut Eller <eller.helmut@gmail.com> writes:
>
>> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>>
>>> Helmut, could you please see if that helps with the pi code?
>>
>> Yes, it helps:
>>
>>   ./src/emacs -Q -batch -l \
>>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
>>   '(elisp-benchmarks-run "pidigits" nil 1)'
>>
>> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
>> version.  And it uses something like 2.8 GB compared to 350 MB of the
>> non-MPS version (estimated by looking at the RES column in top).
>
> So 1000 is probably to high for that that use case, or 0.1s is too low,
> especially in batch mode. Grmpf. Could you try with 100 instead of 1000?

Yeah, it should do all messages in batch mode. I've pushed that.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Helmut Eller <eller.helmut@gmail.com>
>> Cc: gerd.moellmann@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
>> Date: Sat, 06 Jul 2024 15:50:59 +0200
>> 
>> On Sat, Jul 06 2024, Eli Zaretskii wrote:
>> 
>> > Isn't the call to balance_an_interval made from sweep_buffers and
>> > sweep_strings?  We balance the intervals of the buffers and strings
>> > that survived GC, to make accessing these trees faster.
>> 
>> I don't know; I thought that the interval tree is a red-black tree that
>> is always balanced.
>
> No, the interval tree is not a red-black tree.
>
>> > How did you conclude that rebalancing interval trees is needed for
>> > printing backtraces?
>> 
>> What else could cause it in ert-test-run-tests-batch-expensive?
>
> I don't know, and I don't see why we should guess.  Run that under a
> debugger with a breakpoint in balance_an_interval that shows the
> backtrace, and you will see the answer very quickly.

Just for info:

  (defun backtrace-to-string (&optional frames)
    "Format FRAMES, a list of `backtrace-frame' objects, for output.
  Return the result as a string.  If FRAMES is nil, use all
  function calls currently active."
    (substring-no-properties
     (backtrace--to-string
      (or frames (backtrace-get-frames 'backtrace-to-string)))))

which ert uses, calls backteace-get-frames which uses
filtered-buffer-substring and so on, and then we throw all the
properties away. 

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Gerd Möllmann wrote:

>> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
>> version.  And it uses something like 2.8 GB compared to 350 MB of the
>> non-MPS version (estimated by looking at the RES column in top).

Scratch that.  That had some MPS_KEY_COMMIT_LIMIT in there.

> So 1000 is probably to high for that that use case, or 0.1s is too low,
> especially in batch mode. Grmpf. Could you try with 100 instead of 1000?

This is should be better:

N	Seconds	RES
1	65.10	920MB
10      49.59   1GB
50      45.75   1.4GB
100     43.50   2.8GB
500     42.14   2.6GB
1000    41.98   2.6GB

As before the RES column is what I saw in top (sampled every 3 seconds).

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>
>>> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
>>> version.  And it uses something like 2.8 GB compared to 350 MB of the
>>> non-MPS version (estimated by looking at the RES column in top).
>
> Scratch that.  That had some MPS_KEY_COMMIT_LIMIT in there.
>
>> So 1000 is probably to high for that that use case, or 0.1s is too low,
>> especially in batch mode. Grmpf. Could you try with 100 instead of 1000?
>
> This is should be better:
>
> N	Seconds	RES
> 1	65.10	920MB
> 10      49.59   1GB
> 50      45.75   1.4GB
> 100     43.50   2.8GB
> 500     42.14   2.6GB
> 1000    41.98   2.6GB
>
> As before the RES column is what I saw in top (sampled every 3 seconds).

Thanks! I've made it so that in batch mode we don't put a time limit on
processing messages because that made no sense.

Hm. Don't know how to do better at the moement. The message passing
itself is of course costly.

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 14:52, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Helmut Eller eller.helmut@gmail.com writes:
> 
> > On Sat, Jul 06 2024, Gerd Möllmann wrote:
> > 
> > > > finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
> > > > version. And it uses something like 2.8 GB compared to 350 MB of the
> > > > non-MPS version (estimated by looking at the RES column in top).
> > 
> > Scratch that. That had some MPS_KEY_COMMIT_LIMIT in there.
> > 
> > > So 1000 is probably to high for that that use case, or 0.1s is too low,
> > > especially in batch mode. Grmpf. Could you try with 100 instead of 1000?
> > 
> > This is should be better:
> > 
> > N Seconds RES
> > 1 65.10 920MB
> > 10 49.59 1GB
> > 50 45.75 1.4GB
> > 100 43.50 2.8GB
> > 500 42.14 2.6GB
> > 1000 41.98 2.6GB
> > 
> > As before the RES column is what I saw in top (sampled every 3 seconds).
> 
> Thanks! I've made it so that in batch mode we don't put a time limit on
> processing messages because that made no sense.
> 
> Hm. Don't know how to do better at the moement. The message passing
> itself is of course costly.

I wonder how representative that is of actual workloads, though. It does appear mostly to be the cost of finalization, if I deactivate that (and leak the memory instead!) it takes about 6.5 seconds on this machine compared to ~9 on my main Emacs. Totally unscientific, of course, I'm pretty sure I even updated my compiler since compiling vanilla Emacs. Both use nativecomp.

So IF it's worth optimizing this, the thing to look into would be to use MPS-managed memory for GMP bignums, so we don't need a finalizer at all. I think that's quite easy to do, but requires violating the GMP API by accessing internal member fields directly.

I believe Eli is right, though, that we should deviate from what Emacs usually does as little as possible until we've got things working. That means just keeping track of how much we've allocated and calling garbage_collect via maybe_garbage_collect, I think.

As for memory usage, I wonder how much of that is MPS memory and how much is simply the limbs of the bignums, which MPS doesn't know about. My guess is pidgits uses large bignums, but MPS only sees the small mpz_t allocations.

Pip

Re: MPS: weak hash tables

[Helmut Eller]

[-- Attachment #1: Type: text/plain, Size: 673 bytes --]

On Sat, Jul 06 2024, Eli Zaretskii wrote:

>> What else could cause it in ert-test-run-tests-batch-expensive?
>
> I don't know, and I don't see why we should guess.  Run that under a
> debugger with a breakpoint in balance_an_interval that shows the
> backtrace, and you will see the answer very quickly.

Here are the flame graphs; recorded with

  perf record -g -o ../src/emacs -Q --batch -f igc--collect \
  -l lisp/emacs-lisp/ert-tests.el --eval \
  '(ert-run-tests-batch-and-exit
  "ert-test-\\(parse\\|plist\\|record\\|run-tests-batch-exp\\)")'

Both the MPS and non-MPS version compiled with -g -O2
-fno-omit-frame-pointer.  I don't see the anything very quickly.


[-- Attachment #2: flamegraph-mps.html.gz --]
[-- Type: application/gzip, Size: 64956 bytes --]

[-- Attachment #3: flamegraph-non-mps.html.gz --]
[-- Type: application/gzip, Size: 52693 bytes --]

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> I wonder how representative that is of actual workloads, though. 

It isn't, for sure :-).

> It does appear mostly to be the cost of finalization, if I deactivate
> that (and leak the memory instead!) it takes about 6.5 seconds on this
> machine compared to ~9 on my main Emacs. Totally unscientific, of
> course, I'm pretty sure I even updated my compiler since compiling
> vanilla Emacs. Both use nativecomp.

I think the same. I under the impression that probably many millions of
bignums are used, each of which requires inter-thread communication and
so on. That's quite expensive if true.

> So IF it's worth optimizing this, the thing to look into would be to
> use MPS-managed memory for GMP bignums, so we don't need a finalizer
> at all. I think that's quite easy to do, but requires violating the
> GMP API by accessing internal member fields directly.

We have already this in bignum.c

  mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);

Haven't read the GMP docs yet, but that looks like something that could
be used.

> I believe Eli is right, though, that we should deviate from what Emacs
> usually does as little as possible until we've got things working.
> That means just keeping track of how much we've allocated and calling
> garbage_collect via maybe_garbage_collect, I think.

Can you explain? I mean I agree in general, but in this case I'm not so
sure. What I've currently implemented is basically a function of the
number of allocated finalizable objects and only finalizable objects pay
the price. The size of allocated memory overall, i.e. counting the bytes
in alloc_impl doesn't contain the information.

> As for memory usage, I wonder how much of that is MPS memory and how
> much is simply the limbs of the bignums, which MPS doesn't know about.
> My guess is pidgits uses large bignums, but MPS only sees the small
> mpz_t allocations.

Could be. Do we know the algorithm pidigits uses? Maybe one can find out
if that uses large bignums.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Helmut Eller <eller.helmut@gmail.com>
> Cc: gerd.moellmann@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 18:20:02 +0200
> 
> On Sat, Jul 06 2024, Eli Zaretskii wrote:
> 
> >> What else could cause it in ert-test-run-tests-batch-expensive?
> >
> > I don't know, and I don't see why we should guess.  Run that under a
> > debugger with a breakpoint in balance_an_interval that shows the
> > backtrace, and you will see the answer very quickly.
> 
> Here are the flame graphs; recorded with
> 
>   perf record -g -o ../src/emacs -Q --batch -f igc--collect \
>   -l lisp/emacs-lisp/ert-tests.el --eval \
>   '(ert-run-tests-batch-and-exit
>   "ert-test-\\(parse\\|plist\\|record\\|run-tests-batch-exp\\)")'
> 
> Both the MPS and non-MPS version compiled with -g -O2
> -fno-omit-frame-pointer.  I don't see the anything very quickly.

AFAIU, we call buffer-string, which then must copy the interval tree
of the buffer to the interval tree of the string we create.

Is that what you wanted to know and understand?

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Eli Zaretskii wrote:

>> What else could cause it in ert-test-run-tests-batch-expensive?
[...]
> AFAIU, we call buffer-string, which then must copy the interval tree
> of the buffer to the interval tree of the string we create.
>
> Is that what you wanted to know and understand?

> AFAIU, we call buffer-string, which then must copy the interval tree
> of the buffer to the interval tree of the string we create.
>
> Is that what you wanted to know and understand?

Well, I wanted to know if it could be something other than printing
backtraces.  E.g. ert creating some annotated log buffer.

Anyway, it look likes the MPS version is slower and needs twice the
memory than the non-MPS version.

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 2246 bytes --]

On Saturday, July 6th, 2024 at 16:31, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > I wonder how representative that is of actual workloads, though.
> 
> It isn't, for sure :-).
> 
> > It does appear mostly to be the cost of finalization, if I deactivate
> > that (and leak the memory instead!) it takes about 6.5 seconds on this
> > machine compared to ~9 on my main Emacs. Totally unscientific, of
> > course, I'm pretty sure I even updated my compiler since compiling
> > vanilla Emacs. Both use nativecomp.
> 
> I think the same. I under the impression that probably many millions of
> bignums are used, each of which requires inter-thread communication and
> so on. That's quite expensive if true.
> 
> > So IF it's worth optimizing this, the thing to look into would be to
> > use MPS-managed memory for GMP bignums, so we don't need a finalizer
> > at all. I think that's quite easy to do, but requires violating the
> > GMP API by accessing internal member fields directly.
> 
> 
> We have already this in bignum.c
> 
> mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
> 
> Haven't read the GMP docs yet, but that looks like something that could
> be used.

Patch attached, couldn't resist :-)

Memory usage is perfectly acceptable with this patch, but it does do a lot of GC.

> > I believe Eli is right, though, that we should deviate from what Emacs
> > usually does as little as possible until we've got things working.
> > That means just keeping track of how much we've allocated and calling
> > garbage_collect via maybe_garbage_collect, I think.

> Can you explain? I mean I agree in general, but in this case I'm not so
> sure. What I've currently implemented is basically a function of the
> number of allocated finalizable objects and only finalizable objects pay
> the price. The size of allocated memory overall, i.e. counting the bytes
> in alloc_impl doesn't contain the information.

But it's probably a better indicator of how much GC activity happened, and that influences how many finalization messages there would be, assuming that an approximately constant percentage of objects is finalizable...

Pip

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0002-mps-bignums.patch --]
[-- Type: text/x-patch; name=0002-mps-bignums.patch, Size: 2762 bytes --]

diff --git a/src/bignum.c b/src/bignum.c
index 1fe195d78ea..330fdf4324c 100644
--- a/src/bignum.c
+++ b/src/bignum.c
@@ -20,12 +20,13 @@
 #include <config.h>
 
 #include "bignum.h"
-
 #include "lisp.h"
 
 #include <math.h>
 #include <stdlib.h>
 
+#include "igc.h"
+
 /* mpz global temporaries.  Making them global saves the trouble of
    properly using mpz_init and mpz_clear on temporaries even when
    storage is exhausted.  Admittedly this is not ideal.  An mpz value
@@ -34,18 +35,29 @@
    rounddiv_q and rounding_driver both need four and time_arith needs
    five.  */
 
-mpz_t mpz[5];
+mpz_t mpz[5] = { 0, };
+
+static void *
+xmalloc_for_gmp (size_t size)
+{
+  return igc_alloc_bytes (size);
+}
 
 static void *
 xrealloc_for_gmp (void *ptr, size_t ignore, size_t size)
 {
-  return xrealloc (ptr, size);
+  if (size > ignore)
+    {
+      void *ret = xmalloc_for_gmp (size);
+      memcpy (ret, ptr, ignore);
+      return ret;
+    }
+  return ptr;
 }
 
 static void
 xfree_for_gmp (void *ptr, size_t ignore)
 {
-  xfree (ptr);
 }
 
 void
@@ -62,8 +74,10 @@ init_bignum (void)
      program execution.  A 'longjmp' or throwing a C++ exception will
      have undefined results."  But xmalloc and xrealloc do call
      'longjmp'.  */
-  mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
+  mp_set_memory_functions (xmalloc_for_gmp, xrealloc_for_gmp, xfree_for_gmp);
 
+  for (int i = 0; i < ARRAYELTS (mpz); i++)
+    igc_root_create_exact_ptr (&mpz[i][0]._mp_d);
   for (int i = 0; i < ARRAYELTS (mpz); i++)
     mpz_init (mpz[i]);
 }
diff --git a/src/igc.c b/src/igc.c
index ccfa136d258..f2fa3270765 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -2170,6 +2170,19 @@ fix_marker (mps_ss_t ss, struct Lisp_Marker *m)
   return MPS_RES_OK;
 }
 
+static mps_res_t
+fix_bignum (mps_ss_t ss, struct Lisp_Bignum *m)
+{
+  MPS_SCAN_BEGIN (ss)
+  {
+    mps_addr_t ref = m->value[0]._mp_d;
+    IGC_FIX12_RAW (ss, &ref);
+    m->value[0]._mp_d = ref;
+  }
+  MPS_SCAN_END (ss);
+  return MPS_RES_OK;
+}
+
 static mps_res_t
 fix_finalizer (mps_ss_t ss, struct Lisp_Finalizer *f)
 {
@@ -2375,6 +2388,7 @@ fix_vector (mps_ss_t ss, struct Lisp_Vector *v)
 	break;
 
       case PVEC_BIGNUM:
+	IGC_FIX_CALL_FN (ss, struct Lisp_Bignum, v, fix_bignum);
 	break;
 
       case PVEC_NATIVE_COMP_UNIT:
@@ -3195,7 +3209,6 @@ maybe_finalize (mps_addr_t client, enum pvec_type tag)
   mps_addr_t ref = client_to_base (client);
   switch (tag)
     {
-    case PVEC_BIGNUM:
     case PVEC_FONT:
     case PVEC_THREAD:
     case PVEC_MUTEX:
@@ -3210,6 +3223,7 @@ maybe_finalize (mps_addr_t client, enum pvec_type tag)
       mps_finalize (global_igc->arena, &ref);
       break;
 
+    case PVEC_BIGNUM:
 #ifndef IN_MY_FORK
     case PVEC_OBARRAY:
 #endif

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Helmut Eller <eller.helmut@gmail.com>
> Cc: gerd.moellmann@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 18:48:26 +0200
> 
> On Sat, Jul 06 2024, Eli Zaretskii wrote:
> 
> >> What else could cause it in ert-test-run-tests-batch-expensive?
> [...]
> > AFAIU, we call buffer-string, which then must copy the interval tree
> > of the buffer to the interval tree of the string we create.
> >
> > Is that what you wanted to know and understand?
> 
> Well, I wanted to know if it could be something other than printing
> backtraces.  E.g. ert creating some annotated log buffer.

The backtrace is inserted into a special backtrace buffer.  The
backtrace buffer uses 'invisible' text properties to hide long lines.
Then the 'invisible' properties need to be removed when the backtrace
is prepared for display on the terminal (which is what ERT wants to
do, I believe).

> Anyway, it look likes the MPS version is slower and needs twice the
> memory than the non-MPS version.

Do you understand why?

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> We have already this in bignum.c
>> 
>> mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
>> 
>> Haven't read the GMP docs yet, but that looks like something that could
>> be used.
>
> Patch attached, couldn't resist :-)

Haha :-). I'm all for it!

> Memory usage is perfectly acceptable with this patch, but it does do a
> lot of GC.

What do the timings say?

>> > I believe Eli is right, though, that we should deviate from what Emacs
>> > usually does as little as possible until we've got things working.
>> > That means just keeping track of how much we've allocated and calling
>> > garbage_collect via maybe_garbage_collect, I think.
>
>> Can you explain? I mean I agree in general, but in this case I'm not so
>> sure. What I've currently implemented is basically a function of the
>> number of allocated finalizable objects and only finalizable objects pay
>> the price. The size of allocated memory overall, i.e. counting the bytes
>> in alloc_impl doesn't contain the information.
>
> But it's probably a better indicator of how much GC activity happened,
> and that influences how many finalization messages there would be,
> assuming that an approximately constant percentage of objects is
> finalizable...

Hm. I'm not really convinced the total amount allocated is a better
predictor for how many finalzation msgs we might expect than the real
number of objects for which we might expect finalization messages.

But whatever. Something for later, maybe.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Hm. I'm not really convinced the total amount allocated is a better
> predictor for how many finalzation msgs we might expect than the real
> number of objects for which we might expect finalization messages.

Forgot to add - because there is no assumption of a constant factor and
so on.

Re: MPS: weak hash tables

[Helmut Eller]

On Sat, Jul 06 2024, Eli Zaretskii wrote:

>> Anyway, it look likes the MPS version is slower and needs twice the
>> memory than the non-MPS version.
>
> Do you understand why?

No.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Helmut Eller <eller.helmut@gmail.com>
>> Cc: gerd.moellmann@gmail.com,  pipcet@protonmail.com,  emacs-devel@gnu.org
>> Date: Sat, 06 Jul 2024 18:48:26 +0200
>> 
>> On Sat, Jul 06 2024, Eli Zaretskii wrote:
>> 
>> >> What else could cause it in ert-test-run-tests-batch-expensive?
>> [...]
>> > AFAIU, we call buffer-string, which then must copy the interval tree
>> > of the buffer to the interval tree of the string we create.
>> >
>> > Is that what you wanted to know and understand?
>> 
>> Well, I wanted to know if it could be something other than printing
>> backtraces.  E.g. ert creating some annotated log buffer.
>
> The backtrace is inserted into a special backtrace buffer.  The
> backtrace buffer uses 'invisible' text properties to hide long lines.
> Then the 'invisible' properties need to be removed when the backtrace
> is prepared for display on the terminal (which is what ERT wants to
> do, I believe).

I don't know where the invisible text property comes into play. What ERT
does is this:

               (with-temp-buffer
               ...
                   (insert (backtrace-to-string
                            (ert-test-result-with-condition-backtrace result))))
                 (if (not ert-batch-backtrace-right-margin)
                     (message "%s"
                              (buffer-substring-no-properties (point-min)
                                                              (point-max)))
                   (goto-char (point-min))
                   (while (not (eobp))
                     (let ((start (point))
                           (end (line-end-position)))
                       (setq end (min end
                                      (+ start
                                         ert-batch-backtrace-right-margin)))
                       (message "%s" (buffer-substring-no-properties
                                      start end)))
                     (forward-line 1))))

Re: MPS: weak hash tables

[Pip Cet]

On Saturday, July 6th, 2024 at 17:28, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > > We have already this in bignum.c
> > > 
> > > mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
> > > 
> > > Haven't read the GMP docs yet, but that looks like something that could
> > > be used.
> > 
> > Patch attached, couldn't resist :-)
> 
> 
> Haha :-). I'm all for it!
> 
> > Memory usage is perfectly acceptable with this patch, but it does do a
> > lot of GC.
> 
> 
> What do the timings say?

Horrible things. Unacceptably slow. Sufficiently so that I looked into the generation parameters and randomly changed them, and now it's faster than vanilla Emacs?! Does that make sense to you, or is it more likely I'm being tricked by something silly like CPU speed?

All I did was change:

-  mps_gen_param_s gens[] = { { 128000, 0.8 }, { 5 * 128000, 0.4 } };
+  mps_gen_param_s gens[] = { { 64000, 0.8 }, { 5 * 64000, 0.4 }, { 10 * 64000, 0.3 }, };

but that was a totally random guess...

Again, I may just be doing something wrong.

> > > > I believe Eli is right, though, that we should deviate from what Emacs
> > > > usually does as little as possible until we've got things working.
> > > > That means just keeping track of how much we've allocated and calling
> > > > garbage_collect via maybe_garbage_collect, I think.
> > 
> > > Can you explain? I mean I agree in general, but in this case I'm not so
> > > sure. What I've currently implemented is basically a function of the
> > > number of allocated finalizable objects and only finalizable objects pay
> > > the price. The size of allocated memory overall, i.e. counting the bytes
> > > in alloc_impl doesn't contain the information.
> > 
> > But it's probably a better indicator of how much GC activity happened,
> > and that influences how many finalization messages there would be,
> > assuming that an approximately constant percentage of objects is
> > finalizable...
> 
> 
> Hm. I'm not really convinced the total amount allocated is a better
> predictor for how many finalzation msgs we might expect than the real
> number of objects for which we might expect finalization messages.

Now that you put it like that, maybe the case I've been worrying about (phase one of the program creates a huge number of live finalizable objects; phase two stops creating them; finalizable objects never get finalized because no new ones are being created) isn't that likely. Anyway, your code works, so it wins :-)

> But whatever. Something for later, maybe.

Definitely.

Pip

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Helmut Eller <eller.helmut@gmail.com>,  pipcet@protonmail.com,
>   emacs-devel@gnu.org
> Date: Sat, 06 Jul 2024 20:14:21 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > The backtrace is inserted into a special backtrace buffer.  The
> > backtrace buffer uses 'invisible' text properties to hide long lines.
> > Then the 'invisible' properties need to be removed when the backtrace
> > is prepared for display on the terminal (which is what ERT wants to
> > do, I believe).
> 
> I don't know where the invisible text property comes into play. What ERT
> does is this:

It isn't in ERT, it's in backtrace.el.

>                (with-temp-buffer
>                ...
>                    (insert (backtrace-to-string
>                             (ert-test-result-with-condition-backtrace result))))
>                  (if (not ert-batch-backtrace-right-margin)
>                      (message "%s"
>                               (buffer-substring-no-properties (point-min)
>                                                               (point-max)))
>                    (goto-char (point-min))
>                    (while (not (eobp))
>                      (let ((start (point))
>                            (end (line-end-position)))
>                        (setq end (min end
>                                       (+ start
>                                          ert-batch-backtrace-right-margin)))
>                        (message "%s" (buffer-substring-no-properties
>                                       start end)))
>                      (forward-line 1))))

As you see, it calls backtrace.el functions (look there to see what
they do), and then removes properties from the text produced by
backtrace.el functions.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> What do the timings say?
>
> Horrible things. Unacceptably slow. Sufficiently so that I looked into
> the generation parameters and randomly changed them, and now it's
> faster than vanilla Emacs?! Does that make sense to you, or is it more
> likely I'm being tricked by something silly like CPU speed?

Good tension building :-)

>
> All I did was change:
>
> -  mps_gen_param_s gens[] = { { 128000, 0.8 }, { 5 * 128000, 0.4 } };
> +  mps_gen_param_s gens[] = { { 64000, 0.8 }, { 5 * 64000, 0.4 }, { 10 * 64000, 0.3 }, };
>
> but that was a totally random guess...

Wow, one of the knobs I always wanted to play with but couldn't figure
out the rules :-).

> Again, I may just be doing something wrong.

Hm, what might be happening? I guess we can ignore the mortality because
MPS says these values are only initial estimates, and it computes
them itself over time.

So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
makes sense since we now have GMP objects, but a dramatic improvement?

The number of generations? Maybe MPS gets away, in the 3 gens case, with
collecting gen1 and 2 most of the time if gen1 is not enough, which
means 6 * 64, while in the 2 gens case, when it runs out of space
in gen1 it directly has to handle gen1 + gen2 = 12 * 64M?

That's the only thing I can come up with ATM. Complete guesswork, of
course. I wonder how one would find an "optimal" configuration at all.

Helmut, do you perhaps have an idea?

And could one do something with telemetry to optimize generations? Do
they mention something like that?

Re: MPS: weak hash tables

[Ihor Radchenko]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
> makes sense since we now have GMP objects, but a dramatic improvement?
> ...
>
> That's the only thing I can come up with ATM. Complete guesswork, of
> course. I wonder how one would find an "optimal" configuration at all.

I feel kind of silly, but
https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
maybe? It has an example of "dramatic improvement".

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: MPS: weak hash tables

[Gerd Möllmann]

Ihor Radchenko <yantar92@posteo.net> writes:

> Gerd Möllmann <gerd.moellmann@gmail.com> writes:
>
>> So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
>> makes sense since we now have GMP objects, but a dramatic improvement?
>> ...
>>
>> That's the only thing I can come up with ATM. Complete guesswork, of
>> course. I wonder how one would find an "optimal" configuration at all.
>
> I feel kind of silly, but
> https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
> maybe? It has an example of "dramatic improvement".

Thanks, Ihor!

(Shows it again - I don't listen, I don't read ... :-))

Re: MPS: weak hash tables

[Gerd Möllmann]

Ihor Radchenko <yantar92@posteo.net> writes:

> Gerd Möllmann <gerd.moellmann@gmail.com> writes:
>
>> So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
>> makes sense since we now have GMP objects, but a dramatic improvement?
>> ...
>>
>> That's the only thing I can come up with ATM. Complete guesswork, of
>> course. I wonder how one would find an "optimal" configuration at all.
>
> I feel kind of silly, but
> https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
> maybe? It has an example of "dramatic improvement".

Interestingly, the 3 gens have the opposite effect with the Helmut showed.

   master       passed  27/54  ert-test-run-tests-batch-expensive (5.857224 sec)
   2-gen        passed  27/54  ert-test-run-tests-batch-expensive (80.113908 sec)
   3-gen        passed  27/54  ert-test-run-tests-batch-expensive (142.356406 sec)

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Ihor Radchenko <yantar92@posteo.net> writes:
>
>> Gerd Möllmann <gerd.moellmann@gmail.com> writes:
>>
>>> So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
>>> makes sense since we now have GMP objects, but a dramatic improvement?
>>> ...
>>>
>>> That's the only thing I can come up with ATM. Complete guesswork, of
>>> course. I wonder how one would find an "optimal" configuration at all.
>>
>> I feel kind of silly, but
>> https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
>> maybe? It has an example of "dramatic improvement".
>
> Interestingly, the 3 gens have the opposite effect with the Helmut showed.
>
>    master       passed  27/54  ert-test-run-tests-batch-expensive (5.857224 sec)
>    2-gen        passed  27/54  ert-test-run-tests-batch-expensive (80.113908 sec)
>    3-gen        passed  27/54  ert-test-run-tests-batch-expensive (142.356406 sec)

And, BTW, if someone knows why the test is named expensive please let me
know. I suppose someone must have had an idea when naming the test. I
don't see it.

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 04:27, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Ihor Radchenko yantar92@posteo.net writes:
> > Gerd Möllmann gerd.moellmann@gmail.com writes:
> > 
> > > So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
> > > makes sense since we now have GMP objects, but a dramatic improvement?
> > > ...
> > > 
> > > That's the only thing I can come up with ATM. Complete guesswork, of
> > > course. I wonder how one would find an "optimal" configuration at all.
> > 
> > I feel kind of silly, but
> > https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
> > maybe? It has an example of "dramatic improvement".
> 
> Interestingly, the 3 gens have the opposite effect with the Helmut showed.
> 
> master passed 27/54 ert-test-run-tests-batch-expensive (5.857224 sec)
> 2-gen passed 27/54 ert-test-run-tests-batch-expensive (80.113908 sec)
> 3-gen passed 27/54 ert-test-run-tests-batch-expensive (142.356406 sec)

I'm confused by that test. I see similar results to you when I "make lisp/emacs-lisp/ert-tests", but when I run the test directly it finishes quickly:

$ ../src/emacs -Q --batch -f igc--collect -l lisp/emacs-lisp/ert-tests.el --eval '(ert-run-tests-batch-and-exit "ert-test-run-tests-batch-expensive")'

Running 1 tests (2024-07-07 06:00:57-0000, selector ‘"ert-test-run-tests-batch-expensive"’)
   passed  1/1  ert-test-run-tests-batch-expensive (1.079868 sec)

Ran 1 tests, 1 results as expected, 0 unexpected (2024-07-07 06:00:58-0000, 1.080000 sec)


What's going on here?

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Sunday, July 7th, 2024 at 04:27, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> Ihor Radchenko yantar92@posteo.net writes:
>> > Gerd Möllmann gerd.moellmann@gmail.com writes:
>> > 
>> > > So, we had 14 * 64M total before, and 16 * 64M afterwards. A bit more
>> > > makes sense since we now have GMP objects, but a dramatic improvement?
>> > > ...
>> > > 
>> > > That's the only thing I can come up with ATM. Complete guesswork, of
>> > > course. I wonder how one would find an "optimal" configuration at all.
>> > 
>> > I feel kind of silly, but
>> > https://memory-pool-system.readthedocs.io/en/latest/guide/perf.html
>> > maybe? It has an example of "dramatic improvement".
>> 
>> Interestingly, the 3 gens have the opposite effect with the Helmut showed.
>> 
>> master passed 27/54 ert-test-run-tests-batch-expensive (5.857224 sec)
>> 2-gen passed 27/54 ert-test-run-tests-batch-expensive (80.113908 sec)
>> 3-gen passed 27/54 ert-test-run-tests-batch-expensive (142.356406 sec)
>
> I'm confused by that test. I see similar results to you when I "make lisp/emacs-lisp/ert-tests", but when I run the test directly it finishes quickly:
>
> $ ../src/emacs -Q --batch -f igc--collect -l lisp/emacs-lisp/ert-tests.el --eval '(ert-run-tests-batch-and-exit "ert-test-run-tests-batch-expensive")'
>
> Running 1 tests (2024-07-07 06:00:57-0000, selector ‘"ert-test-run-tests-batch-expensive"’)
>    passed  1/1  ert-test-run-tests-batch-expensive (1.079868 sec)
>
> Ran 1 tests, 1 results as expected, 0 unexpected (2024-07-07 06:00:58-0000, 1.080000 sec)
>
>
> What's going on here?
>
> Pip

I see the same

  % ../src/emacs -Q --batch -f igc--collect -l lisp/emacs-lisp/ert-tests.el --eval '(ert-run-tests-batch-and-exit "ert-test-run-tests-batch-expensive")'
  Running 1 tests (2024-07-07 09:29:07+0200, selector ‘"ert-test-run-tests-batch-expensive"’)
     passed  1/1  ert-test-run-tests-batch-expensive (2.679200 sec)

  Ran 1 tests, 1 results as expected, 0 unexpected (2024-07-07 09:29:10+0200, 2.679337 sec)

3-gen case, 140s down to 2.5. Wot?

Re: MPS: weak hash tables

[Helmut Eller]

On Sun, Jul 07 2024, Pip Cet wrote:
> What's going on here?

How likely is a bug in the tree balancing code?  I find it rather odd
that the old GC rebalances interval trees during the sweep phase.

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sun, Jul 07 2024, Pip Cet wrote:
>> What's going on here?
>
> How likely is a bug in the tree balancing code?  I find it rather odd
> that the old GC rebalances interval trees during the sweep phase.

I'd say not very likely but of course not impossible.

The problem with the interval tree is that it isn't self-balancing like
say a red-black tree. It isn't using an algorithm that I recognize.
Already when I wrote the new redisplay code it was a problem that the
tree sometimes degraded for which I added more calls to balance it.

Both string and buffer intervals are balanced in the swepp phase of the
old GC I see.

Hm, maybe we are missing out on something here, in igc. I don't remember
that I balance in igc.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Helmut Eller <eller.helmut@gmail.com> writes:
>
>> On Sun, Jul 07 2024, Pip Cet wrote:
>>> What's going on here?
>>
>> How likely is a bug in the tree balancing code?  I find it rather odd
>> that the old GC rebalances interval trees during the sweep phase.
>
> I'd say not very likely but of course not impossible.
>
> The problem with the interval tree is that it isn't self-balancing like
> say a red-black tree. It isn't using an algorithm that I recognize.
> Already when I wrote the new redisplay code it was a problem that the
> tree sometimes degraded for which I added more calls to balance it.
>
> Both string and buffer intervals are balanced in the swepp phase of the
> old GC I see.
>
> Hm, maybe we are missing out on something here, in igc. I don't remember
> that I balance in igc.

I've also run the slow version of the test, when it happens to be slow
which is a mystery, under Instruments, which is kind of the shitty
equivalent of perf on macOS.

From the little I see there, something I don't know is concatenating
strings, and adding text properties to them. This allocates conses and
intervals. The allocation point is running out of reserved memory,
mps_ap_fill is called, and MPS scans like mad. That's where the time
goes. Alone 13% of the whole time is spent in fix_cons for example.

More I can't see with the tools I have available here. Maybe intersting
could be that balance_intervals doesn't show up here, but that could be
due to the differences in barrier implementation on macOS.

And the good question is of course why is the test fast when invoked
like Pip showed? 

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 08:24, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Gerd Möllmann gerd.moellmann@gmail.com writes:
> > Helmut Eller eller.helmut@gmail.com writes:
> > > On Sun, Jul 07 2024, Pip Cet wrote:
> > > > What's going on here?
> > > 
> > > How likely is a bug in the tree balancing code? I find it rather odd
> > > that the old GC rebalances interval trees during the sweep phase.
> > 
> > I'd say not very likely but of course not impossible.
> > 
> > The problem with the interval tree is that it isn't self-balancing like
> > say a red-black tree. It isn't using an algorithm that I recognize.
> > Already when I wrote the new redisplay code it was a problem that the
> > tree sometimes degraded for which I added more calls to balance it.
> > 
> > Both string and buffer intervals are balanced in the swepp phase of the
> > old GC I see.
> > 
> > Hm, maybe we are missing out on something here, in igc. I don't remember
> > that I balance in igc.

Do we remove intervals at all with igc? It looks to me like they're partially-weak objects, effectively, and we scan them strongly, removing them only when the buffer dies?

> I've also run the slow version of the test, when it happens to be slow
> which is a mystery, under Instruments, which is kind of the shitty
> equivalent of perf on macOS.
> 
> From the little I see there, something I don't know is concatenating
> strings, and adding text properties to them. This allocates conses and
> intervals. The allocation point is running out of reserved memory,
> mps_ap_fill is called, and MPS scans like mad. That's where the time
> goes. Alone 13% of the whole time is spent in fix_cons for example.
> 
> More I can't see with the tools I have available here. Maybe intersting
> could be that balance_intervals doesn't show up here, but that could be
> due to the differences in barrier implementation on macOS.
> 
> And the good question is of course why is the test fast when invoked
> like Pip showed?

Well, the backtrace that's scanned lists all tests that have previously run (and their results), and thus it's a lot larger when there are more preceding tests.

And if I modify things a little and make the preceding test fail, the problem test doesn't seem to finish at all, and uses many gigabytes of memory...

Very strange.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

>> Hm, maybe we are missing out on something here, in igc. I don't remember
>> that I balance in igc.

I've pushed something for buffer intervals which I think should suffice,
given the fact that we balance all over the place anyway. For strings, I
don't see how we could do something.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> > Hm, maybe we are missing out on something here, in igc. I don't remember
>> > that I balance in igc.
>
> Do we remove intervals at all with igc? It looks to me like they're
> partially-weak objects, effectively, and we scan them strongly,
> removing them only when the buffer dies?

Balancing only changes the tree structure, without freeing nodes, AFAIR.
But that could be wrong. It's been a long time since I looked closer at
that tree.

Wrt to weakness, I don't think there are weak references. The big
difference to the non-MPS case is that struct interval is subject to GC
at all, they are malloc'd without igc. I didn't see another way to
handle their plist otherwise. Making them malloc'd roots would have
meant too many roots for my taste. I have currently ca. 20.000 live
intervals for example, after GC.
>
>> I've also run the slow version of the test, when it happens to be slow
>> which is a mystery, under Instruments, which is kind of the shitty
>> equivalent of perf on macOS.
>> 
>> From the little I see there, something I don't know is concatenating
>> strings, and adding text properties to them. This allocates conses and
>> intervals. The allocation point is running out of reserved memory,
>> mps_ap_fill is called, and MPS scans like mad. That's where the time
>> goes. Alone 13% of the whole time is spent in fix_cons for example.
>> 
>> More I can't see with the tools I have available here. Maybe intersting
>> could be that balance_intervals doesn't show up here, but that could be
>> due to the differences in barrier implementation on macOS.
>> 
>> And the good question is of course why is the test fast when invoked
>> like Pip showed?
>
> Well, the backtrace that's scanned lists all tests that have
> previously run (and their results), and thus it's a lot larger when
> there are more preceding tests.
>
> And if I modify things a little and make the preceding test fail, the
> problem test doesn't seem to finish at all, and uses many gigabytes of
> memory...
>
> Very strange.

Yeah. I don't get the reason why it is allocating that much.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

>> Well, the backtrace that's scanned lists all tests that have
>> previously run (and their results), and thus it's a lot larger when
>> there are more preceding tests.

And why the heck is that the case in the first place? Another thing I
don't get.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Helmut Eller <eller.helmut@gmail.com>,  Ihor Radchenko
>  <yantar92@posteo.net>,  Eli Zaretskii <eliz@gnu.org>,  emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 11:24:11 +0200
> 
> Pip Cet <pipcet@protonmail.com> writes:
> 
> >> > Hm, maybe we are missing out on something here, in igc. I don't remember
> >> > that I balance in igc.
> >
> > Do we remove intervals at all with igc? It looks to me like they're
> > partially-weak objects, effectively, and we scan them strongly,
> > removing them only when the buffer dies?
> 
> Balancing only changes the tree structure, without freeing nodes, AFAIR.
> But that could be wrong. It's been a long time since I looked closer at
> that tree.

We free nodes in sweep_intervals.

Re: MPS: weak hash tables

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 1514 bytes --]

On Sunday, July 7th, 2024 at 09:24, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> > > > Hm, maybe we are missing out on something here, in igc. I don't remember
> > > > that I balance in igc.
> > 
> > Do we remove intervals at all with igc? It looks to me like they're
> > partially-weak objects, effectively, and we scan them strongly,
> > removing them only when the buffer dies?
> 
> 
> Balancing only changes the tree structure, without freeing nodes, AFAIR.
> But that could be wrong. It's been a long time since I looked closer at
> that tree.
> 
> Wrt to weakness, I don't think there are weak references.

Oh, you're right! That's a relief.

> The big
> difference to the non-MPS case is that struct interval is subject to GC
> at all, they are malloc'd without igc. I didn't see another way to
> handle their plist otherwise. Making them malloc'd roots would have
> meant too many roots for my taste. I have currently ca. 20.000 live
> intervals for example, after GC.

Does there have to be a big difference at all, or is it possible the test is broken on vanilla Emacs, and it just so happens that GC happens at the right time and hides that bug?

The attached patch to Emacs master makes

make -C test lisp/emacs-lisp/ert-tests

run out of memory for me (again, on master, nothing special). I don't think it should: all it does is modify the test that runs before.

So is it possible this isn't all that MPS-specific?

Pip

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-ert-tests.patch --]
[-- Type: text/x-patch; name=0001-ert-tests.patch, Size: 559 bytes --]

diff --git a/test/lisp/emacs-lisp/ert-tests.el b/test/lisp/emacs-lisp/ert-tests.el
index 1aff73d66f6..4cb523d2ff1 100644
--- a/test/lisp/emacs-lisp/ert-tests.el
+++ b/test/lisp/emacs-lisp/ert-tests.el
@@ -569,7 +569,7 @@ ert-test-run-tests-batch
         (save-window-excursion
           (let ((case-fold-search nil)
                 (ert-batch-backtrace-right-margin nil)
-		(ert-batch-print-level 10)
+		(ert-batch-print-level 1)
 		(ert-batch-print-length 11))
             (ert-run-tests-batch
              `(member ,failing-test-1 ,failing-test-2)))))

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> Balancing only changes the tree structure, without freeing nodes, AFAIR.
>> But that could be wrong. It's been a long time since I looked closer at
>> that tree.
>
> We free nodes in sweep_intervals.

I think that is handled in igc.c by intervals becoming unreachable.

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> The big
>> difference to the non-MPS case is that struct interval is subject to GC
>> at all, they are malloc'd without igc. I didn't see another way to
>> handle their plist otherwise. Making them malloc'd roots would have
>> meant too many roots for my taste. I have currently ca. 20.000 live
>> intervals for example, after GC.
>
> Does there have to be a big difference at all, 

The only thing i can think of is what Helmut already suspected, namely
barriers. OTOH, it's not really noticeable in other cases, at least here
on macOS. In any case, I wouldn't expect anything remotely that big.
After all, it's not like a barrier is hit, the client runs a bit, and
the barrier goes up again.

> or is it possible the test is broken on vanilla Emacs, and it just so
> happens that GC happens at the right time and hides that bug?

ERT is a dark chapter for me. Digged through it once for the debugger
handling and giving the right backtraces in condition-case, and didn't
like it :-). I'd say everything is possible.

> The attached patch to Emacs master makes
>
> make -C test lisp/emacs-lisp/ert-tests
>
> run out of memory for me (again, on master, nothing special). I don't
> think it should: all it does is modify the test that runs before.
>
> So is it possible this isn't all that MPS-specific?

I have to admit I don't understand how that has the effect it has. Can
you see where it gets stuck?

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Pip Cet <pipcet@protonmail.com> writes:
>
>>> The big
>>> difference to the non-MPS case is that struct interval is subject to GC
>>> at all, they are malloc'd without igc. I didn't see another way to
>>> handle their plist otherwise. Making them malloc'd roots would have
>>> meant too many roots for my taste. I have currently ca. 20.000 live
>>> intervals for example, after GC.
>>
>> Does there have to be a big difference at all,
>
> The only thing i can think of is what Helmut already suspected, namely
> barriers. OTOH, it's not really noticeable in other cases, at least here
> on macOS. In any case, I wouldn't expect anything remotely that big.
> After all, it's not like a barrier is hit, the client runs a bit, and
> the barrier goes up again.
>
>> or is it possible the test is broken on vanilla Emacs, and it just so
>> happens that GC happens at the right time and hides that bug?
>
> ERT is a dark chapter for me. Digged through it once for the debugger
> handling and giving the right backtraces in condition-case, and didn't
> like it :-). I'd say everything is possible.
>
>> The attached patch to Emacs master makes
>>
>> make -C test lisp/emacs-lisp/ert-tests
>>
>> run out of memory for me (again, on master, nothing special). I don't
>> think it should: all it does is modify the test that runs before.
>>
>> So is it possible this isn't all that MPS-specific?
>
> I have to admit I don't understand how that has the effect it has. Can
> you see where it gets stuck?

Maybe it helps when I describe how I understand the test, so that others
can add something or correct me.

  (ert-deftest ert-test-run-tests-batch-expensive ()
    :tags (if (getenv "EMACS_EMBA_CI") '(:unstable))

Let's start with the purpose which is not apparent. AFAIU, this tests if
ert-batch-print-level and ert-batch-print-length work. Which is already
obvious from the test name, but I looked at the git history instead.

    (let* ((complex-list '((:1 (:2 (:3 (:4 (:5 (:6 "abc"))))))))
           (failing-test-1
            (make-ert-test :name 'failing-test-1
                           :body (lambda () (should (equal complex-list
           1))))))

Anove, we have a test that always fails. When it does it prints
something, and apparently what it prints depends on the ert-batch-xy
options.

      (let ((ert-debug-on-error nil)
            messages)
        (cl-letf* (((symbol-function 'message)
                    (lambda (format-string &rest args)
                      (push (apply #'format format-string args)
            messages))))

Setting the symbol function lets us catch what gets printed for the
failing test.

          (save-window-excursion
            (let ((case-fold-search nil)
                  (ert-batch-backtrace-right-margin nil)
                  (ert-batch-backtrace-line-length nil)
                  (ert-batch-print-level 6)
                  (ert-batch-print-length 11))
              (ert-run-tests-batch
               `(member ,failing-test-1)))))

Run test failing test.

        (let ((frame "ert-fail(((should (equal complex-list 1)) :form (equal ((:1 (:2 (:3 (:4 (:5 (:6 \"abc\"))))))) 1) :value nil :explanation (different-types ((:1 (:2 (:3 (:4 (:5 (:6 \"abc\"))))))) 1)))")
              found-frame)

This is what it should print with the given print-level and length.

          (cl-loop for msg in (reverse messages)
                   do
                   (unless found-frame

Someone didn't know while or until. :-)

                     (setq found-frame (cl-search frame msg :test
                   'equal))))

Check that what we expect was printed.

          (should found-frame)))))

🤷

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

>           (save-window-excursion
>             (let ((case-fold-search nil)
>                   (ert-batch-backtrace-right-margin nil)
>                   (ert-batch-backtrace-line-length nil)

This measn backtrace-line-limit is set to nil, meaning no limit. Default
is 5000.

  ert-batch-backtrace-line-length is a variable defined in ‘ert.el’.

  Its value is t

  Target length for lines in ERT batch backtraces.

  Even modest settings for ‘print-length’ and ‘print-level’ can
  produce extremely long lines in backtraces and lengthy delays in
  forming them.  This variable governs the target maximum line
  length by manipulating these two variables while printing stack
  traces.  Setting this variable to t will reuse the value of
  ‘backtrace-line-length’ while printing stack traces in ERT batch
  mode.  Any other value will be temporarily bound to
  ‘backtrace-line-length’ when producing stack traces in batch
  mode.


>                   (ert-batch-print-level 6)
>                   (ert-batch-print-length 11))
>               (ert-run-tests-batch
>                `(member ,failing-test-1)))))
>
> Run test failing test.
>
>         (let ((frame "ert-fail(((should (equal complex-list 1)) :form (equal ((:1 (:2 (:3 (:4 (:5 (:6 \"abc\"))))))) 1) :value nil :explanation (different-types ((:1 (:2 (:3 (:4 (:5 (:6 \"abc\"))))))) 1)))")
>               found-frame)
>
> This is what it should print with the given print-level and length.
>
>           (cl-loop for msg in (reverse messages)
>                    do
>                    (unless found-frame

We only have a few messages, but one gets really large

*** length 947
*** length 30
*** length 8184211
*** length 30
*** length 158
*** length 46
*** length 93
*** length 21
*** length 25
*** length 0

It's the backtrace string. In fact it gets larger with each preceding
test. Maybe it contains the value of a variable holding the results of
all preceding tests.

Constructing that large string gets slower and slower. Maybe an O(N^2)
somewhere or something like that.

I summary, I think this is an absoutely pathological case. I don't think
it's terribly interesting for igc.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>   emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 13:19:09 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> Balancing only changes the tree structure, without freeing nodes, AFAIR.
> >> But that could be wrong. It's been a long time since I looked closer at
> >> that tree.
> >
> > We free nodes in sweep_intervals.
> 
> I think that is handled in igc.c by intervals becoming unreachable.

They will not become unreachable unless we unchain them, as is done in
sweep_intervals.  Right?

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>   emacs-devel@gnu.org
>> Date: Sun, 07 Jul 2024 13:19:09 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> Balancing only changes the tree structure, without freeing nodes, AFAIR.
>> >> But that could be wrong. It's been a long time since I looked closer at
>> >> that tree.
>> >
>> > We free nodes in sweep_intervals.
>> 
>> I think that is handled in igc.c by intervals becoming unreachable.
>
> They will not become unreachable unless we unchain them, as is done in
> sweep_intervals.  Right?

It starts with the root of a tree becoming unreachable, say a string's
intervals become unreachable because the string is unreachable. By that,
the root's children are unreachable and so on.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>   emacs-devel@gnu.org
>> Date: Sun, 07 Jul 2024 13:19:09 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> Balancing only changes the tree structure, without freeing nodes, AFAIR.
>> >> But that could be wrong. It's been a long time since I looked closer at
>> >> that tree.
>> >
>> > We free nodes in sweep_intervals.
>> 
>> I think that is handled in igc.c by intervals becoming unreachable.
>
> They will not become unreachable unless we unchain them, as is done in
> sweep_intervals.  Right?

Forgot to add that the interval::next pointer doesn't exist with igc.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>>   emacs-devel@gnu.org
>>> Date: Sun, 07 Jul 2024 13:19:09 +0200
>>> 
>>> Eli Zaretskii <eliz@gnu.org> writes:
>>> 
>>> >> Balancing only changes the tree structure, without freeing nodes, AFAIR.
>>> >> But that could be wrong. It's been a long time since I looked closer at
>>> >> that tree.
>>> >
>>> > We free nodes in sweep_intervals.
>>> 
>>> I think that is handled in igc.c by intervals becoming unreachable.
>>
>> They will not become unreachable unless we unchain them, as is done in
>> sweep_intervals.  Right?
>
> Forgot to add that the interval::next pointer doesn't exist with igc.

And scratch that, I was thinking of markers. Need a break :-)

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 11:48, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Gerd Möllmann gerd.moellmann@gmail.com writes:
> > Pip Cet pipcet@protonmail.com writes:
> > 
> > > > The big
> > > > difference to the non-MPS case is that struct interval is subject to GC
> > > > at all, they are malloc'd without igc. I didn't see another way to
> > > > handle their plist otherwise. Making them malloc'd roots would have
> > > > meant too many roots for my taste. I have currently ca. 20.000 live
> > > > intervals for example, after GC.
> > > 
> > > Does there have to be a big difference at all,
> > 
> > The only thing i can think of is what Helmut already suspected, namely
> > barriers. OTOH, it's not really noticeable in other cases, at least here
> > on macOS. In any case, I wouldn't expect anything remotely that big.
> > After all, it's not like a barrier is hit, the client runs a bit, and
> > the barrier goes up again.
> > 
> > > or is it possible the test is broken on vanilla Emacs, and it just so
> > > happens that GC happens at the right time and hides that bug?
> > 
> > ERT is a dark chapter for me. Digged through it once for the debugger
> > handling and giving the right backtraces in condition-case, and didn't
> > like it :-). I'd say everything is possible.
> > 
> > > The attached patch to Emacs master makes
> > > 
> > > make -C test lisp/emacs-lisp/ert-tests
> > > 
> > > run out of memory for me (again, on master, nothing special). I don't
> > > think it should: all it does is modify the test that runs before.
> > > 
> > > So is it possible this isn't all that MPS-specific?
> > 
> > I have to admit I don't understand how that has the effect it has. Can
> > you see where it gets stuck?

Deep in the cl-print machinery, generating a buffer which reaches many megabytes.

I don't think it's actually inflooping, just running out of memory.

If I turn cl-print--vector-contents into a nop, it finishes quite quickly, and succeeds.

Oh, I think I found something! "messages" is a let-bound variable containing all messages. The backtrace goes there. But the backtrace also prints the values of let-bound variables in closures, so it'll print all messages recursively, giving us O(N^2) behavior at least...

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> Deep in the cl-print machinery, generating a buffer which reaches many megabytes.
>
> I don't think it's actually inflooping, just running out of memory.
>
> If I turn cl-print--vector-contents into a nop, it finishes quite quickly, and succeeds.
>
> Oh, I think I found something! "messages" is a let-bound variable
> containing all messages. The backtrace goes there. But the backtrace
> also prints the values of let-bound variables in closures, so it'll
> print all messages recursively, giving us O(N^2) behavior at least...

Ohgodogodgod, that matches what I see. Thanks!

I don't think it's really important to improve that with igc.I wouldn't
be able to anyway :-).

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>   emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 16:15:54 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> >> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
> >>   emacs-devel@gnu.org
> >> Date: Sun, 07 Jul 2024 13:19:09 +0200
> >> 
> >> Eli Zaretskii <eliz@gnu.org> writes:
> >> 
> >> >> Balancing only changes the tree structure, without freeing nodes, AFAIR.
> >> >> But that could be wrong. It's been a long time since I looked closer at
> >> >> that tree.
> >> >
> >> > We free nodes in sweep_intervals.
> >> 
> >> I think that is handled in igc.c by intervals becoming unreachable.
> >
> > They will not become unreachable unless we unchain them, as is done in
> > sweep_intervals.  Right?
> 
> It starts with the root of a tree becoming unreachable, say a string's
> intervals become unreachable because the string is unreachable. By that,
> the root's children are unreachable and so on.

I thought about the case where the string or the buffer are still
alive, but some of their intervals are no longer used because of
changes in the text properties.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> It starts with the root of a tree becoming unreachable, say a string's
>> intervals become unreachable because the string is unreachable. By that,
>> the root's children are unreachable and so on.
>
> I thought about the case where the string or the buffer are still
> alive, but some of their intervals are no longer used because of
> changes in the text properties.

Isn't that similar? In that case, no root and not other node in the tree
has a reference to the interval in question, so it's unreachable.

Re: MPS: weak hash tables

[Helmut Eller]

On Sun, Jul 07 2024, Pip Cet wrote:

> Oh, I think I found something! "messages" is a let-bound variable
> containing all messages. The backtrace goes there. But the backtrace
> also prints the values of let-bound variables in closures, so it'll
> print all messages recursively, giving us O(N^2) behavior at least...

Hm, messages is let-bound in ert-test-run-tests-batch-expensive.  How
can it have any effect or be effected by other tests?

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>   emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 16:52:15 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> It starts with the root of a tree becoming unreachable, say a string's
> >> intervals become unreachable because the string is unreachable. By that,
> >> the root's children are unreachable and so on.
> >
> > I thought about the case where the string or the buffer are still
> > alive, but some of their intervals are no longer used because of
> > changes in the text properties.
> 
> Isn't that similar? In that case, no root and not other node in the tree
> has a reference to the interval in question, so it's unreachable.

It's a C struct, not a Lisp object, so I'm not sure I understand what
you are saying here.  It sounds like we are having a misunderstanding.

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>   emacs-devel@gnu.org
>> Date: Sun, 07 Jul 2024 16:52:15 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> It starts with the root of a tree becoming unreachable, say a string's
>> >> intervals become unreachable because the string is unreachable. By that,
>> >> the root's children are unreachable and so on.
>> >
>> > I thought about the case where the string or the buffer are still
>> > alive, but some of their intervals are no longer used because of
>> > changes in the text properties.
>> 
>> Isn't that similar? In that case, no root and not other node in the tree
>> has a reference to the interval in question, so it's unreachable.
>
> It's a C struct, not a Lisp object, so I'm not sure I understand what
> you are saying here.  It sounds like we are having a misunderstanding.

Looks like we do. References in igc can be pointers and Lisp_Objects.
Maybe that's the misunderstanding?

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sun, Jul 07 2024, Pip Cet wrote:
>
>> Oh, I think I found something! "messages" is a let-bound variable
>> containing all messages. The backtrace goes there. But the backtrace
>> also prints the values of let-bound variables in closures, so it'll
>> print all messages recursively, giving us O(N^2) behavior at least...
>
> Hm, messages is let-bound in ert-test-run-tests-batch-expensive.  How
> can it have any effect or be effected by other tests?

I thought it maybe comes from here

  (defun ert-run-tests (selector listener &optional interactively)
    "Run the tests specified by SELECTOR, sending progress updates to LISTENER."
    (let* ((tests (ert-select-tests selector t))
           (stats (ert--make-stats tests selector)))

Haven't checked that though, the lines were too long for me.

Re: MPS: weak hash tables

[Helmut Eller]

On Sun, Jul 07 2024, Gerd Möllmann wrote:

>>> Oh, I think I found something! "messages" is a let-bound variable
>>> containing all messages. The backtrace goes there. But the backtrace
>>> also prints the values of let-bound variables in closures, so it'll
>>> print all messages recursively, giving us O(N^2) behavior at least...
>>
>> Hm, messages is let-bound in ert-test-run-tests-batch-expensive.  How
>> can it have any effect or be effected by other tests?
>
> I thought it maybe comes from here
>
>   (defun ert-run-tests (selector listener &optional interactively)
>     "Run the tests specified by SELECTOR, sending progress updates to LISTENER."
>     (let* ((tests (ert-select-tests selector t))
>            (stats (ert--make-stats tests selector)))
>
> Haven't checked that though, the lines were too long for me.

You mean "stats", which includes results and possibly big objects of the
previous tests, is included in the backtrace.  And
ert-test-run-tests-batch-expensive prints it with altered printer
settings.  Could be.

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sun, Jul 07 2024, Gerd Möllmann wrote:
>
>>>> Oh, I think I found something! "messages" is a let-bound variable
>>>> containing all messages. The backtrace goes there. But the backtrace
>>>> also prints the values of let-bound variables in closures, so it'll
>>>> print all messages recursively, giving us O(N^2) behavior at least...
>>>
>>> Hm, messages is let-bound in ert-test-run-tests-batch-expensive.  How
>>> can it have any effect or be effected by other tests?
>>
>> I thought it maybe comes from here
>>
>>   (defun ert-run-tests (selector listener &optional interactively)
>>     "Run the tests specified by SELECTOR, sending progress updates to LISTENER."
>>     (let* ((tests (ert-select-tests selector t))
>>            (stats (ert--make-stats tests selector)))
>>
>> Haven't checked that though, the lines were too long for me.
>
> You mean "stats", which includes results and possibly big objects of the
> previous tests, is included in the backtrace.  And
> ert-test-run-tests-batch-expensive prints it with altered printer
> settings.  Could be.

Yes, something like that. I couldn't find something global that could be
the culprit, so it should be something above the frames of the current
test. How that exactly works with stats being a lexical variable I don't
know though.

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 15:52, Helmut Eller <eller.helmut@gmail.com> wrote:
> On Sun, Jul 07 2024, Gerd Möllmann wrote:
> 
> > > > Oh, I think I found something! "messages" is a let-bound variable
> > > > containing all messages. The backtrace goes there. But the backtrace
> > > > also prints the values of let-bound variables in closures, so it'll
> > > > print all messages recursively, giving us O(N^2) behavior at least...
> > > 
> > > Hm, messages is let-bound in ert-test-run-tests-batch-expensive. How
> > > can it have any effect or be effected by other tests?
> > 
> > I thought it maybe comes from here
> > 
> > (defun ert-run-tests (selector listener &optional interactively)
> > "Run the tests specified by SELECTOR, sending progress updates to LISTENER."
> > (let* ((tests (ert-select-tests selector t))
> > (stats (ert--make-stats tests selector)))
> > 
> > Haven't checked that though, the lines were too long for me.
> 
> 
> You mean "stats", which includes results and possibly big objects of the
> previous tests, is included in the backtrace. And
> ert-test-run-tests-batch-expensive prints it with altered printer
> settings. Could be.

So

(cl-defmethod cl-print-object ((object ert--stats) stream))

should help? It appears to...

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>  emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 17:36:18 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> >> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
> >>   emacs-devel@gnu.org
> >> Date: Sun, 07 Jul 2024 16:52:15 +0200
> >> 
> >> Eli Zaretskii <eliz@gnu.org> writes:
> >> 
> >> >> It starts with the root of a tree becoming unreachable, say a string's
> >> >> intervals become unreachable because the string is unreachable. By that,
> >> >> the root's children are unreachable and so on.
> >> >
> >> > I thought about the case where the string or the buffer are still
> >> > alive, but some of their intervals are no longer used because of
> >> > changes in the text properties.
> >> 
> >> Isn't that similar? In that case, no root and not other node in the tree
> >> has a reference to the interval in question, so it's unreachable.
> >
> > It's a C struct, not a Lisp object, so I'm not sure I understand what
> > you are saying here.  It sounds like we are having a misunderstanding.
> 
> Looks like we do. References in igc can be pointers and Lisp_Objects.
> Maybe that's the misunderstanding?

But does igc know that an interval is no longer needed?  How does it
know that when sweep_intervals in the old GC needed to do that
explicitly in C?

Re: MPS: weak hash tables

[Helmut Eller]

On Sun, Jul 07 2024, Pip Cet wrote:

>> You mean "stats", which includes results and possibly big objects of the
>> previous tests, is included in the backtrace. And
>> ert-test-run-tests-batch-expensive prints it with altered printer
>> settings. Could be.
>
> So
>
> (cl-defmethod cl-print-object ((object ert--stats) stream))
>
> should help? It appears to...

Good idea!  This makes ert-test-run-tests-batch-expensive definitely
less expensive.

Can we conclude something about igc from this?  Maybe that it works as
it should.  But also that it's not particularly good if the heap is
almost full with live objects.

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sun, Jul 07 2024, Pip Cet wrote:
>
>>> You mean "stats", which includes results and possibly big objects of the
>>> previous tests, is included in the backtrace. And
>>> ert-test-run-tests-batch-expensive prints it with altered printer
>>> settings. Could be.
>>
>> So
>>
>> (cl-defmethod cl-print-object ((object ert--stats) stream))
>>
>> should help? It appears to...
>
> Good idea!  This makes ert-test-run-tests-batch-expensive definitely
> less expensive.

👍 Looking forward to commits I can transfer back home :-).

> Can we conclude something about igc from this?  Maybe that it works as
> it should.  But also that it's not particularly good if the heap is
> almost full with live objects.

I believe it works as expected, yes. When one allocs in such a pattern,
maybe one should use park the arena, or use ramp allocation, or
something. 

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

> But does igc know that an interval is no longer needed?  How does it
> know that when sweep_intervals in the old GC needed to do that
> explicitly in C?

It's kind of mark-sweep vs. copying collector algorithms.

The mark phase of mark-sweep marks all objects reachable from roots,
then the sweep phase frees what's not marked.

A copying collector copies every object reachable from roots. At the
end, what has not been copied is implicitly unreachable.

MPS is a copying collection, with some additional complications, like
ambiguous references (-> mostly-copying), and incrementality (->
barriers), but the principle is still the same.

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>   emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 19:08:45 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > But does igc know that an interval is no longer needed?  How does it
> > know that when sweep_intervals in the old GC needed to do that
> > explicitly in C?
> 
> It's kind of mark-sweep vs. copying collector algorithms.
> 
> The mark phase of mark-sweep marks all objects reachable from roots,
> then the sweep phase frees what's not marked.
> 
> A copying collector copies every object reachable from roots. At the
> end, what has not been copied is implicitly unreachable.
> 
> MPS is a copying collection, with some additional complications, like
> ambiguous references (-> mostly-copying), and incrementality (->
> barriers), but the principle is still the same.

I understand all that, but unchaining an interval involves the need to
modify the pointers of its adjacent nodes, and how can MPS do that
without understanding our data structures?

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>   emacs-devel@gnu.org
>> Date: Sun, 07 Jul 2024 19:08:45 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > But does igc know that an interval is no longer needed?  How does it
>> > know that when sweep_intervals in the old GC needed to do that
>> > explicitly in C?
>> 
>> It's kind of mark-sweep vs. copying collector algorithms.
>> 
>> The mark phase of mark-sweep marks all objects reachable from roots,
>> then the sweep phase frees what's not marked.
>> 
>> A copying collector copies every object reachable from roots. At the
>> end, what has not been copied is implicitly unreachable.
>> 
>> MPS is a copying collection, with some additional complications, like
>> ambiguous references (-> mostly-copying), and incrementality (->
>> barriers), but the principle is still the same.
>
> I understand all that, but unchaining an interval involves the need to
> modify the pointers of its adjacent nodes, and how can MPS do that
> without understanding our data structures?

Can you please show me what code you mean? 

Re: MPS: weak hash tables

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>   emacs-devel@gnu.org
> Date: Sun, 07 Jul 2024 20:15:34 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > I understand all that, but unchaining an interval involves the need to
> > modify the pointers of its adjacent nodes, and how can MPS do that
> > without understanding our data structures?
> 
> Can you please show me what code you mean? 

This one:

  static void
  sweep_intervals (void)
  {
    struct interval_block **iprev = &interval_block;
    int lim = interval_block_index;
    object_ct num_free = 0, num_used = 0;

    interval_free_list = 0;

    for (struct interval_block *iblk; (iblk = *iprev); )
      {
	int this_free = 0;
	ASAN_UNPOISON_INTERVAL_BLOCK (iblk);
	for (int i = 0; i < lim; i++)
	  {
	    if (!iblk->intervals[i].gcmarkbit)
	      {
		set_interval_parent (&iblk->intervals[i], interval_free_list);
		interval_free_list = &iblk->intervals[i];
		ASAN_POISON_INTERVAL (&iblk->intervals[i]);
		this_free++;
	      }
	    else
	      {
		num_used++;
		iblk->intervals[i].gcmarkbit = 0;
	      }
	  }
	lim = INTERVAL_BLOCK_SIZE;
	/* If this block contains only free intervals and we have already
	   seen more than two blocks worth of free intervals then
	   deallocate this block.  */
	if (this_free == INTERVAL_BLOCK_SIZE && num_free > INTERVAL_BLOCK_SIZE)
	  {
	    *iprev = iblk->next;
	    /* Unhook from the free list.  */
	    ASAN_UNPOISON_INTERVAL (&iblk->intervals[0]);
	    interval_free_list = INTERVAL_PARENT (&iblk->intervals[0]);
	    lisp_free (iblk);
	  }
	else
	  {
	    num_free += this_free;
	    iprev = &iblk->next;
	  }
      }

Re: MPS: weak hash tables

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  eller.helmut@gmail.com,  yantar92@posteo.net,
>>   emacs-devel@gnu.org
>> Date: Sun, 07 Jul 2024 20:15:34 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > I understand all that, but unchaining an interval involves the need to
>> > modify the pointers of its adjacent nodes, and how can MPS do that
>> > without understanding our data structures?
>> 
>> Can you please show me what code you mean? 
>
> This one:
>
>   static void
>   sweep_intervals (void)
>   {
>     struct interval_block **iprev = &interval_block;
>     int lim = interval_block_index;
>     object_ct num_free = 0, num_used = 0;
>
>     interval_free_list = 0;
>
>     for (struct interval_block *iblk; (iblk = *iprev); )
>       {
> 	int this_free = 0;
> 	ASAN_UNPOISON_INTERVAL_BLOCK (iblk);
> 	for (int i = 0; i < lim; i++)
> 	  {
> 	    if (!iblk->intervals[i].gcmarkbit)
> 	      {
> 		set_interval_parent (&iblk->intervals[i], interval_free_list);
> 		interval_free_list = &iblk->intervals[i];
> 		ASAN_POISON_INTERVAL (&iblk->intervals[i]);
> 		this_free++;
> 	      }
> 	    else
> 	      {
> 		num_used++;
> 		iblk->intervals[i].gcmarkbit = 0;
> 	      }
> 	  }
> 	lim = INTERVAL_BLOCK_SIZE;
> 	/* If this block contains only free intervals and we have already
> 	   seen more than two blocks worth of free intervals then
> 	   deallocate this block.  */
> 	if (this_free == INTERVAL_BLOCK_SIZE && num_free > INTERVAL_BLOCK_SIZE)
> 	  {
> 	    *iprev = iblk->next;
> 	    /* Unhook from the free list.  */
> 	    ASAN_UNPOISON_INTERVAL (&iblk->intervals[0]);
> 	    interval_free_list = INTERVAL_PARENT (&iblk->intervals[0]);
> 	    lisp_free (iblk);
> 	  }
> 	else
> 	  {
> 	    num_free += this_free;
> 	    iprev = &iblk->next;
> 	  }
>       }

Ah!

There are no interval_blocks, no interval_free_list nothing of that in
MPS.

Re: MPS: weak hash tables

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Helmut Eller <eller.helmut@gmail.com> writes:
>
>> On Sun, Jul 07 2024, Pip Cet wrote:
>>
>>>> You mean "stats", which includes results and possibly big objects of the
>>>> previous tests, is included in the backtrace. And
>>>> ert-test-run-tests-batch-expensive prints it with altered printer
>>>> settings. Could be.
>>>
>>> So
>>>
>>> (cl-defmethod cl-print-object ((object ert--stats) stream))
>>>
>>> should help? It appears to...
>>
>> Good idea!  This makes ert-test-run-tests-batch-expensive definitely
>> less expensive.
>
> 👍 Looking forward to commits I can transfer back home :-).
>
>> Can we conclude something about igc from this?  Maybe that it works as
>> it should.  But also that it's not particularly good if the heap is
>> almost full with live objects.
>
> I believe it works as expected, yes. When one allocs in such a pattern,
> maybe one should use park the arena, or use ramp allocation, or
> something. 

Helmut, I seem to remember that you had 3 points on your list that
needed investigation, pi, ert-test, and something else I can't find now
and don't remember.

Could you please remind me, or am I misremembering?

Re: MPS: weak hash tables

[Helmut Eller]

On Sun, Jul 07 2024, Gerd Möllmann wrote:

> Helmut, I seem to remember that you had 3 points on your list that
> needed investigation, pi, ert-test, and something else I can't find now
> and don't remember.
>
> Could you please remind me, or am I misremembering?

The third was some form of heap size limit.  Maybe
mps_arena_commit_limit_set is what I want.  I'd have to try it.

Re: MPS: weak hash tables

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sun, Jul 07 2024, Gerd Möllmann wrote:
>
>> Helmut, I seem to remember that you had 3 points on your list that
>> needed investigation, pi, ert-test, and something else I can't find now
>> and don't remember.
>>
>> Could you please remind me, or am I misremembering?
>
> The third was some form of heap size limit.  Maybe
> mps_arena_commit_limit_set is what I want.  I'd have to try it.

Ah right, thanks! The strange behaviour when set via MPS_KEY_... etc.

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 19:00, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Helmut Eller eller.helmut@gmail.com writes:
> 
> > On Sun, Jul 07 2024, Gerd Möllmann wrote:
> > 
> > > Helmut, I seem to remember that you had 3 points on your list that
> > > needed investigation, pi, ert-test, and something else I can't find now
> > > and don't remember.
> > > 
> > > Could you please remind me, or am I misremembering?
> > 
> > The third was some form of heap size limit. Maybe
> > mps_arena_commit_limit_set is what I want. I'd have to try it.
> 
> 
> Ah right, thanks! The strange behaviour when set via MPS_KEY_... etc.

I looked into that briefly, and believe it happens only when we hit the memory limit. Does that match what you're seeing?

The weird bug happens when I set the limit with mps_arena_commit_limit_set, too.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> On Sunday, July 7th, 2024 at 19:00, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
>> Helmut Eller eller.helmut@gmail.com writes:
>> 
>> > On Sun, Jul 07 2024, Gerd Möllmann wrote:
>> > 
>> > > Helmut, I seem to remember that you had 3 points on your list that
>> > > needed investigation, pi, ert-test, and something else I can't find now
>> > > and don't remember.
>> > > 
>> > > Could you please remind me, or am I misremembering?
>> > 
>> > The third was some form of heap size limit. Maybe
>> > mps_arena_commit_limit_set is what I want. I'd have to try it.
>> 
>> 
>> Ah right, thanks! The strange behaviour when set via MPS_KEY_... etc.
>
> I looked into that briefly, and believe it happens only when we hit
> the memory limit. Does that match what you're seeing?

Not sure. IIRC, I used 1 << 30, and got the assertion when dumping. I
don't know if Emacs uses 1G for dumping.

Re: MPS: weak hash tables

[Pip Cet]

On Sunday, July 7th, 2024 at 16:26, Helmut Eller <eller.helmut@gmail.com> wrote:
> On Sun, Jul 07 2024, Pip Cet wrote:
> 
> > > You mean "stats", which includes results and possibly big objects of the
> > > previous tests, is included in the backtrace. And
> > > ert-test-run-tests-batch-expensive prints it with altered printer
> > > settings. Could be.
> > 
> > So
> > 
> > (cl-defmethod cl-print-object ((object ert--stats) stream))
> > 
> > should help? It appears to...
> 
> Good idea! This makes ert-test-run-tests-batch-expensive definitely
> less expensive.

I've opened Bug#71988 to document the somewhat subtle change to the test that is required. Let's see what the others say.

> Can we conclude something about igc from this? Maybe that it works as
> it should. But also that it's not particularly good if the heap is
> almost full with live objects.

My conclusions for igc are:
* it appears to work in non-pathological cases
* there might be problems balancing string intervals, which we're going to have to revisit at some point
* building large strings by concatenating repeatedly might have worse performance than it does on Emacs master, particularly if those strings have many text properties

In summary, I think we're fine for now, but I think backtrace--filter-visible may require some attention:

(defun backtrace--filter-visible (beg end &optional _delete)
  "Return the visible text between BEG and END."
  (let ((result ""))
    (while (< beg end)
      (let ((next (next-single-char-property-change beg 'invisible)))
        (unless (get-char-property beg 'invisible)
          (setq result (concat result (buffer-substring beg (min end next)))))
        (setq beg next)))
    result))

I think it would be better to create a list of strings and concatenate them with a single call instead.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

> I think it would be better to create a list of strings and concatenate
> them with a single call instead.

We could also expose ramp allocation to Lisp for these kinds of things,
so that one doesn't drive the collector nuts by allocating objects in
this manner.

Re: MPS: weak hash tables

[Pip Cet]

On Monday, July 8th, 2024 at 05:17, Gerd Möllmann <gerd.moellmann@gmail.com> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > I think it would be better to create a list of strings and concatenate
> > them with a single call instead.
> 
> 
> We could also expose ramp allocation to Lisp for these kinds of things,
> so that one doesn't drive the collector nuts by allocating objects in
> this manner.

We can and should expose that, but probably not use it in this case. It might be worth it for large vectors, but for strings it probably won't help:

Ramp allocation is only supported by AMC (Automatic Mostly-Copying).

String data is AMCZ.

I've decided to go ahead with the ugly non-bitfield patch, mostly for one reason: I'd really like to record previous and current addresses of moved objects somewhere, and the exthdr thing seems perfect for that--it lives in xmalloc'd memory so we can modify it from the scan function. Sorry it took such a lot of sleeping over it :-)

So, last chance to object there.

Pip

Re: MPS: weak hash tables

[Gerd Möllmann]

Pip Cet <pipcet@protonmail.com> writes:

>> We could also expose ramp allocation to Lisp for these kinds of things,
>> so that one doesn't drive the collector nuts by allocating objects in
>> this manner.
>
> We can and should expose that, but probably not use it in this case.
> It might be worth it for large vectors, but for strings it probably
> won't help:
>
> Ramp allocation is only supported by AMC (Automatic Mostly-Copying).

Oh, didn't remember that. Then ramp allocation is pretty worthless.

We could park the arena temporarily though. I used that already for
dumping which similarly creates tons of objects, and it had a very
noticeable effect.

> I've decided to go ahead with the ugly non-bitfield patch, mostly for
> one reason: I'd really like to record previous and current addresses
> of moved objects somewhere, and the exthdr thing seems perfect for
> that--it lives in xmalloc'd memory so we can modify it from the scan
> function. Sorry it took such a lot of sleeping over it :-)
>
> So, last chance to object there.

Not me :-).

MPS: commit limit

[Gerd Möllmann]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Helmut Eller <eller.helmut@gmail.com> writes:
>
>> On Sun, Jul 07 2024, Gerd Möllmann wrote:
>>
>>> Helmut, I seem to remember that you had 3 points on your list that
>>> needed investigation, pi, ert-test, and something else I can't find now
>>> and don't remember.
>>>
>>> Could you please remind me, or am I misremembering?
>>
>> The third was some form of heap size limit.  Maybe
>> mps_arena_commit_limit_set is what I want.  I'd have to try it.
>
> Ah right, thanks! The strange behaviour when set via MPS_KEY_... etc.

Sometimes it works just fine, sometimes not. For example, with 1 << 29,
I get a nice memory full when dumping, always. With 1 << 30, only the
expensice ert-test triggers something, namely the assertion in MPS.

Hm.

Re: MPS: weak hash tables

[Andrea Corallo]

Helmut Eller <eller.helmut@gmail.com> writes:

> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>
>> Helmut, could you please see if that helps with the pi code?
>
> Yes, it helps:
>
>   ./src/emacs -Q -batch -l \
>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
>   '(elisp-benchmarks-run "pidigits" nil 1)'
>
> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
> version.  And it uses something like 2.8 GB compared to 350 MB of the
> non-MPS version (estimated by looking at the RES column in top).

Such a difference in memory footprint is because MPS can't GC at the
speed the main thread is allocating or for some other reason?

  Andrea

Re: MPS: weak hash tables

[Gerd Möllmann]

Andrea Corallo <acorallo@gnu.org> writes:

> Helmut Eller <eller.helmut@gmail.com> writes:
>
>> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>>
>>> Helmut, could you please see if that helps with the pi code?
>>
>> Yes, it helps:
>>
>>   ./src/emacs -Q -batch -l \
>>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
>>   '(elisp-benchmarks-run "pidigits" nil 1)'
>>
>> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
>> version.  And it uses something like 2.8 GB compared to 350 MB of the
>> non-MPS version (estimated by looking at the RES column in top).
>
> Such a difference in memory footprint is because MPS can't GC at the
> speed the main thread is allocating or for some other reason?

Yes, that's it basically. The client is allocating at a high rate,
and not much is dying until the end of that phase. Both together mean
that MPS is scanning like wild to make some room, without having a
chance to find something it can discard.

Re: MPS: weak hash tables

[Andrea Corallo]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Andrea Corallo <acorallo@gnu.org> writes:
>
>> Helmut Eller <eller.helmut@gmail.com> writes:
>>
>>> On Sat, Jul 06 2024, Gerd Möllmann wrote:
>>>
>>>> Helmut, could you please see if that helps with the pi code?
>>>
>>> Yes, it helps:
>>>
>>>   ./src/emacs -Q -batch -l \
>>>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
>>>   '(elisp-benchmarks-run "pidigits" nil 1)'
>>>
>>> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
>>> version.  And it uses something like 2.8 GB compared to 350 MB of the
>>> non-MPS version (estimated by looking at the RES column in top).
>>
>> Such a difference in memory footprint is because MPS can't GC at the
>> speed the main thread is allocating or for some other reason?
>
> Yes, that's it basically. The client is allocating at a high rate,
> and not much is dying until the end of that phase.

What do you mean with "not much is dying"?  IIUC the original GC is
collecting most of them, so they are not live anymore.

> Both together mean
> that MPS is scanning like wild to make some room, without having a
> chance to find something it can discard.

Sounds to me like a bandwidth limitaiton in the collector (we see in
this patological case).

Re: MPS: weak hash tables

[Gerd Möllmann]

Andrea Corallo <acorallo@gnu.org> writes:

> What do you mean with "not much is dying"?  

Not much is becoming unreachable.

> IIUC the original GC is collecting most of them, so they are not live
> anymore.

Pip has run the test on master, and seen large process sizes there too.
SO I guess the old GC has basically the same problem.

Re: MPS: out-of-memory

[Eli Zaretskii]

[I've changed the Subject, since this ceased to be about weak hash
tables long ago.]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: Helmut Eller <eller.helmut@gmail.com>,  Eli Zaretskii <eliz@gnu.org>,
>   pipcet@protonmail.com,  emacs-devel@gnu.org
> Date: Mon, 08 Jul 2024 11:24:25 +0200
> 
> Andrea Corallo <acorallo@gnu.org> writes:
> 
> >>   ./src/emacs -Q -batch -l \
> >>   ~/.emacs.d/elpa/elisp-benchmarks-1.14/elisp-benchmarks.el --eval \
> >>   '(elisp-benchmarks-run "pidigits" nil 1)'
> >>
> >> finishes and requires 41.82 seconds compared to the 12.26 of the non-MPS
> >> version.  And it uses something like 2.8 GB compared to 350 MB of the
> >> non-MPS version (estimated by looking at the RES column in top).
> >
> > Such a difference in memory footprint is because MPS can't GC at the
> > speed the main thread is allocating or for some other reason?
> 
> Yes, that's it basically. The client is allocating at a high rate,
> and not much is dying until the end of that phase. Both together mean
> that MPS is scanning like wild to make some room, without having a
> chance to find something it can discard.

Btw, the current GC in Emacs has a feature for when Emacs runs out of
memory: it sets some small amount of memory aside, and uses it when
"memory-full" condition happens, because some memory is needed to show
the memory-full error message, and then shut down in an orderly
fashion:

  void
  memory_full (size_t nbytes)
  {
    if (!initialized)
      fatal ("memory exhausted");

    /* Do not go into hysterics merely because a large request failed.  */
    bool enough_free_memory = false;
    if (SPARE_MEMORY < nbytes)
      {
	void *p;

	MALLOC_BLOCK_INPUT;
	p = malloc (SPARE_MEMORY);
	if (p)
	  {
	    free (p);
	    enough_free_memory = true;
	  }
	MALLOC_UNBLOCK_INPUT;
      }

    if (! enough_free_memory)
      {
	Vmemory_full = Qt;
	consing_until_gc = min (consing_until_gc, memory_full_cons_threshold);

	/* The first time we get here, free the spare memory.  */
	for (int i = 0; i < ARRAYELTS (spare_memory); i++)
	  if (spare_memory[i])
	    {
	      if (i == 0)
		free (spare_memory[i]);
	      else if (i >= 1 && i <= 4)
		lisp_align_free (spare_memory[i]);
	      else
		lisp_free (spare_memory[i]);
	      spare_memory[i] = 0;
	    }
      }

    /* This used to call error, but if we've run out of memory, we could
       get infinite recursion trying to build the string.  */
    xsignal (Qnil, Vmemory_signal_data);
  }

See also refill_memory_reserve.

Do we perhaps need something like that with MPS?