bug#69706: 30.0.50; sort.c, unnecessary GC marking

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Gerd Möllmann]

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

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@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.

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

> Can you show the patch, please?

I haven't made one yet. Should I?

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Eli Zaretskii]

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

I think so, yes.

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Mattias Engdegård]

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

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Gerd Möllmann]

Mattias Engdegård <mattias.engdegard@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
;-).

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Mattias Engdegård]

10 mars 2024 kl. 12.29 skrev Gerd Möllmann <gerd.moellmann@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.

bug#69706: 30.0.50; sort.c, unnecessary GC marking

[Gerd Möllmann]

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

> 10 mars 2024 kl. 12.29 skrev Gerd Möllmann <gerd.moellmann@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.