From owner-freebsd-hackers@freebsd.org Sat Nov 26 12:28:37 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 3F3A7C5512B for ; Sat, 26 Nov 2016 12:28:37 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from BAY004-OMC3S26.hotmail.com (bay004-omc3s26.hotmail.com [65.54.190.164]) (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 11F40F59 for ; Sat, 26 Nov 2016 12:28:36 +0000 (UTC) (envelope-from tris_vern@hotmail.com) Received: from AUS01-SY3-obe.outbound.protection.outlook.com ([65.54.190.187]) by BAY004-OMC3S26.hotmail.com over TLS secured channel with Microsoft SMTPSVC(7.5.7601.23008); Sat, 26 Nov 2016 04:27:31 -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=2O2ChWrLvboFNLjQDj2Jw8OW2l1KjHV251Pm4VCAvkc=; b=Z6WEXsD5NThM62lE4CM88cNLzBkfKbD5MINXhmRRUaauZmrNy4iQ9s8ZMrXTYy/hYj/zWkrAZssBWMuVtRmzUk/VVBOMwQmg6uEbw/iBJ/dSxGZ0H05Nvdmj5VOdQayQpABF9qGsrWaRlTI8Pq5m6q0THEujsvU1lFsBpscamqmC2Bji7V9Ahz69BxxCPpS2sLRnW+yig6v1a/TcZTT3U5BiXR3s9kQwGiLL3/vXJr0q9L1YfR/LWlstelN0RXmV0tFFifbQubA8YeHcLCJkxzqDmpkOUt+C+xesTOgaotEjZsfAYzGgDmgWEmjIDk6Xv4LARZQWjaGHikuTjItKXA== Received: from SY3AUS01FT009.eop-AUS01.prod.protection.outlook.com (10.152.234.58) by SY3AUS01HT006.eop-AUS01.prod.protection.outlook.com (10.152.234.97) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.734.4; Sat, 26 Nov 2016 12:27:09 +0000 Received: from ME1PR01MB0546.ausprd01.prod.outlook.com (10.152.234.51) by SY3AUS01FT009.mail.protection.outlook.com (10.152.234.103) 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; Sat, 26 Nov 2016 12:27:09 +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; Sat, 26 Nov 2016 12:27:09 +0000 From: Tristan Verniquet To: Hans Petter Selasky , freebsd hackers Subject: Re: qsort switching to insertsort Thread-Topic: qsort switching to insertsort Thread-Index: AQHSR8zfjghRy3NqhkaB3zSchVE3aKDrFm4AgAAXcRo= Date: Sat, 26 Nov 2016 12:27:09 +0000 Message-ID: References: , <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> In-Reply-To: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.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:7495; Count:39 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [+5wImb4miwUI5grgp7sRocSDzhqcaUKt] x-incomingheadercount: 39 x-eopattributedmessage: 0 x-microsoft-exchange-diagnostics: 1; SY3AUS01HT006; 5:G5k3CLhTRbCGAc/1kTC36Lo7UQTj0iWx2ST/O6jn29Ln0x3QYXgkr73Vfj6Oq4k3W/W2I1vFiTSOpLYLPmN3HbOxNJb/wkH20LF8TlAB4oxOh927kVqqk0FO7sRpQb1dKfQd/L5Vrg8Nhpb1mpuzDi9QNwmyjhyQ3kXvxl4rWFk=; 24:K44oe/k8qufHkv5c9euKZ/mgtQmBU8QpVFFJvlJTJqmizjUCg2E9B/ZI/uwXNAwQ6Yr2jvxwhsvUtU5v9brezKaUchN/dIComC7eMzT+jYA=; 7:167kFFytTVSb9OOUCm9/NmlEDm59HGQiBqnn4+yFY++ZoPrIpy5J/lAYI7r7vN1VxS52bFFRdhjAUOxm/a19dRjcjTeqN829cJtdCxiTX0xfwvFrPpKiMO3310vSDChkN9Xw5nXPVS7FFOifYzcnagM0GU+7VOgBBidx90F5zm7ogJTQu32SIaNRrtED5qEC/T5ZjqfEewsOy33uvr4UD1f7X3PdYXi6BxzYJf3YFuzDB8ptti3frBIy2Omc/WaS/740QFO3xTaMNXNCASw0ARrBY7mgMHGVP4rMQQXZ1Jf1e3Z6UNNWxr+txHN8b4DRlu23XCnSUYwkCIyWh7oj5EiEwLwBSvLjMzQ6UySGAHI= x-forefront-antispam-report: EFV:NLI; SFV:NSPM; SFS:(10019020)(98900003); DIR:OUT; SFP:1102; SCL:1; SRVR:SY3AUS01HT006; H:ME1PR01MB0546.ausprd01.prod.outlook.com; FPR:; SPF:None; LANG:en; x-ms-office365-filtering-correlation-id: 92b1dd91-73ca-4a4f-7c6b-08d415f78ae9 x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(1601124038)(1603103113)(1603101340)(1601125047); SRVR:SY3AUS01HT006; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(432015012)(82015046); SRVR:SY3AUS01HT006; BCL:0; PCL:0; RULEID:; SRVR:SY3AUS01HT006; x-forefront-prvs: 0138CD935C 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: 26 Nov 2016 12:27:09.7235 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: SY3AUS01HT006 X-OriginalArrivalTime: 26 Nov 2016 12:27:32.0086 (UTC) FILETIME=[75BEF160:01D247E0] 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: Sat, 26 Nov 2016 12:28:37 -0000 > From: Hans Petter Selasky > 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=