[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 13 Sep 2017 20:51:06 +0200
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Re: Wrong info in libc comparison
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
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.
