From owner-freebsd-hackers@freebsd.org Sun Nov 27 12:47:47 2016 Return-Path: Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 22739C540AD for ; Sun, 27 Nov 2016 12:47:47 +0000 (UTC) (envelope-from mitchell@wyatt672earp.force9.co.uk) Received: from avasout02.plus.net (avasout02.plus.net [212.159.14.17]) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (Client CN "Bizanga Labs SMTP Client Certificate", Issuer "Bizanga Labs CA" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id B91D41044 for ; Sun, 27 Nov 2016 12:47:46 +0000 (UTC) (envelope-from mitchell@wyatt672earp.force9.co.uk) Received: from daa860.localnet ([146.90.200.236]) by avasout02 with smtp id D0kX1u00856XT2i010kYbW; Sun, 27 Nov 2016 12:44:32 +0000 X-CM-Score: 0.00 X-CNFS-Analysis: v=2.2 cv=G/5eKJs5 c=1 sm=1 tr=0 a=X4HkhBxjgj1rt5EbMA0B3g==:117 a=X4HkhBxjgj1rt5EbMA0B3g==:17 a=IkcTkHD0fZMA:10 a=MKtGQD3n3ToA:10 a=dik7HMQjudEA:10 a=ZZnuYtJkoWoA:10 a=pGLkceISAAAA:8 a=6I5d2MoRAAAA:8 a=pVDYhNIf0EFrnJ2VQR4A:9 a=GxsDny6wD0BKfkrr:21 a=FzMToYfDCPDZsbqE:21 a=QEXdDO2ut3YA:10 a=6kGIvZw6iX1k4Y-7sg4_:22 a=IjZwj45LgO3ly-622nXo:22 From: Mitchell To: freebsd-hackers@freebsd.org Subject: Re: qsort switching to insertsort Date: Sun, 27 Nov 2016 12:38:56 +0000 Message-ID: <2066156.rDbTD5n9LR@daa860> User-Agent: KMail/4.14.1 (Linux/3.16.0-4-amd64; KDE/4.14.2; x86_64; ; ) In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 27 Nov 2016 12:47:47 -0000 In "Numerical Recipes" (Press, Teukolsky, Vetterling & Flannery) the=20= Partitioning Element chosen is the median of the First, Middle & Last. = They=20 mention other techniques too. On Sunday 27 November 2016 04:17:02 Tristan Verniquet wrote: > From: Mehmet Erol Sanliturk > Sent: Sunday, 27 November 2016 5:51 AM > To: Arne Dag Fidjest=C3=B8l > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort >=20 >=20 >=20 > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l wrote: >=20 > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk =20 wrote: > > > > In quick sort , it is necessary to check worst case and switch to a= nother > > 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 met= hod . >=20 > I you sort the smaller partition recursively first, and then sort the= larger=20 partition either by tail recursion or iteration, you will only consume = O(log=20 n) of stack, so stack overflow needn=E2=80=99t be an issue, regardless = of the input. >=20 > -adf >=20 >=20 >=20 > Important problem is caused by almost sorted values . Myself , I am c= ounting=20 the sorted elements first , if they exceed a large percentage of number= of all=20 elements , then I am switching to an alternative sort , otherwise a qui= ck sort=20 is used . This is for a simple application . >=20 > In an operating system , more complex algorithms may be more useful .= >=20 >=20 > Mehmet Erol Sanliturk >=20 > --- >=20 > It can still trigger with completely unsorted data in the top and bot= tom=20 half, as long as it chooses the middle value for the pivot. The main re= ason=20 nearly sorted data is vulnerable is that it is more likely to match the= se=20 conditions, and more likely to happen in real life situations. >=20 > But this is why i don't really consider it an "edge" case, there woul= d be a=20 whole class of situations (like the one we had) where it would be very = likely=20 to trigger with very bad side effects. >=20 > Maybe, does anyone continue to use FreeBSD qsort while being aware of= this=20 implementation detail? Under what conditions/assurances? >=20 > Does anyone use FreeBSDs qsort because of this feature? >=20 > Tristan > ________________________________ > From: Mehmet Erol Sanliturk > Sent: Sunday, 27 November 2016 5:51:31 AM > To: Arne Dag Fidjest=C3=B8l > Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort >=20 >=20 >=20 > On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l=20 > wrote: >=20 > > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk=20 > wrote: > > > > In quick sort , it is necessary to check worst case and switch to a= nother > > 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 met= hod . >=20 > I you sort the smaller partition recursively first, and then sort the= larger=20 partition either by tail recursion or iteration, you will only consume = O(log=20 n) of stack, so stack overflow needn=E2=80=99t be an issue, regardless = of the input. >=20 > -adf >=20 >=20 >=20 > Important problem is caused by almost sorted values . Myself , I am c= ounting=20 the sorted elements first , if they exceed a large percentage of number= of all=20 elements , then I am switching to an alternative sort , otherwise a qui= ck sort=20 is used . This is for a simple application . >=20 > In an operating system , more complex algorithms may be more useful .= >=20 >=20 > Mehmet Erol Sanliturk >=20 >=20 >=20 > _______________________________________________ > 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"