Date: Sat, 26 Nov 2016 12:27:09 +0000 From: Tristan Verniquet <tris_vern@hotmail.com> To: Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> In-Reply-To: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com>, <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
> From: Hans Petter Selasky <hps@selasky.org> > Sent: Saturday, 26 November 2016 8:51 PM > To: Tristan Verniquet; freebsd hackers > Subject: Re: qsort switching to insertsort > > On 11/26/16 11:26, Tristan Verniquet wrote: >> The easiest way forward for us is probably to comment out the offending code. >> > > Commenting out the offending code does not help. It simply leaves for > another type of dataset to provide the same behaviour. qsort() is doomed > in this regard. > > --HPS I can see that from, say, a security perspective, as long as a worst-case exists you would assume it, and so this would make no difference. But from an everyday usage where security is not such an issue, I see the two worst-case triggers as being in different ball park. I would happily assume I'd never meet an accidental case of triggering a qsort worst-case based on pivot given the pivot selection method it uses, but can no longer have that confidence with qsort triggering an insertsort. I was kind of suspecting that this might be the reasoning behind it. For example the second link shows problems with all quicksorts. But do you not think this makes a big difference in the everyday use case where qsort would actually be used (and not avoided)? Tristan
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ME1PR01MB0546D041DC160763C5D3689883880>