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
Powered by Openwall GNU/*/Linux - Powered by OpenVZ