GNU bug report logs - #69706
30.0.50; sort.c, unnecessary GC marking

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 69706 in the body.
You can then email your comments to 69706 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 09:45:01 +0100

sort.c uses record_unwind_protect_mark to let GC mark some objects in
its merge_state structure, while GC marks the specpdl stack.

This is

- unnecessary because all the objects that are currrently extra
  protected by merge_markmem, are already seen by the GC, because these
  are the objects being sorted, which are protected in the usual way
  (marking the control stack, ...)

- costs GC time

- complicates the code

I therefore suggest removing this, including the removal of
record_unwind_protect_mark and the mark function pointer in union
specbinding (sort.c is the only user).

Message #8 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 Mattias Engdegård <mattiase <at> acm.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 12:38:17 +0200

> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
> Date: Sun, 10 Mar 2024 09:45:01 +0100
> 
> sort.c uses record_unwind_protect_mark to let GC mark some objects in
> its merge_state structure, while GC marks the specpdl stack.
> 
> This is
> 
> - unnecessary because all the objects that are currrently extra
>   protected by merge_markmem, are already seen by the GC, because these
>   are the objects being sorted, which are protected in the usual way
>   (marking the control stack, ...)
> 
> - costs GC time
> 
> - complicates the code
> 
> I therefore suggest removing this, including the removal of
> record_unwind_protect_mark and the mark function pointer in union
> specbinding (sort.c is the only user).

Can you show the patch, please?

Adding Stefan and Mattias to the discussion, in case they have
comments or suggestions.

Thanks.

Message #11 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Mattias Engdegård <mattiase <at> acm.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 11:51:41 +0100

Eli Zaretskii <eliz <at> gnu.org> writes:

> Can you show the patch, please?

I haven't made one yet. Should I?

Message #14 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: mattiase <at> acm.org, monnier <at> iro.umontreal.ca, 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 13:12:05 +0200

> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
> Cc: Mattias Engdegård <mattiase <at> acm.org>,  Stefan Monnier
>  <monnier <at> iro.umontreal.ca>,  69706 <at> debbugs.gnu.org
> Date: Sun, 10 Mar 2024 11:51:41 +0100
> 
> Eli Zaretskii <eliz <at> gnu.org> writes:
> 
> > Can you show the patch, please?
> 
> I haven't made one yet. Should I?

I think so, yes.

Message #17 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Gerd Möllmann <gerd.moellmann <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 12:16:42 +0100

>> sort.c uses record_unwind_protect_mark to let GC mark some objects in
>> its merge_state structure, while GC marks the specpdl stack.
>> 
>> This is
>> 
>> - unnecessary because all the objects that are currrently extra
>>  protected by merge_markmem, are already seen by the GC, because these
>>  are the objects being sorted, which are protected in the usual way
>>  (marking the control stack, ...)

Thank you Gerd, but I don't think we can guarantee that those objects are present anywhere else -- the original vector is being mutated by the algorithm, after all.

In addition, I have Grand Plans (well, some kind of plans) for an improvement to the sorting code that will likely require record_unwind_protect_mark or an equivalent facility. A new bug will be opened about that.

Message #20 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 12:29:11 +0100

Mattias Engdegård <mattias.engdegard <at> gmail.com> writes:

>>> sort.c uses record_unwind_protect_mark to let GC mark some objects in
>>> its merge_state structure, while GC marks the specpdl stack.
>>> 
>>> This is
>>> 
>>> - unnecessary because all the objects that are currrently extra
>>>  protected by merge_markmem, are already seen by the GC, because these
>>>  are the objects being sorted, which are protected in the usual way
>>>  (marking the control stack, ...)
>
> Thank you Gerd, but I don't think we can guarantee that those objects
> are present anywhere else -- the original vector is being mutated by
> the algorithm, after all.

You nean sort.c is removing objects temporarily from the vector, so that
they are not reachable from any other root, especially from the control
stack? Could be, the code is a bit hard to follow.

OTOH, I think it would not be too hard to make such objects reachanble
from control stack...

> In addition, I have Grand Plans (well, some kind of plans) for an
> improvement to the sorting code that will likely require
> record_unwind_protect_mark or an equivalent facility. A new bug will
> be opened about that.

Please make it easy for a concurrent, mostly-copying GC, use the stack
;-).

Message #23 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 14:38:38 +0100

10 mars 2024 kl. 12.29 skrev Gerd Möllmann <gerd.moellmann <at> gmail.com>:

> You nean sort.c is removing objects temporarily from the vector, so that
> they are not reachable from any other root, especially from the control
> stack? Could be, the code is a bit hard to follow.

The comment in cleanup_mem is explicit about this:

>   /* If we have an exception while merging, some of the list elements
>      might only live in temp storage; we copy everything remaining in
>      the temp storage back into the original list.  This ensures that
>      the original list has all of the original elements, although
>      their order is unpredictable.  */


> Please make it easy for a concurrent, mostly-copying GC, use the stack

We can't use the C stack for allocations of arbitrary size, unfortunately.

Furthermore, we currently make the (correct) assumption that explicit xmalloc/xfree for temporary storage is faster than allocating a Lisp vector in most places. If a new GC shrinks the performance gap sufficiently, then we could reconsider that.

See bug#69709 for the new `sort` plan.

Message #26 received at 69706 <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 69706 <at> debbugs.gnu.org
Subject: Re: bug#69706: 30.0.50; sort.c, unnecessary GC marking
Date: Sun, 10 Mar 2024 15:01:59 +0100

Mattias Engdegård <mattias.engdegard <at> gmail.com> writes:

> 10 mars 2024 kl. 12.29 skrev Gerd Möllmann <gerd.moellmann <at> gmail.com>:
>
>> You nean sort.c is removing objects temporarily from the vector, so that
>> they are not reachable from any other root, especially from the control
>> stack? Could be, the code is a bit hard to follow.
>
> The comment in cleanup_mem is explicit about this:

Ok, too bad :-(

>
>>   /* If we have an exception while merging, some of the list elements
>>      might only live in temp storage; we copy everything remaining in
>>      the temp storage back into the original list.  This ensures that
>>      the original list has all of the original elements, although
>>      their order is unpredictable.  */
>
>
>> Please make it easy for a concurrent, mostly-copying GC, use the stack
>
> We can't use the C stack for allocations of arbitrary size,
> unfortunately.

That goes without saying. I was more thinking about having a Lisp_Vector
on the stack, maybe in the state, which is already on the stack.

> Furthermore, we currently make the (correct) assumption that explicit
> xmalloc/xfree for temporary storage is faster than allocating a Lisp
> vector in most places. If a new GC shrinks the performance gap
> sufficiently, then we could reconsider that.
>
> See bug#69709 for the new `sort` plan.

Thanks, if I find the time, I'll take a look.

So, I guess I should close this.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.