bug#54532: [PATCH] sorting

[Andrew Cohen <acohen@ust.hk>]

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

[...]

    >> Because Lisp values are temporarily moved out to a heap allocated
    >> buffer which isn't traversed by the stack
    >> scanner. `record_unwind_protect_ptr_mark` can be seen as a
    >> generalisation of `record_unwind_protect_ptr` (because that's
    >> what it is).

    EZ> I understand that these objects are on the heap, but AFAIU a
    EZ> reference to them is on the stack, isn't it?

Not always. The algorithm merges sublists A and B (which are adjacent to
each other on the stack). Doing this entirely in place is very slow
(lots of swaps) so we use temp memory of size A (assume A is the shorter
list). The idea is to copy the A list to the heap memory, and then use
the standard merge algorithm between the heap version of A and (stack
version of) B, filling in the space where A used to reside in the
stack. The issue is that since we are filling in areas in the stack that
were once occupied by A we can end up with some of the original
Lisp_Objects residing only in the /copy/ of A on the heap. Once the
merging is done, everyone is at home back on the stack.

Maybe a simple example: A = (A1, A2) and B=(B1, B2) with merged ordering (A1,
B1, A2, B2). Here is the merge sequence:
(A1, A2, B1, B2) (start)
(A1, A2, B1, B2) (copy A1 from the heap to the first space)
(A1, B1, B1, B2) (copy B1 from the stack to the second place)
(A1, B1, A2, B2) (copy A2 from the heap to the third place and finish)

Notice that in the third step A2 exists only in the heap copy. 

Best,
Andy
-- 
Andrew Cohen