[PATCH v3 0/7] Use introsort for qsort

[Paul Eggert]

On 9/7/21 7:32 AM, Adhemerval Zanella wrote:

> I consider this a QoI to move toward provide memory bounded and async-safe
> interfaces

This is of course fine for new APIs. However, qsort users are accustomed 
to the longstanding behavior, and good performance is part of their 
expectations.


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

Ruby already has its own qsort implementation. Ruby's portability bug 
(which occurs only in theory) is that at a delicate point during a fork 
Ruby uses the system qsort rather than its own qsort.

For what it's worth I submitted a patch for this bug 
<https://bugs.ruby-lang.org/issues/18152>. Regardless of whether that 
patch is accepted, this Ruby example is not a good argument for changing 
glibc qsort behavior, since the bug is not triggered in practical programs.


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

Yes, often it make sense to go beyond what the standard requires. 
However, each case is different needs to be decided on its own merits.


> The blocks usage is only for *_b symbols, the BSD do provide default
> C compliant mergesort and heapsort.

The blocks usage in macOS is essential for doing closures (the 
equivalent of qsort_r). Since we don't want to require blocks, we need a 
better API than what macOS supplies for non-qsort.

Would you like to work together to come up with a new API that addresses 
both of our concerns?


> 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.

If we were creating the qsort implementation for the first time, the 
async-signal-safety arguments could be compelling. However, it is an 
entirely different thing to ask a significant number of users to change 
longstanding uses; this would be more work for them simply because the 
libc maintainers changed their mind about a particular 
performance-safety tradeoff.


> 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

Users can be upset by many things. They can be upset if qsort calls 
malloc. They can be upset if qsort is slow. They can be especially upset 
if we make changes to qsort that force them to rewrite their code. No 
matter what we do, users can be upset. It's our job to manage these 
tradeoffs, and to do so in a stable and responsible way.