Re: sorting in C

[Andrew Cohen <acohen@ust.hk>]

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

    >> From: Andrew Cohen <acohen@ust.hk> Date: Sun, 27 Feb 2022
    >> 10:27:30 +0800 Cc: Mattias Engdegård <mattiase@acm.org>

[...]

    >> Dealing with the tmp space is my one remaining question. I note
    >> that when sorting a list of length L, the current (vector)
    >> sorting routine requires space for a tmp array of length L/2.  It
    >> uses SAFE_ALLOCA_LISP (and SAFE_FREE) outside the sorting routine
    >> and passes a pointer to the storage as an argument to
    >> =sort_vector_inplace=. This way memory management is easy.
    >> 
    >> TIMSORT /also/ requires space for a tmp array of length L/2, but
    >> only in the worst case (random lists). For partially sorted lists
    >> it can make do with less. So it takes a dynamic approach: it
    >> allocates a small amount of storage (enough for an array of
    >> length 256) which can handle all short lists and longer partially
    >> sorted lists; and then allocates additional storage on the fly as
    >> needed for other cases.
    >> 

[...]

    EZ> It is okay to use the existing scheme, since it will at worst
    EZ> have the same limitation as the existing one: when the list or
    EZ> vector to sort is very large, you might run out of memory trying
    EZ> to allocate L/2-size array.

    EZ> However, from your description, it doesn't sound like the more
    EZ> optimal approach of allocating dynamically is much more
    EZ> complicated.  In particular, what Mattias said should be easy
    EZ> using the unwind-protect machinery we already have (and use in
    EZ> many similar situations).  See the calls to
    EZ> record_unwind_protect_ptr whose first argument is 'xfree'.  We
    EZ> also have reallocation routines ready to be used.

That is how I am handling it now, but I'm not sure if I have it right
(sorry for the naive question):

When I need new memory I call

:   specpdl_ref sa_count = SPECPDL_INDEX ();
:   a = (Lisp_Object *) record_xmalloc (need * sizeof (Lisp_Object));

and I save =sa_count=; I guess =record_xmalloc= handles freeing the
memory on exception. Later during the sorting process I free the memory
explicitly with 

: safe_free (sa_count)

Does this seem right? (Probably, since I've been running this way for
awhile and would have expected lots of problems if I weren't allocating
and freeing the memory :))


-- 
Andrew Cohen