Date: Sat, 26 Nov 2016 22:40:20 -0800 From: Alfred Perlstein <alfred@freebsd.org> To: Tristan Verniquet <tris_vern@hotmail.com>, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com>, =?UTF-8?Q?Arne_Dag_Fidjest=c3=b8l?= <adf@idi.ntnu.no> Cc: Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5@freebsd.org> In-Reply-To: <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com> <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no> <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com>
next in thread | previous in thread | raw e-mail | index | archive | help
A couple notes: 1) It's interesting to me that it's based on a simple heuristic as opposed to also checking the depth of the recursion within the qsort itself. 2) Wondering if upon detection of this situation it might even be faster to perform some randomization (shuffle) of the data and then retry. 3) Wondering if there could be a way to return an error and indicate the data is unsorted if the corner case is hit allowing the caller to make a choice at that point. Obviously the API would need to be changed. I haven't thought too hard on this. One thing to keep in mind: Using qsort in a codepath has "deadlines" or other deterministic needs is not going to work out well. It's better to use a sort with a known complexity with an upper bound than something that can be defeated by a pathological input data set. -Alfred On 11/26/16 8:17 PM, Tristan Verniquet wrote: > From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> > Sent: Sunday, 27 November 2016 5:51 AM > To: Arne Dag Fidjestøl > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort > > > > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjestøl <adf@idi.ntnu.no> wrote: > >> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> wrote: >> >> In quick sort , it is necessary to check worst case and switch to another >> sort method if it is detected . >> When this is not done , end result is stack overflow , etc . , but not >> success . >> Therefore , it is not possible to eliminate an alternative sort method . > I you sort the smaller partition recursively first, and then sort the larger partition either by tail recursion or iteration, you will only consume O(log n) of stack, so stack overflow needn’t be an issue, regardless of the input. > > -adf > > > > Important problem is caused by almost sorted values . Myself , I am counting the sorted elements first , if they exceed a large percentage of number of all elements , then I am switching to an alternative sort , otherwise a quick sort is used . This is for a simple application . > > In an operating system , more complex algorithms may be more useful . > > > Mehmet Erol Sanliturk > > --- > > It can still trigger with completely unsorted data in the top and bottom half, as long as it chooses the middle value for the pivot. The main reason nearly sorted data is vulnerable is that it is more likely to match these conditions, and more likely to happen in real life situations. > > But this is why i don't really consider it an "edge" case, there would be a whole class of situations (like the one we had) where it would be very likely to trigger with very bad side effects. > > Maybe, does anyone continue to use FreeBSD qsort while being aware of this implementation detail? Under what conditions/assurances? > > Does anyone use FreeBSDs qsort because of this feature? > > Tristan > ________________________________ > From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> > Sent: Sunday, 27 November 2016 5:51:31 AM > To: Arne Dag Fidjestøl > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort > > > > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjestøl <adf@idi.ntnu.no<mailto:adf@idi.ntnu.no>> wrote: > >> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com<mailto:m.e.sanliturk@gmail.com>> wrote: >> >> In quick sort , it is necessary to check worst case and switch to another >> sort method if it is detected . >> When this is not done , end result is stack overflow , etc . , but not >> success . >> Therefore , it is not possible to eliminate an alternative sort method . > I you sort the smaller partition recursively first, and then sort the larger partition either by tail recursion or iteration, you will only consume O(log n) of stack, so stack overflow needn’t be an issue, regardless of the input. > > -adf > > > > Important problem is caused by almost sorted values . Myself , I am counting the sorted elements first , if they exceed a large percentage of number of all elements , then I am switching to an alternative sort , otherwise a quick sort is used . This is for a simple application . > > In an operating system , more complex algorithms may be more useful . > > > Mehmet Erol Sanliturk > > > > _______________________________________________ > freebsd-hackers@freebsd.org mailing list > https://lists.freebsd.org/mailman/listinfo/freebsd-hackers > To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org" >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5>