Re: [PATCH] msort: Get rid of alloca.

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 06/07/23 16:29, Xi Ruoyao wrote:
> On Thu, 2023-07-06 at 15:17 -0400, Joe Simmons-Talbott via Libc-alpha wrote:
>> On Thu, Jul 06, 2023 at 10:43:42AM -0300, Adhemerval Zanella Netto wrote:
>>>
>>>
>>> On 03/07/23 13:08, Joe Simmons-Talbott via Libc-alpha wrote:
>>>> On Fri, Jun 30, 2023 at 01:12:28PM -0700, Paul Eggert wrote:
>>>>> On 2023-06-30 10:26, Joe Simmons-Talbott via Libc-alpha wrote:
>>>>>
>>>>>> +  /* If the memory requirements are too high don't allocate memory.  */
>>>>>> +  if (size / pagesize > (size_t) phys_pages)
>>>>>> +    {
>>>>>> +      _quicksort (b, n, s, cmp, arg);
>>>>>> +      return;
>>>>>> +    }
>>>>>> ...
>>>>>> +  if (!scratch_buffer_set_array_size (&buf, 1, size))
>>>>>> +    {
>>>>>> +      /* Couldn't get space, so use the slower algorithm
>>>>>> +         that doesn't need a temporary array.  */
>>>>>> +      _quicksort (b, n, s, cmp, arg);
>>>>>> +      return;
>>>>>>       }
>>>>>
>>>>> Please combine the two ifs into one, since their then-parts are the same and
>>>>> that will make the code easier to follow.
>>>>
>>>> I'll do this in v2.  Thanks for the suggestion and the review.
>>>>
>>>>>
>>>>>
>>>>>> +  scratch_buffer_free (&buf);
>>>>>
>>>>> Dumb question: can we arrange for scratch_buffer_free to be called even if
>>>>> qsort's comparison function longjmps out of qsort? I realize the old code
>>>>> leaked in that case, but it'd be nice if the new code didn't leak too. This
>>>>> sort of longjmp sometimes happens in real code, e.g., in GNU 'ls'.
>>>>>
>>>>
>>>> I'll have to defer to someone more knowledgable than me on this one.  My
>>>> understanding is that longjmp resets the stack pointer and doesn't call
>>>> any GCC cleanup handlers thus ruling out the one option I was able to
>>>> think of.  Does anyone else have thoughts on this?
>>>
>>> Another option would to just remove malloc from qsort usage, by using the
>>> quicksort implementation instead.  To avoid the worse case we fallback to
>>> a simple heapsort, as some of C++ implementation does.  This has the advantage
>>> of fixing the possible longjmp issue and making the qsort full async-safe.
>>>
>>
>> From my understanding there are three cases in __qsort_r; small where we
>> use alloca, medium where we use malloc, and large where we use
>> _quicksort.  This would lead to always using _quicksort, if I understand
>> correctly.  _quicksort reduces the probability of the worst case by
>> choosing the median as the pivot.  Am I missing something?
> 
> "To avoid the worse case we fallback to a simple heapsort".  This is not
> implemented in _quicksort yet.
> 
> See https://en.wikipedia.org/wiki/Introsort.

The issue is mergesort is a stable sort and usually much faster than
quicksort, so changing the implementation to introsort will have performance
impacts.  That's the main issue Paul has brought in a previous attempt [1],
as he suggested that instead we provide a better API instead.  I still think
this is an orthogonal issue, we should instead strive on glibc to provide
a simpler implementation that works on most scenarios without adding significant
drawnbacks (that's why I suggested a non quadratic implementation without
the need to allocate extra memory).

And it seems that FreeBSD developers is also moving toward this direction.
They tried to improve bsort a bitonic type sorting, but revert it instead [2]
with an important remark:

  libc is not the right place for sorting algorithms

So I still think that we should provide better sorting algorithms through
a different project (maybe gnulib itself).

[1] https://sourceware.org/pipermail/libc-alpha/2021-September/130698.html
[2] https://github.com/freebsd/freebsd-src/commit/bb8e8e230d94c9522bd9ff95c13dc9f5b1592929