From owner-freebsd-hackers@freebsd.org Sat Nov 26 14:35:55 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 2E030C56076 for ; Sat, 26 Nov 2016 14:35:55 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: from mail-yw0-x22f.google.com (mail-yw0-x22f.google.com [IPv6:2607:f8b0:4002:c05::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id DF88DE3C for ; Sat, 26 Nov 2016 14:35:54 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: by mail-yw0-x22f.google.com with SMTP id t125so82359220ywc.1 for ; Sat, 26 Nov 2016 06:35:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=ZAuQZdoIt8qkJ8pSEUDAASmO3HCWc3cd8m8Ozh46rPc=; b=XZFv+Rd4eJ6HjzxQbrU2HUPaV7Djp4j2SjRqOlV5MCoI80p9Ca66m++hTNtfgwNIW4 rloBZKCnUG7BA7bqjASd+GffsEiI2+6qe+0WR9zcCcAD5nNSvvCXErzN8SEaWCQKqncn lxts8t2nKV2l+Aq+YPMm5v1ZgTzHwqG9L9eqbvpPRd54slROsx5iA9QVyUo/QKRiIWwz b7Fa++GKrhJnZSk1YGs7+aE8npNFT9+SfRN172AoPlnCbc2qLkYimYjEanbMUr98KgQB LdK2SDBuMHwKZxXbU9V7q/pZqWs2V1LoFLH0vX3/0Zzm/01cn8K8/86b3xILYjDSE3Rp 2yEw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=ZAuQZdoIt8qkJ8pSEUDAASmO3HCWc3cd8m8Ozh46rPc=; b=ONXc3GCsFNdiP6HtFfd50WY3ZPDtCprsm+bcdCZe8SoUjg99Qq1e5EhAjWa+0f9med jDuv6xfih0ACDAL1KlawaJd98QNuGuhCP5wP5VlX56GNaWF/vxfR0Dta+Z6vXBO1VfD+ rAfNKz5u+ogb+rsfnGUok/Utxdblf84pDYTAJ1thiyZuseULZkOK5Axj3DHNnaTtE0Hl 12KDu68TIWeP0bvUMpxNUrG6qj0TvqHdrfPuknPnHb9I58sDNSt2CB2KRs7hBlXLNj9w fEk+lIp0mxfmlIRVmITnnox0DNQjerMAVG6C6QVTOAjxHNYY/JX7EX0WFk5kO3GjEuzU VxLw== X-Gm-Message-State: AKaTC01BoHUvEBKnQar/eLfyL/2seM1hDHwh9oU1vCnbWtkF8TK9Mj809YiTASphQ/DVTcDYXDwxPW1R2KqJ4A== X-Received: by 10.129.0.67 with SMTP id 64mr16033190ywa.61.1480170953978; Sat, 26 Nov 2016 06:35:53 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.170.67 with HTTP; Sat, 26 Nov 2016 06:35:53 -0800 (PST) In-Reply-To: References: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> From: Mehmet Erol Sanliturk Date: Sat, 26 Nov 2016 06:35:53 -0800 Message-ID: Subject: Re: qsort switching to insertsort To: Tristan Verniquet Cc: Hans Petter Selasky , freebsd hackers Content-Type: text/plain; charset=UTF-8 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: Sat, 26 Nov 2016 14:35:55 -0000 On Sat, Nov 26, 2016 at 4:27 AM, Tristan Verniquet wrote: > > From: Hans Petter Selasky > > Sent: Saturday, 26 November 2016 8:51 PM > > To: Tristan Verniquet; freebsd hackers > > Subject: Re: qsort switching to insertsort > > > > On 11/26/16 11:26, Tristan Verniquet wrote: > >> The easiest way forward for us is probably to comment out the offending > code. > >> > > > > Commenting out the offending code does not help. It simply leaves for > > another type of dataset to provide the same behaviour. qsort() is doomed > > in this regard. > > > > --HPS > > I can see that from, say, a security perspective, as long as a worst-case > exists 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 > two worst-case triggers as being in different ball park. I would happily > assume I'd never meet an accidental case of triggering a qsort worst-case > based 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 > example the second link shows problems with all quicksorts. But do you not > think this makes a big difference in the everyday use case where qsort > would actually be used (and not avoided)? > > Tristan > _______________________________________________ > > 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 . Mehmet Erol Sanliturk