From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#69709: `sort` interface improvement and universal ordering predicate Date: Sat, 23 Mar 2024 19:39:51 +0200 Message-ID: References: <86zfv6uqjn.fsf@gnu.org> <4391448A-C7AF-4D7F-8866-C0313956D52D@gmail.com> <8366111E-97C4-4839-AA1E-A577C81A6035@gmail.com> <4B7ACA81-DEB9-4878-BE0B-88A302AF7081@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16822"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla Thunderbird Cc: 69709@debbugs.gnu.org, Gerd =?UTF-8?Q?M=C3=B6llmann?= , Eli Zaretskii , Stefan Monnier To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Mar 23 18:40:54 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ro5MT-0004AX-DB for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 23 Mar 2024 18:40:54 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ro5M4-00030b-2Q; Sat, 23 Mar 2024 13:40:28 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ro5Lx-0002yJ-SF for bug-gnu-emacs@gnu.org; Sat, 23 Mar 2024 13:40:23 -0400 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ro5Lx-0008BP-H7 for bug-gnu-emacs@gnu.org; Sat, 23 Mar 2024 13:40:21 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ro5Mc-0003JC-Ex for bug-gnu-emacs@gnu.org; Sat, 23 Mar 2024 13:41:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 23 Mar 2024 17:41:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 69709 X-GNU-PR-Package: emacs Original-Received: via spool by 69709-submit@debbugs.gnu.org id=B69709.171121564912681 (code B ref 69709); Sat, 23 Mar 2024 17:41:02 +0000 Original-Received: (at 69709) by debbugs.gnu.org; 23 Mar 2024 17:40:49 +0000 Original-Received: from localhost ([127.0.0.1]:42855 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ro5MO-0003IT-VF for submit@debbugs.gnu.org; Sat, 23 Mar 2024 13:40:49 -0400 Original-Received: from wout3-smtp.messagingengine.com ([64.147.123.19]:48989) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ro5ML-0003I8-0a for 69709@debbugs.gnu.org; Sat, 23 Mar 2024 13:40:47 -0400 Original-Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailout.west.internal (Postfix) with ESMTP id 860DE3200A11; Sat, 23 Mar 2024 13:39:57 -0400 (EDT) Original-Received: from mailfrontend2 ([10.202.2.163]) by compute2.internal (MEProxy); Sat, 23 Mar 2024 13:39:58 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gutov.dev; h=cc :cc:content-transfer-encoding:content-type:content-type:date :date:from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:subject:subject:to:to; s=fm3; t=1711215597; x=1711301997; bh=l5Ggg79ag8TiqSQC+pOvaerCPbtGRgFnDQJKhZrcr+8=; b= dcx8rHgv5nSVPgbeFCHgouj7Nefu/zWDW3Gvu+lyy4F6Fv3IW238kCsQ/ihXLtJn AxaazA0L2sGHsz8jLqC0V0YXMPmdEVqGj0gqdjv7mjnEcUbjM9z37yVnCFGc3UHQ TdnqjLuv3naVYRBtGYjT+45EJBz5R61o21vhbY3GPaoQnxlngtl9FgF5zPyW9Nni nGvZep0zkiaTFRWldITa+gF+W0ZHeMN4O73iiPjmKp79V4TvHq1zn8JO7I5odydj 8FlqJQ6hwkwBLqxAiJw2Kffz+hQL4QL4UJNhHGzq/d81g7mNnzWUGuxLnq5+oaEC d7cQdOFaq9y5CHXWq4OGow== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:content-type:date:date:feedback-id:feedback-id :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm2; t=1711215597; x= 1711301997; bh=l5Ggg79ag8TiqSQC+pOvaerCPbtGRgFnDQJKhZrcr+8=; b=x vTQzPPA3Gad+Rg8/X8DcpvwfJGEUsZcOlU2o9BvxiuZ4z6SXLLZ3N/pRpjUHc5FE S7+xj4nafujFQCfJK0zjsWFqTtr8JqCZZQnBFWbxEL7mC4RExtXE778UE+fLhHRM RLg35KpMfntyyDE4nyYB7HC5TBsaoeKqOmgbxxIxzjcOKls0TNRalp2Ne3nqsxV2 Xrk3MVBK3ZfmLdXnya+D7X/9VD/0n5ITAzxGB7Ulq0/GKt9+pRdNkqDXCJaYNvts jlf93Y9rUwtu85Xd0LldG6GFWkrlE1YfBIlpW6RlDrXdGufw4t2ZFp3hB1jTawq1 1ykex/a5drU2fDl7J2CEw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledruddtgedguddtgecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpefkffggfgfuvfevfhfhjggtgfesthekredttddvjeenucfhrhhomhepffhm ihhtrhihucfiuhhtohhvuceoughmihhtrhihsehguhhtohhvrdguvghvqeenucggtffrrg htthgvrhhnpeegleefteekgffhvdfhtdegveevveetteegteevgeettdehhfdukeetheff ueekkeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe gumhhithhrhiesghhuthhovhdruggvvh X-ME-Proxy: Feedback-ID: i0e71465a:Fastmail Original-Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sat, 23 Mar 2024 13:39:54 -0400 (EDT) Content-Language: en-US In-Reply-To: <4B7ACA81-DEB9-4878-BE0B-88A302AF7081@gmail.com> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:281991 Archived-At: On 23/03/2024 16:58, Mattias Engdegård wrote: > 22 mars 2024 kl. 21.55 skrev Dmitry Gutov : > >> :in-place is not too bad. > > Thank you, I'm going with :in-place because :destructive puts emphasis on the wrong aspect. Sorting in-place has predictable and useful side-effects, in contrast to the old (pre-timsort) implementation that garbled the input list. Okay. > But non-destructive should definitely be the default. All my own experience (and from observations, that of other people) shows that it's far less error-prone. This applies to other languages as well, even very imperative ones like Python. My concern is that it will make people write less performant code by default. Which will degrade unnecessarily on larger inputs (often not anticipated by the author in advance). So others will have to go around each such project, ensure the original list is "owned" and add the :in-place argument, to reach the optimum performance. That's why, I think, 'sort' is mutating in most languages. I suppose an extra copy-sequence is not that expensive, compared to most things. It's still extra garbage (meaning GC pauses sooner or later). Maybe it'll become less important with a better GC algorithm. > The branch scratch/sort-key has been updated with polished changes, including updates of the Lisp manual. > `value-less-p` is now called `value<`. (We could still unify it with `<`, perhaps.) > > A small tweak to the implementation of non-destructive list sorting gave a speed-up of 1.1x-1.5x, which was surprisingly good. The old code just called copy-sequence on the input. > > An even bigger boost was gained from special-casing the ordering predicate `value<`: 1.5x-2x speed-up on practically all input. This alone could be worth all the trouble with the patch series. We could do even better by special-casing on common key types, such as fixnums. Very nice.