libkern: qsort: Sync with libc sources

[jlduran]

Summary

See 5205b32de3fb ("libc: Drop incorrect qsort optimization") for
additional details.

PR: 287089
MFC after: 1 week

[des]

if I were you I would just leave the qsort_s() code in, it's #ifdefed out anyway.

[jlduran]

Address suggestions:

• Leave qsort_r_compat and qsort_s code, it is #ifdefed out anyway, plus it reduces the diff.

[kevans]

Have you looked into how feasible it would be to sync them up and just have libc reach into libkern for the bulk of the implementation?

[des]

In D51920#1186595, @kevans wrote:

Have you looked into how feasible it would be to sync them up and just have libc reach into libkern for the bulk of the implementation?

I had the same thought, but I would prefer if we landed this first so I can MFC it without the build changes.

[des]

I'm going to land D51919 now so I can MFC the smallest possible change, then you can turn this review into a patch that moves libc qsort.c into libkern and has libc pull it from there.

[jlduran]

In D51920#1186595, @kevans wrote:

Have you looked into how feasible it would be to sync them up and just have libc reach into libkern for the bulk of the implementation?

OK, will look into that.
I would prefer to have it duplicated, but I guess it is prone to getting out of sync in the future.

In D51920#1186610, @des wrote:

I'm going to land D51919 now so I can MFC the smallest possible change, then you can turn this review into a patch that moves libc qsort.c into libkern and has libc pull it from there.

OK, let's go with this plan. It also buys me some time to test the benchmarks described in the article, for comparison.

[kevans]

In D51920#1186615, @jlduran wrote:

In D51920#1186595, @kevans wrote:

Have you looked into how feasible it would be to sync them up and just have libc reach into libkern for the bulk of the implementation?

OK, will look into that.
I would prefer to have it duplicated, but I guess it is prone to getting out of sync in the future.

I'm curious to hear you're reasoning there... in general, these things frequently get out of sync and I can't imagine off-hand why we wouldn't want to reduce our maintenance burden if the implementations are (or should be) largely the same.

[jlduran]

In D51920#1186616, @kevans wrote:

In D51920#1186615, @jlduran wrote:

In D51920#1186595, @kevans wrote:

Have you looked into how feasible it would be to sync them up and just have libc reach into libkern for the bulk of the implementation?

OK, will look into that.
I would prefer to have it duplicated, but I guess it is prone to getting out of sync in the future.

I'm curious to hear you're reasoning there... in general, these things frequently get out of sync and I can't imagine off-hand why we wouldn't want to reduce our maintenance burden if the implementations are (or should be) largely the same.

Just to have kernel/userland implementations. Note that I'm not opposed to the idea, in fact, I will look into it.

[jlduran]

It will take a while.
From a brief series of tests[1] libkern's implementation is slightly more performant than libc's (Note that this test already has D51919 applied, as it prevents it from going quadratic.).
Also, I'd like to take a look at OpenBSD, NetBSD, and especially macOS' which perform really well overall.

[1]: https://github.com/jlduran/qsort_dev/actions/runs/17001051638/job/48202771322

[des]

I already benchmarked NetBSD's code, we're about twice as fast as them. Apple's code is ours (including the insertion sort bug) with an added recursion limit.

[jlduran]

In D51920#1186701, @des wrote:

Apple's code is ours (including the insertion sort bug) with an added recursion limit.

I'm testing with the current version from https://github.com/apple-oss-distributions/Libc/blob/main/stdlib/FreeBSD/qsort.c although it has swap_cnt it doesn't go quadratic (e.g., testing the minimal example from bug #287089 on a mac results in qsort: 886371 compares, 0.003354 seconds). As you well point out, we are their upstream, so the diff is minimal compared to the others.