Re: [PATCH v3 0/7] Use introsort for qsort

[Adhemerval Zanella via Libc-alpha <libc-alpha@sourceware.org>]

On 06/09/2021 21:14, Paul Eggert wrote:
> On 9/6/21 7:13 AM, Carlos O'Donell wrote:
> 
>> All existing ruby implementations I can see use qsort in an
>> AS-safe-requiring context (process.c) and this would help those scenarios.
> 
> I don't see how those scenarios are practical. Assuming glibc and the standard Ruby implementation, any async signal problems could occur only if Ruby's spawn method has more than 32 redirects, as this is the minimum number that would cause qsort to call malloc on practical platforms. In practice Ruby spawns don't have that many redirects, so Ruby programs won't run into a problem unless they're contrived to illustrate this portability bug in the Ruby implementation.

I consider this a QoI to move toward provide memory bounded and async-safe
interfaces even though the interface contract does not really specify such
constraint.  I give you that it might lead to non-portable code such the
ruby case, but I prefer to actually move the interface to be async-safe
instead of either trying break the caller expectations (that only works due
an optimization) or changing the implementation and let the users handle 
any potential breakage.

Eventually what might happen when some breakage occurs is users like ruby 
to roll out their own qsort() implementation to fulfill its need.

We already have some concession about symbols that are not support to work
in some scenarios (such as malloc() after fork()).

> 
>> If we want better performance we need to:
>>
>> - Add new APIs mirroring what BSD is doing.
> 
> BSD's APIs are not good, partly because they rely on nonportable C extensions (blocks) that I doubt whether glibc can insist on, partly for other reasons discussed below. An API like what I suggested in my previous email would be better, if we want to add new APIs.

The blocks usage is only for *_b symbols, the BSD do provide default
C compliant mergesort and heapsort.  Also, FreeBSD really specifies
the worst-case space complexity and its quicksort has constant-size
(although it uses recursion).

> 
>> - New APIs explicitly call out the *type* of sort algorithm.
> 
> "Type" should not mean "heapsort" vs "quicksort" vs "mergesort" as in BSD. Users need performance, async-signal-safety, and stability; the BSD "type" approach is merely a means to that end and any new API should focus on their needs rather than on "type".
> 
>> we should aim for a good implementation that is as safe as we
>> can make it (limit memory usage, avoid malloc, avoid quadratic performance
>> behaviour).
> 
> If such an approach doesn't significantly hurt typical performance, I'm all for it. I'm skeptical that it's doable, though.

As I put, it is always a tradeoff.  Making async-safe means that we need to
either use a different algorithm with constant worst-case space, use a
hybrid approach, or use a different mechanism to allocate memory.

> 
> Let's not underestimate ordinary users' desires for performance here. qsort is used in other core apps (e.g., Emacs) without running afoul of async-signal-safety bugs.
> 
> Also, this is not merely about core apps like Emacs and Ruby; it's also about user one-off apps.  I often see Glibc qsort in benchmarks, and if the benchmarks results become significantly worse we'll be more likely to scare users away from Glibc and toward other platforms. Unless we can fix the significant performance issues in the proposed patch, the benefit of working around an only-theoretical bug in Ruby's implementation doesn't seem worth this cost.

I really don't think providing a async-safe with constant worst-case space
and be *clear* about it will 'scare away' uses, specially because we are
making the interface behaving in a more constraint way which imho is good
way forward.  Users will roll out their implementation due different needs
and tradeoff, such as gcc or python.

What I think really upsets users it finding out that if they use a different
element size or a large number its qsort now starts to call mallocs, or starts
to opens system files, or when memory is low it fallbacks to a completely
different implementation (which might have quadratic performance in some cases).

One possibility is to keep the mergesort using the static array if it
fits and fallback to another sorting (possible heapsort or at least
the intrasort I am suggesting).  I still prefer to keep it simple and
with a predictable performance.