[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <OlSnP45UngXLkUJ8mnHSB6uorof2Lz3e6h1JMtPALAtpb7iSPg8LdcAFdk-H3o4daNOANuGNFX8ruDQ4nm0xEnGuCOBYie8QTa9l94_t7Io=@proton.me>
Date: Sun, 19 Apr 2026 04:25:24 +0000
From: David Sparks <sparks05@...ton.me>
To: "dalias@...ifal.cx" <dalias@...ifal.cx>
Cc: "musl@...ts.openwall.com" <musl@...ts.openwall.com>, "mailto.luca.kellermann@...il.com" <mailto.luca.kellermann@...il.com>, David Sparks <sparks05@...ton.me>
Subject: Re: Some additional qsort patches
On Sunday, April 19th, 2026 at 02:38, dalias@...ifal.cx <dalias@...ifal.cx> wrote:
> On Wed, Apr 15, 2026 at 01:05:45AM +0000, David Sparks wrote:
>> Thank you! This would be a wonderful addition to the coding-style
>> wiki page, which I read very carefully before sending anything.
>
> Yeah. There are a lot of things like this that were written down in
> various places over the years but never consolidated in a good place
> for new folks to find.
The coding-style doc seems like a good place. "Musl strongly prefers
to avoid code churn (so that fixes backport as easily as possible), so
do not 'fix' style issues unless there is a functional reason to change
the corresponding code region, or it's something really egregious like
misleading indentation or comments."
I don't know what the policy is about compiler warnings.
> Before we even worry about whether this warrants manual optimization
> we should probably know how much time is spent on it to begin with. I
> suspect it's vanishingly small.
The code is called every time we traverse the stepchild link,
either in trinkle() after popping the root of a non-singleton tree,
or after popping the root of a singleton tree, so it's called at
least n times even if the input is presorted.
The cmp() function obviously dominates, but it's a pretty warm path.
I will, however, do some benchmarks.
>> 1) Using __uint128_t (or uint64_t on 32-bit) for the tree-size
>> bitmap. This would require a chunk of ugly preprocessor
>> code to find the appropriate data type, plus the current
>> code as a fallback.
>
> Yeah, that's not something I'd want to be doing. musl is written in
> C99 to the maximum extent possible, using a minimal set of extensions,
> and builds fine on pcc, gcc 3, firm/cparser, etc.
As I mentioned, there would absolutely have to be a fallback
implementation, which is why it would be a bit ugly. (But all
neatly encapsulated so the core qsort code wouldn't be uglified.)
> On most archs using __[u]int128_t would be calling out to libgcc
> anyway, and the branch would just be moved there.
Actually, as you can see from the lack of libgcc helper calls in
the previous sample code, gcc and clang can inline most uint128_t math.
In particular, logical operations, shifts, and __builtin_ctzg are
all inlined.
This shouldn't be surprising. double-width math has been well supported
by C compilers since the 16-bit PDP-11 implemented 32-bit longs.
>> 2) Saving a compare in trinkle(). There seem to be two ways
>> to go about this:
>> 2a) Move the top level of sift() into trinkle(), and have
>> the call to sift() take the appropriate subtree, or
>
> What do you mean by the "top level"? The first iteration of the loop?
Yes; I was talking about "top" in a tree sense, not a code sense.
Code-wise, it's the first iteration of the sift-down loop.
When trinkling down an order-k (k >= 2) Leonardo tree, we'd figure
out which branch to take while leaving the trinkle loop, and call
sift on the appropriate order-k-1 or order-k-2 subreeee.
This duplicates a bit of code, but is definitely the smaller patch.
>> 2b) Implement a do_sift() helper which takes the root compare
>> as an argument and can be used by both sift() and
>> trinkle(). (This has the potential to take an ar[] array
>> as well and merge the cycle() operations.)
>
> This maybe sounds better, but I'd probably have to see it to
> understand what you mean.
I'm working on all of this; I just got sidetracked finding
64-bit multipliers for using Matt Taylor's folding trick
in ctz128.
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
