From owner-freebsd-hackers@freebsd.org Sun Nov 27 04:18:14 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 573EEC5857D for ; Sun, 27 Nov 2016 04:18:14 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from COL004-OMC3S16.hotmail.com (col004-omc3s16.hotmail.com [65.55.34.154]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (Client CN "*.outlook.com", Issuer "Microsoft IT SSL SHA2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 0E363874 for ; Sun, 27 Nov 2016 04:18:13 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from AUS01-ME1-obe.outbound.protection.outlook.com ([65.55.34.135]) by COL004-OMC3S16.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Sat, 26 Nov 2016 20:17:07 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=U/HcDXxUdlsK22fqZyyVBebgRSLLXQi2Rc6sEOhyO2k=; b=kjIqhnHE3kUaBMGeZ+JCzevtmTs0j1YeyiPbyBSy3XdjgeSEpCh0whrCFnF2kSX8P0PF2L6cDga+fa8LqDgh0qM7A4YqfJU56HfZsA60YQjS2UCqFlmOjfqfG5y0mx2t2z5UTYTlS7Mm7AXU2Bbm9RoZsYLl29DRFcPesOQ0bH/xPkVZXE7dQHpLo9LNo5/b6s+N6uR8rDs16bVZZtBcCeESNHR/ayFo/NVh0cbYZkpbIXUBtLCji37LmoZg6fZ1/6+AOpwN1tksMdfg7e4ttcwCVQ3onpgkZ0Xy9D/aO9YgBZdaQKxE1fFxrIhWkPeg9zWf31zzDhoT9AOekRaAjA== Received: from ME1AUS01FT008.eop-AUS01.prod.protection.outlook.com (10.152.232.57) by ME1AUS01HT009.eop-AUS01.prod.protection.outlook.com (10.152.232.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.4; Sun, 27 Nov 2016 04:17:03 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com (10.152.232.58) by ME1AUS01FT008.mail.protection.outlook.com (10.152.232.117) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.4 via Frontend Transport; Sun, 27 Nov 2016 04:17:03 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com ([10.162.68.22]) by ME1PR01MB0546.ausprd01.prod.outlook.com ([10.162.68.22]) with mapi id 15.01.0734.014; Sun, 27 Nov 2016 04:17:03 +0000 From: Tristan Verniquet To: Mehmet Erol Sanliturk , =?Windows-1252?Q?Arne_Dag_Fidjest=F8l?= CC: Hans Petter Selasky , freebsd hackers Subject: Re: qsort switching to insertsort Thread-Topic: qsort switching to insertsort Thread-Index: AQHSR8zfjghRy3NqhkaB3zSchVE3aKDrFm4AgAAXcRqAACdOgIAALDUAgAAr+4CAAIhjtQ== Date: Sun, 27 Nov 2016 04:17:02 +0000 Message-ID: References: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> , In-Reply-To: Accept-Language: en-AU, en-US Content-Language: en-AU X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=none action=none header.from=hotmail.com; x-incomingtopheadermarker: OriginalChecksum:; UpperCasedChecksum:; SizeAsReceived:7938; Count:40 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [kY4N+mw+7UvRm7rvdgraOqg33M/yLZQw] x-incomingheadercount: 40 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; ME1AUS01HT009; 5:M7xHpnja/UGqgOsq5YqMnFnn7xc0oU/zqKxOUNJinzXXhijRSp7bnGvd1z09Ne09bfcl3YlCPn+au9sflPDWYML2S3ow6j3DMzNxbB8Bn6y3ayE4ScK5Pml2NUl4hb/9GPwdV5ZOlgJ9KhNAD41TxhbVY3w6OkgyFwXk5C1qC+U=; 24:omenyLVCTnGHSKJzo20GkpDp8/cUnxaEdVbJmfoaINqnCFoXQ6Wfh1bmWAakCk8EQB6Wtl4P4U1TXFE3JwSSMDwdBOYuHC5mSts2v9hv2lE=; 7:0HGKQn4yx2HQg69DgpWMr3qqmwZKzjwB6aJqtmCK9LPUKic8BWN6FXO/Z5pKUNA5prScE6QRtmShuzDQd9LH32WS64tMIL5tWu6TgOmq1oz/RzCBvSBrTpH/zkg4XYENxyjtPTW2zSIXdXYQ1aGQb/1BMVpTqCCAgdi+pavVFRYJLDo71q37D1u/mAKHGGFwqcarv75dwT5gmyhqjHBPzrvhrlExOXaX2en2UMPtsQyDs8itb4uUzXFjUYGwvTtXIncq4Rxw+JFDdWeQwqi88bbBNWukX4R4MAs6w3BVHTi72eNbVfGgDj+sxwe1xdYigyCzOf0o7Zm41NtprHMOEpcoNOTwGY4sJ4urAdl3P7A= x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900003); DIR:OUT; SFP:1102; SCL:1; SRVR:ME1AUS01HT009; H:ME1PR01MB0546.ausprd01.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: 24938fd6-753c-4951-84f1-08d4167c3dc3 x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(1601124038)(1603103113)(1603101340)(1601125047); SRVR:ME1AUS01HT009; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(432015012)(82015046); SRVR:ME1AUS01HT009; BCL:0; PCL:0; RULEID:; SRVR:ME1AUS01HT009; x-forefront-prvs: 0139052FDB spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: hotmail.com X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Nov 2016 04:17:02.6105 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: ME1AUS01HT009 X-OriginalArrivalTime: 27 Nov 2016 04:17:07.0019 (UTC) FILETIME=[1D73C9B0:01D24865] Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.23 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 04:18:14 -0000 From: Mehmet Erol Sanliturk Sent: Sunday, 27 November 2016 5:51 AM To: Arne Dag Fidjest=F8l 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=F8l wro= te: > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk = 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 large= r partition either by tail recursion or iteration, you will only consume O(= log n) of stack, so stack overflow needn=92t be an issue, regardless of the= input. -adf Important problem is caused by almost sorted values . Myself , I am countin= g the sorted elements first , if they exceed a large percentage of number o= f all elements , then I am switching to an alternative sort , otherwise a q= uick 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 ha= lf, as long as it chooses the middle value for the pivot. The main reason n= early sorted data is vulnerable is that it is more likely to match these co= nditions, 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 lik= ely 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 Sent: Sunday, 27 November 2016 5:51:31 AM To: Arne Dag Fidjest=F8l 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=F8l > wrote: > On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk > 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 large= r partition either by tail recursion or iteration, you will only consume O(= log n) of stack, so stack overflow needn=92t be an issue, regardless of the= input. -adf Important problem is caused by almost sorted values . Myself , I am countin= g the sorted elements first , if they exceed a large percentage of number o= f all elements , then I am switching to an alternative sort , otherwise a q= uick sort is used . This is for a simple application . In an operating system , more complex algorithms may be more useful . Mehmet Erol Sanliturk