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