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

[Paul Eggert <eggert@cs.ucla.edu>]

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.

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

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

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.