From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: Change Emacs 'sort' API to use three-way comparison Date: Fri, 29 Aug 2014 23:51:56 +0200 Organization: Organization?!? Message-ID: <87wq9rm0ar.fsf@fencepost.gnu.org> References: <83fvgfinea.fsf@gnu.org> <5400EE70.8050207@cs.ucla.edu> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1409349168 32030 80.91.229.3 (29 Aug 2014 21:52:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 29 Aug 2014 21:52:48 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Aug 29 23:52:41 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XNU65-0003zE-FU for ged-emacs-devel@m.gmane.org; Fri, 29 Aug 2014 23:52:41 +0200 Original-Received: from localhost ([::1]:44443 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNU65-0004zX-60 for ged-emacs-devel@m.gmane.org; Fri, 29 Aug 2014 17:52:41 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:42920) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNU5m-0004zD-56 for emacs-devel@gnu.org; Fri, 29 Aug 2014 17:52:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNU5g-0003mC-2B for emacs-devel@gnu.org; Fri, 29 Aug 2014 17:52:22 -0400 Original-Received: from plane.gmane.org ([80.91.229.3]:45731) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNU5f-0003lx-RS for emacs-devel@gnu.org; Fri, 29 Aug 2014 17:52:15 -0400 Original-Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1XNU5Z-0003Zc-KW for emacs-devel@gnu.org; Fri, 29 Aug 2014 23:52:09 +0200 Original-Received: from x2f4ca08.dyn.telefonica.de ([2.244.202.8]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 29 Aug 2014 23:52:09 +0200 Original-Received: from dak by x2f4ca08.dyn.telefonica.de with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 29 Aug 2014 23:52:09 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 23 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: x2f4ca08.dyn.telefonica.de X-Face: 2FEFf>]>q>2iw=B6, xrUubRI>pR&Ml9=ao@P@i)L:\urd*t9M~y1^:+Y]'C0~{mAl`oQuAl \!3KEIp?*w`|bL5qr,H)LFO6Q=qx~iH4DN; i"; /yuIsqbLLCh/!U#X[S~(5eZ41to5f%E@'ELIi$t^ Vc\LWP@J5p^rst0+('>Er0=^1{]M9!p?&:\z]|;&=NP3AhB!B_bi^]Pfkw User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) Cancel-Lock: sha1:iqaP7JnaN29oWqemtd18mKnNKA4= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 80.91.229.3 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:173897 Archived-At: Paul Eggert writes: > One infelicity I noticed in the recent change to 'sort' in the trunk > is that the new implementation calls its predicate twice for each > comparison. This is because the Lisp API says the comparison function > returns a boolean (nil or non-nil), whereas qsort_r wants the > comparison function to return a ternary value (-1, 0, or 1). If the > predicate is expensive, the new Fsort can be twice as slow as the old. > We could tune it but I don't see how to get it any faster than 1.5x > slower than before, assuming random input and an expensive comparison > function. Can someone give an executive summary why we would be using a "qsort_r" here? "sort" sorts a list. There is really not much of a point in not using a mergesort here, resulting in a stable sort and requiring only a binary comparison function. Quicksorts make sense when sorting arrays. -- David Kastrup