[PATCH v6 4/6] stdlib: Implement introsort for qsort (BZ 19305)

[Noah Goldstein]

On Thu, Aug 31, 2023 at 7:13 AM Adhemerval Zanella Netto
<adhemerval.zanella@linaro.org> wrote:
>
>
>
> On 29/08/23 04:45, Noah Goldstein wrote:
> > On Tue, Jul 18, 2023 at 2:08 PM Adhemerval Zanella Netto
> > <adhemerval.zanella@linaro.org> wrote:
> >>
> >>
> >>
> >> On 18/07/23 14:37, Noah Goldstein wrote:
> >>> On Tue, Jul 18, 2023 at 9:19 AM Adhemerval Zanella via Libc-alpha
> >>> <libc-alpha@sourceware.org> wrote:
> >>>>
> >>>> This patch makes the quicksort implementation to acts as introsort, to
> >>>> avoid worse-case performance (and thus making it O(nlog n)).  It switch
> >>>> to heapsort when the depth level reaches 2*log2(total elements).  The
> >>>> heapsort is a textbook implementation.
> >>>>
> >>>> Checked on x86_64-linux-gnu.
> >>>> ---
> >>>>  stdlib/qsort.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++----
> >>>>  1 file changed, 79 insertions(+), 6 deletions(-)
> >>>>
> >>>> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> >>>> index 640896a598..054c900b02 100644
> >>>> --- a/stdlib/qsort.c
> >>>> +++ b/stdlib/qsort.c
> >>>> @@ -119,6 +119,7 @@ typedef struct
> >>>>    {
> >>>>      char *lo;
> >>>>      char *hi;
> >>>> +    size_t depth;
> >>>
> >>> You don't actually need to track depth in the "stack"
> >>> when you pop hi/lo you can take log2(hi - lo) to compute
> >>> what depth counter "should" be i.e
> >>
> >> I don't think we can take the assumption quicksort will always iterate the
> >> input array as a binary tree, so we can't really use log2(hi - lo) as the
> >> depth.
> >> However I found another issue, which a change to use 'stack_node *top = stack + 1'
> >> removed the initial depth initialization.
> >>
> >
> > Bah, sorry missed your reply!
> >
> > What i mean is not that you take `log2(hi - lo)` as the current depth,
> > but whenever
> > you pop a new set of bounds you set `max_depth = log2(hi - lo)`. Then
> > in the loop if
> > `--max_depth <= 0` we are in pessimistic state -> do introsort.
> >
> > Think this works to avoid the O(N^2) state and saves a lot of state tracking.
>
> The problem with this approach is not all architectures has a clz instruction,
> so log2 will be a libgcc function call.  And due how partition are pushed on
> the stack, it is guarantee that no more than log (total_elems) state track is
> required (O(1)).  To track the state it is an extra of STACK_SIZE size_t state,
> so I am not sure if this will be a large improvement even archs with clz
> instructions.

absolutely not necessary, just a thought.