Re: sorting in C

[Eli Zaretskii]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Sun, 27 Feb 2022 10:27:30 +0800
> Cc: Mattias Engdegård <mattiase@acm.org>
> 
> 
> Mattias E. reminds me (in a private email):
> >Since Timsort may allocate temporary scratch space it is important to
> >make sure it's freed if the comparison predicate throws. A specbind
> >may be needed for the clean-up, but I haven't looked at your timsort
> >code -- perhaps you have already solved that problem.
> 
> 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.
> 
> Right now my routine accepts a pointer to tmp space as an argument; if
> this is null, it uses the dynamic allocation, and otherwise just uses
> the pre-allocated storage.
> 
> Clearly the less memory required the better, and for mostly-sorted lists
> the pre-allocated 256 is usually sufficient. This saves the space, and
> any (minimal) time needed to allocate additional space.
> 
> But the early allocation of the maximum space required (as is done for
> the current sorting routine) makes the memory management trivial (which
> is good!) and avoids the (minmal) additional time for allocs for random
> lists.
> 
> I'm inclined to just go with the current system: allocate the maximum
> required before calling the routine, but welcome any advice or
> expressions of preference for the dynamic allocation. 

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

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

You could also start with the existing scheme and then add the dynamic
allocation as a followup patch.

Bottom line: I think it's up to you.

Thanks.