bug#54532: [PATCH] sorting

[Andrew Cohen <acohen@ust.hk>]

>>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:

    >> From: Andrew Cohen <acohen@ust.hk> Date: Wed, 23 Mar 2022
    >> 07:59:11 +0800
    >> 
    >> 1. Add a new `record_unwind_protect_ptr_mark` function for use
    >> with C data structures that use the specpdl for clean-up but also
    >> contain possibly unique references to Lisp objects. This is
    >> needed for the dynamic memory management that the new algorithm
    >> uses.

    EZ> Can you tell more why this was needed?  Emacs has conservative
    EZ> stack marking, so any Lisp object that is referred by some
    EZ> stack-based variable should be protected from GC.  Why isn't
    EZ> that enough in this case?

Mattias responded, but just to recap---during the merging of sublists
additional memory is dynamically xalloc'ed (and later xfree'd)  on the
heap, and there can be brief periods where the original Lisp_Objects
exist /only/ in the heap. The alternative (which we mentioned briefly in
earlier discussions) would be to allocate the maximum amount of needed
memory at the outset with SAFE_ALLOCA_LISP. This is what the current
sorting routine does. But for many (maybe most?) actual calls to timsort no
additional memory is needed so the dynamic allocation makes
significantly better use of resources. Mattias explained the issue to me
and once I understood it found it was easy to trigger; there is a
specific test in the unit test patch to check for this issue.

    >> 4. An optimization that resolves the sorting comparison symbol
    >> into the corresponding function before starting the sort.

    EZ> Any reasons this is a separate patch?

Just to make it easier to look at the rather lengthy code by segregating
things that are self-contained.  If/when we decide to put this in I
would probably squash down to two (or maybe 3) commits.

Thanks for the thorough look at the code, I continue to learn a lot!

Best,
Andy
-- 
Andrew Cohen