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 > =20 > On 11/26/16 11:26, Tristan Verniquet wrote: >> The easiest way forward for us is probably to comment out the offending = code. >> >=20 > Commenting out the offending code does not help. It simply leaves for=20 > another type of dataset to provide the same behaviour. qsort() is doomed= =20 > in this regard. >=20 > --HPS I can see that from, say, a security perspective, as long as a worst-case e= xists 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 t= wo worst-case triggers as being in different ball park. I would happily ass= ume I'd never meet an accidental case of triggering a qsort worst-case base= d 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 ex= ample the second link shows problems with all quicksorts. But do you not th= ink 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>