Wrong info in libc comparison

Wrong info in libc comparison

[Markus Wichmann]

Hello,

there's a mistake on the libc comparison page
http://www.etalabs.net/compare_libcs.html: Namely it states that glibc
uses introsort as sorting algorithm. It doesn't. Glibc uses a
bog-standard merge sort as main sorting algorithm. A major part of the
implementation is actually just devoted to optimized copying, and for
arrays of large objects it uses an interesting way to indirectly sort
them (i.e. it then allocates an array of references, sorts the
references, then uses a clever algorithm to get from sorted references
to a sorted array). But it's all just a standard merge sort.

However, merge sort on arrays requires a linear amount of scratch space,
so this merge sort has to allocate memory. Memory allocation is allowed
to fail, but sorting isn't, so, as a fallback, in case the allocation
fails (or would use more than half the physical memory, for some
reason), it falls back to quicksort. This quicksort is implemented with
a really funky scheme for an explicit stack (i.e., while I'd use

    push_total_problem();
    while (stack_not_empty()) {
        pop_subprob();
        if (subprob_worth_bothering_with()) {
            sort_partition();
            push_larger_subprob();
            push_smaller_subprob();
        }
    }

they do something more like:

    push_pseudo_problem();
    while (stack_not_empty()) {
        if (subprob_worth_bothering_with()) {
            sort_partition();
            figure_out_next_subproblem();
            then_maybe_push_or_pop_stuff();
        }
    }

), a median-of-three pivot selection, two-way partitioning (why couldn't
you be perfect for me?), and a minimum partition size of 4,
necessitating an insertion sort stage afterwards.

So, yeah, no introsort in sight. Introsort would be merge sort on large
arrays, then quicksort on smaller partitions, and finally insertion sort
for the smallest partitions.

Ciao,
Markus

Re: Wrong info in libc comparison

[Rich Felker]

On Wed, Sep 13, 2017 at 03:51:54PM +0200, Markus Wichmann wrote:
> Hello,
> 
> there's a mistake on the libc comparison page
> http://www.etalabs.net/compare_libcs.html: Namely it states that glibc
> uses introsort as sorting algorithm. It doesn't. Glibc uses a
> bog-standard merge sort as main sorting algorithm. A major part of the
> implementation is actually just devoted to optimized copying, and for
> arrays of large objects it uses an interesting way to indirectly sort
> them (i.e. it then allocates an array of references, sorts the
> references, then uses a clever algorithm to get from sorted references
> to a sorted array). But it's all just a standard merge sort.
> 
> However, merge sort on arrays requires a linear amount of scratch space,
> so this merge sort has to allocate memory. Memory allocation is allowed
> to fail, but sorting isn't, so, as a fallback, in case the allocation
> fails (or would use more than half the physical memory, for some
> reason), it falls back to quicksort. This quicksort is implemented with
> a really funky scheme for an explicit stack (i.e., while I'd use
> 
>     push_total_problem();
>     while (stack_not_empty()) {
>         pop_subprob();
>         if (subprob_worth_bothering_with()) {
>             sort_partition();
>             push_larger_subprob();
>             push_smaller_subprob();
>         }
>     }
> 
> they do something more like:
> 
>     push_pseudo_problem();
>     while (stack_not_empty()) {
>         if (subprob_worth_bothering_with()) {
>             sort_partition();
>             figure_out_next_subproblem();
>             then_maybe_push_or_pop_stuff();
>         }
>     }
> 
> ), a median-of-three pivot selection, two-way partitioning (why couldn't
> you be perfect for me?), and a minimum partition size of 4,
> necessitating an insertion sort stage afterwards.
> 
> So, yeah, no introsort in sight. Introsort would be merge sort on large
> arrays, then quicksort on smaller partitions, and finally insertion sort
> for the smallest partitions.

I'm not sure we agree on what introsort means -- normally I take it to
mean doing an O(n²) algorithm with good "typical case" performance to
begin with, but switching to an O(log n) algorithm with a worse
constant factor as soon as it detects a risk that time will grow
quadratically. Normally this is something like starting with quicksort
and possibly switching to heapsort, and my understanding at the time
was that glibc was doing that or something similar, and AFAIK it still
is in the general case where there's insufficient memory for a merge
sort. Does that sound incorrect?

Rich

Re: Wrong info in libc comparison

[Markus Wichmann]

On Wed, Sep 13, 2017 at 02:10:10PM -0400, Rich Felker wrote:
> I'm not sure we agree on what introsort means -- normally I take it to
> mean doing an O(n²) algorithm with good "typical case" performance to
> begin with, but switching to an O(log n) algorithm with a worse
> constant factor as soon as it detects a risk that time will grow
> quadratically. Normally this is something like starting with quicksort
> and possibly switching to heapsort, and my understanding at the time
> was that glibc was doing that or something similar, and AFAIK it still
> is in the general case where there's insufficient memory for a merge
> sort. Does that sound incorrect?
> 
> Rich

At least the version I was looking at (2.19) doesn't do that at all. As
I said, even in case of failed malloc(), all it does is a quicksort.
With an insertion sort afterwards, but that's not introsort by either of
our definitions. And in any case, malloc() failure is rare these days,
so the main algorithm is merge sort.

I just checked the version Debian is currently distributing (2.24) and
saw that nothing major has changed. stdlib/msort.c contains the merge
sort algorithm, and stdlib/qsort.c contains the quicksort fallback, for
your perusal.

Ciao,
Markus

Re: Wrong info in libc comparison

[Szabolcs Nagy]

* Markus Wichmann <nullplan@gmx.net> [2017-09-13 20:51:06 +0200]:
> On Wed, Sep 13, 2017 at 02:10:10PM -0400, Rich Felker wrote:
> > I'm not sure we agree on what introsort means -- normally I take it to
> > mean doing an O(n²) algorithm with good "typical case" performance to
> > begin with, but switching to an O(log n) algorithm with a worse
> > constant factor as soon as it detects a risk that time will grow
> > quadratically. Normally this is something like starting with quicksort
> > and possibly switching to heapsort, and my understanding at the time
> > was that glibc was doing that or something similar, and AFAIK it still
> > is in the general case where there's insufficient memory for a merge
> > sort. Does that sound incorrect?
> > 
> > Rich
> 
> At least the version I was looking at (2.19) doesn't do that at all. As
> I said, even in case of failed malloc(), all it does is a quicksort.
> With an insertion sort afterwards, but that's not introsort by either of
> our definitions. And in any case, malloc() failure is rare these days,

i think malloc failure case is the one that matters
for worst case analysis so the comparision table
should say whatever quicksort is doing.

Re: Wrong info in libc comparison

[Rich Felker]

On Wed, Sep 13, 2017 at 09:25:29PM +0200, Szabolcs Nagy wrote:
> * Markus Wichmann <nullplan@gmx.net> [2017-09-13 20:51:06 +0200]:
> > On Wed, Sep 13, 2017 at 02:10:10PM -0400, Rich Felker wrote:
> > > I'm not sure we agree on what introsort means -- normally I take it to
> > > mean doing an O(n²) algorithm with good "typical case" performance to
> > > begin with, but switching to an O(log n) algorithm with a worse
> > > constant factor as soon as it detects a risk that time will grow
> > > quadratically. Normally this is something like starting with quicksort
> > > and possibly switching to heapsort, and my understanding at the time
> > > was that glibc was doing that or something similar, and AFAIK it still
> > > is in the general case where there's insufficient memory for a merge
> > > sort. Does that sound incorrect?
> > > 
> > > Rich
> > 
> > At least the version I was looking at (2.19) doesn't do that at all. As
> > I said, even in case of failed malloc(), all it does is a quicksort.
> > With an insertion sort afterwards, but that's not introsort by either of
> > our definitions. And in any case, malloc() failure is rare these days,
> 
> i think malloc failure case is the one that matters
> for worst case analysis so the comparision table
> should say whatever quicksort is doing.

If you're considering big-O, where n->infinity (or at least to the
largest value that can fit in memory), malloc most certainly has
failed (because the array to be sorted already filled memory) and
you're looking at the "fallback" case.

Maybe the comparison of sort algorithm used is interesting for reasons
other than just big-O though, in which case mentioning the "merge
(when it fits in memory)" would probably be helpful.

Rich

Re: Wrong info in libc comparison

[Markus Wichmann]

On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> If you're considering big-O, where n->infinity (or at least to the
> largest value that can fit in memory), malloc most certainly has
> failed (because the array to be sorted already filled memory) and
> you're looking at the "fallback" case.
> 

I think we're getting sidetracked here. Every libc worth its salt uses a
loglinear sorting algorithm. Thus they are all equal in that regard.
Only exception to this I've ever seen is uclibc, which uses Shell sort
with Pratt's sequence, which is O(sqrt(n^3)) instead (is there a snappy term
for this complexity?)

Besides, big-O is also about the behavior of time on change of space
(what happens if the problem doubles in size?).

> Maybe the comparison of sort algorithm used is interesting for reasons
> other than just big-O though, in which case mentioning the "merge
> (when it fits in memory)" would probably be helpful.
> 
> Rich

Algorithms can be compared on a number of metrics, and just the name
doesn't tell us much (e.g. quicksort with naive "first element" pivot
selection has a pathological case on sorted input, while quicksort with
med3 pivot selection handles that very well). If you really want to know
something specific, you'll have to look it up in source, anyway.

But, if you do give a name, make sure it's the right one.

Ciao,
Markus

Re: Wrong info in libc comparison

[Szabolcs Nagy]

* Markus Wichmann <nullplan@gmx.net> [2017-09-15 21:18:46 +0200]:
> On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> > If you're considering big-O, where n->infinity (or at least to the
> > largest value that can fit in memory), malloc most certainly has
> > failed (because the array to be sorted already filled memory) and
> > you're looking at the "fallback" case.
> > 
> 
> I think we're getting sidetracked here. Every libc worth its salt uses a
> loglinear sorting algorithm. Thus they are all equal in that regard.

that is not true at all.
embedded libcs are often optimized for size, not worst case behaviour.
note that worst-case behaviour is not just big-O..
(e.g. glibc uses mergesort which uses malloc which means it's not as-safe,
may introduce arbitrary latency since malloc can be interposed, concurrent
mallocs can delay forward progress, large allocation may cause swapping,
cancellation or longjmp out of the cmp callback can leak memory etc.)

> > Maybe the comparison of sort algorithm used is interesting for reasons
> > other than just big-O though, in which case mentioning the "merge
> > (when it fits in memory)" would probably be helpful.
> > 
> > Rich
> 
> Algorithms can be compared on a number of metrics, and just the name
> doesn't tell us much (e.g. quicksort with naive "first element" pivot
> selection has a pathological case on sorted input, while quicksort with
> med3 pivot selection handles that very well). If you really want to know
> something specific, you'll have to look it up in source, anyway.

"mergesort+quicksort" sounds good to me,
it tells enough about what's going on, if there is some
known implementation mistake that can be added to the
description (like "naive" quicksort for dietlibc implying
O(n^2) worst case compares and potentially large stack use)

Re: Wrong info in libc comparison

[Markus Wichmann]

On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote:
> * Markus Wichmann <nullplan@gmx.net> [2017-09-15 21:18:46 +0200]:
> > On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> > > If you're considering big-O, where n->infinity (or at least to the
> > > largest value that can fit in memory), malloc most certainly has
> > > failed (because the array to be sorted already filled memory) and
> > > you're looking at the "fallback" case.
> > > 
> > 
> > I think we're getting sidetracked here. Every libc worth its salt uses a
> > loglinear sorting algorithm. Thus they are all equal in that regard.
> 
> that is not true at all.
> embedded libcs are often optimized for size, not worst case behaviour.
> note that worst-case behaviour is not just big-O..
> (e.g. glibc uses mergesort which uses malloc which means it's not as-safe,
> may introduce arbitrary latency since malloc can be interposed, concurrent
> mallocs can delay forward progress, large allocation may cause swapping,
> cancellation or longjmp out of the cmp callback can leak memory etc.)
> 

Did you even read what I wrote? Rich talked about big-O, i.e. complexity
theory, to which I remarked that most algorithms in use are loglinear
and thus equal _in_that_regard_.

And I wrote a bit later that the only exception to this that I know of
is uclibc, which uses Shell sort with Pratt's sequence. uclibc claimed
to be optimized for smaller systems and is thus exactly an example of
your second sentence here. And your third point is what I wrote just a
few lines further below, albeit with a different example.

BTW, in addition to the libcs presented on the libc comparison page, I
had a look at newlib and avr-libc, and they both feature quicksort (and
at least for avr-libc I can't figure out why they did that. Maybe
habit).

> > > Maybe the comparison of sort algorithm used is interesting for reasons
> > > other than just big-O though, in which case mentioning the "merge
> > > (when it fits in memory)" would probably be helpful.
> > > 
> > > Rich
> > 
> > Algorithms can be compared on a number of metrics, and just the name
> > doesn't tell us much (e.g. quicksort with naive "first element" pivot
> > selection has a pathological case on sorted input, while quicksort with
> > med3 pivot selection handles that very well). If you really want to know
> > something specific, you'll have to look it up in source, anyway.
> 
> "mergesort+quicksort" sounds good to me,
> it tells enough about what's going on, if there is some
> known implementation mistake that can be added to the
> description (like "naive" quicksort for dietlibc implying
> O(n^2) worst case compares and potentially large stack use)

Agreed. As I said, if you want to know specifics, looking up keywords is
not the way to go, anyway, and since all of these libcs are open source,
someone wanting to more will have no excuse for not looking up what they
want to know in source. It is in the end the only way to be sure.

Ciao,
Markus

Re: Wrong info in libc comparison

[Rich Felker]

On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote:
> > Algorithms can be compared on a number of metrics, and just the name
> > doesn't tell us much (e.g. quicksort with naive "first element" pivot
> > selection has a pathological case on sorted input, while quicksort with
> > med3 pivot selection handles that very well). If you really want to know
> > something specific, you'll have to look it up in source, anyway.
> 
> "mergesort+quicksort" sounds good to me,
> it tells enough about what's going on, if there is some
> known implementation mistake that can be added to the
> description (like "naive" quicksort for dietlibc implying
> O(n^2) worst case compares and potentially large stack use)

Even non-naive quicksort has O(n²) time; there is a way to avoid this
with an esoteric efficient algorithm for finding the median to use as
the pivot, but nobody does it because the constant is so bad. The only
known practical way to avoid the n² worst-case is some kind of
introsort. So "naive" is really only about the problem of blowing up
the stack.

I agree something like "mergesort+quicksort" sounds good, but just to
make sure, was mergesort already in use in the glibc version in the
comparison? i.e. can I make this fix without inconsistently reflecting
information from different glibc versions?

Rich

Re: Wrong info in libc comparison

[Szabolcs Nagy]

* Markus Wichmann <nullplan@gmx.net> [2017-09-16 16:01:10 +0200]:
> On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote:
> > * Markus Wichmann <nullplan@gmx.net> [2017-09-15 21:18:46 +0200]:
> > > On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> > > > If you're considering big-O, where n->infinity (or at least to the
> > > > largest value that can fit in memory), malloc most certainly has
> > > > failed (because the array to be sorted already filled memory) and
> > > > you're looking at the "fallback" case.
> > > > 
> > > 
> > > I think we're getting sidetracked here. Every libc worth its salt uses a
                                              ^^^^^^^^^^
> > > loglinear sorting algorithm. Thus they are all equal in that regard.
      ^^^^^^^^^                         ^^^^^^^^^^^^^^^^^^
> > 
> > that is not true at all.
> > embedded libcs are often optimized for size, not worst case behaviour.
> > note that worst-case behaviour is not just big-O..
> > (e.g. glibc uses mergesort which uses malloc which means it's not as-safe,
> > may introduce arbitrary latency since malloc can be interposed, concurrent
> > mallocs can delay forward progress, large allocation may cause swapping,
> > cancellation or longjmp out of the cmp callback can leak memory etc.)
> > 
> 
> Did you even read what I wrote? Rich talked about big-O, i.e. complexity
> theory, to which I remarked that most algorithms in use are loglinear
> and thus equal _in_that_regard_.
> 

glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd
qsort are all O(n^2) worst-case, musl qsort is O(n log(n)).

i think this is not a sidetrack, but relevant detail
for a libc comparision page.
(the openbsd proof of concept stack clash exploit
relied on the unbounded stack use in qsort, that
would not work against musl, but all the other libcs
are affected.)

Re: Wrong info in libc comparison

[Markus Wichmann]

On Sat, Sep 16, 2017 at 12:18:02PM -0400, Rich Felker wrote:
> Even non-naive quicksort has O(n²) time; there is a way to avoid this
> with an esoteric efficient algorithm for finding the median to use as
> the pivot, but nobody does it because the constant is so bad. The only
> known practical way to avoid the n² worst-case is some kind of
> introsort. So "naive" is really only about the problem of blowing up
> the stack.
> 

Oh crap, yes, I forgot about that. Median-of-three only solves the
quadratic time problem on sorted inputs but quadratic sequences still
exist. My bad.

> I agree something like "mergesort+quicksort" sounds good, but just to
> make sure, was mergesort already in use in the glibc version in the
> comparison? i.e. can I make this fix without inconsistently reflecting
> information from different glibc versions?
> 
> Rich

Yes, I previously looked at glibc 2.19 and it had the same code.

Apparently, the files are really old with only minor changes over the
years. At least, that's what I gathered from the changelogs.

Ciao,
Markus

Re: Wrong info in libc comparison

[Markus Wichmann]

On Sat, Sep 16, 2017 at 07:11:54PM +0200, Szabolcs Nagy wrote:
> glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd
> qsort are all O(n^2) worst-case, musl qsort is O(n log(n)).
> 

Yes, sorry, I mixed that up. Quicksort is loglinear only in the average
case. Same for Shell sort being O(sqrt(n^3)).

> i think this is not a sidetrack, but relevant detail
> for a libc comparision page.
> (the openbsd proof of concept stack clash exploit
> relied on the unbounded stack use in qsort, that
> would not work against musl, but all the other libcs
> are affected.)

No, stack usage is not necessarily linear even with quicksort. dietlibc
and avr-libc have linear stack usage (with avr-libc always recursing
into the first subproblem, and dietlibc always recursing into both
subproblems), that's right, but glibc uses a constant amount of stack
(automatic allocation of an array to hold the maximum possible number of
subproblems, which is equal to the number of bits in a machine word),
and newlib uses recursion into the smaller subproblem, thus using a
logarithmic amount of stack (functionally constant, since you can give
an upper limit).

And uclibc also uses a constant amount of stack. Shell sort doesn't need
recursion.

Ciao,
Markus