From owner-freebsd-hackers@freebsd.org Sun Nov 27 12:51:19 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 BFEA0C5431F for ; Sun, 27 Nov 2016 12:51:19 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from SNT004-OMC4S31.hotmail.com (snt004-omc4s31.hotmail.com [65.55.90.234]) (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 6FADB12BE; Sun, 27 Nov 2016 12:51:19 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from AUS01-ME1-obe.outbound.protection.outlook.com ([65.55.90.201]) by SNT004-OMC4S31.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Sun, 27 Nov 2016 04:50:12 -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=Drar9Kf3sOsdv4ohZhsto+kMAfGOx3HIFCaY/GL7Y5A=; b=OXE/T7aVJ43hiswrn0anaWL33pkLk2UiS9Bt5gqTu6m3RQg1HwPC+CujdYKA+5rxf3XF7chBvvRyAm7xl4UqC+gYSQUWuKZ+FscRH9thwLHbYZHQKFCGNhLrVEawikCNYzdFNf9baq3vPOvUPVIg53i0anDY5qidt6+HAn26C4EAiVx7mM5DZAdLsTLF9wCAH3G9JB2yCXBDHm2NLbI1JkArwt2LMtok514kL7hOxiQUDIIwgKNJ76rdhHKsLdnGhtNT9Q8udjpQMnT+yRfukr07M9rGrzDogBMfCzZyNBlv0KBWTj4y8ckbDLOvG+SqmjNT0kGj6RDS2h9ZfY3Mbw== Received: from ME1AUS01FT008.eop-AUS01.prod.protection.outlook.com (10.152.232.55) by ME1AUS01HT004.eop-AUS01.prod.protection.outlook.com (10.152.232.123) 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 12:50:05 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com (10.152.232.52) 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 12:50:05 +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 12:50:05 +0000 From: Tristan Verniquet To: Alfred Perlstein , Mehmet Erol Sanliturk , =?iso-8859-1?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+4CAAIhjtYAALOQAgAAUvEo= Date: Sun, 27 Nov 2016 12:50:05 +0000 Message-ID: References: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> , <8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5@freebsd.org> In-Reply-To: <8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5@freebsd.org> Accept-Language: en-AU, en-US Content-Language: en-AU X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: selasky.org; dkim=none (message not signed) header.d=none;selasky.org; dmarc=none action=none header.from=hotmail.com; x-incomingtopheadermarker: OriginalChecksum:; UpperCasedChecksum:; SizeAsReceived:8111; Count:40 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [fBRa4UV4kLllTw8QbURECjL+8AhCHwYn] x-incomingheadercount: 40 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; ME1AUS01HT004; 5:rPcOO/kdygKM2/QfrrgNQg92DL7AVOitcMe8DMpbB5eJ4LmOl3to3saF8H74UmU68iyYlpJKL+sYH7GGSauvj5yVJCOjJk8gVVSrWVb/HCbHO6chBJogYAhUMnbJCBvi46Rm5b1JYvjrp783tYem2qE6J1iJZ8JQEaT8ppQ6KE4=; 24:5qw7bGvuKk2hnFCZqZ+kS88obQiXbV4pkPOByRbFoRQNTbOyrNbM3s8C7P04fYheZsQlhH6f36+7WbKou8aUpAvMA0FoMpNgdVW69WK/nyk=; 7:kl38JezTMrMNGyIfJFZlD7pY0H/jMnd3X4STPw02RWrBxMfR9s0vqdo/SzwCfEvim/Y/y9hbspg8b4HHEOpSURg0hd6IDOSpoKWG0C/dd5txtvawDuIwv0evRaca6qaLBwHrMYMXrAaWuN1/LIC4xvTQJ9I3awMlzSdTeBqklXvn+m8XN0BGKcLVHbIodLSIqxl5Vv78tyeZTDArh2JHo0q3E7nN0mpGN8i6NDonG2eNv2FY2d+dSaZ7ohJ97sUtcCG63jBNzhhh1nSMvxVFs0pdMIJQH7GF1sGpYF/1BEzspJqNDW3zwzbQAUXU90JqcNHp6WhMiIrLNBfZ2NUVUCOKLYCFyZcSf3FozmHcC3c= x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900003); DIR:OUT; SFP:1102; SCL:1; SRVR:ME1AUS01HT004; H:ME1PR01MB0546.ausprd01.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: 3fc25413-ef43-4fbf-f779-08d416c3e97a x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(1601124038)(1603103113)(1603101340)(1601125047); SRVR:ME1AUS01HT004; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(432015012)(82015046); SRVR:ME1AUS01HT004; BCL:0; PCL:0; RULEID:; SRVR:ME1AUS01HT004; x-forefront-prvs: 0139052FDB spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: hotmail.com X-MS-Exchange-CrossTenant-originalarrivaltime: 27 Nov 2016 12:50:05.5414 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: ME1AUS01HT004 X-OriginalArrivalTime: 27 Nov 2016 12:50:12.0840 (UTC) FILETIME=[CB3B4680:01D248AC] 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:51:19 -0000 > From: Alfred Perlstein > Sent: Sunday, 27 November 2016 4:40 PM > To: Tristan Verniquet; Mehmet Erol Sanliturk; Arne Dag Fidjest=F8l > Cc: Hans Petter Selasky; freebsd hackers > Subject: Re: qsort switching to insertsort > =A0 =20 > A couple notes: >=20 > 1) It's interesting to me that it's based on a simple heuristic as=20 > opposed to also checking the depth of the recursion within the qsort=20 > itself. >=20 > 2) Wondering if upon detection of this situation it might even be faster= =20 > to perform some randomization (shuffle) of the data and then retry. >=20 > 3) Wondering if there could be a way to return an error and indicate the= =20 > data is unsorted if the corner case is hit allowing the caller to make a= =20 > choice at that point.=A0 Obviously the API would need to be changed. >=20 > I haven't thought too hard on this. Note that the functionalilty in question is a special-case test which has b= een bolted on to the side. Nothing much is really lost by removing it, whic= h according to my first link is what NetBSD has done. I don't think we'll g= et far discussing how to "fix" it as tempting as that is - probably better = left for a very in depth studious well tested effort.. The qsort.c file is only 200 odd lines long. I highly recommend reading it = to see what I mean (ie the case if swap_cnt =3D=3D 0). (The special-case is to turn sorting sorted data from O(nlogn) to O(n), but= exposes a whole new set of average-case O(n^2) cases) > > One thing to keep in mind: Using qsort in a codepath has "deadlines" or=20 > other deterministic needs is not going to work out well.=A0 It's better t= o=20 > use a sort with a known complexity with an upper bound than something=20 > that can be defeated by a pathological input data set. >=20 > -Alfred I guess I have the same comment/question as I do for Hans Petter Selasky's = response. In the cases where qsort would actually be used, don't you think the much h= igher likelyhood of triggering the insertsort worst case especially with so= me types of data makes a big difference? Maybe, I see the insertsort case as similar (though obviously not as likely= to be hit) as the "choose the last element" pivot selection which sorts O(= n^2) on sorted data. If users need to expect O(n^2) anyway, why not keep th= e last element pivot selection? Instead, a pretty good effort has been made= to make sure bad pivots won't be chosen with normal data. That is undermin= ed slightly with the insertsort switch imho. Tristan =