From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 00:00:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 54532@debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.16479935833343 (code B ref -1); Wed, 23 Mar 2022 00:00:02 +0000 Received: (at submit) by debbugs.gnu.org; 22 Mar 2022 23:59:43 +0000 Received: from localhost ([127.0.0.1]:42105 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nWoPZ-0000rl-Cv for submit@debbugs.gnu.org; Tue, 22 Mar 2022 19:59:43 -0400 Received: from lists.gnu.org ([209.51.188.17]:34294) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nWoPW-0000rb-19 for submit@debbugs.gnu.org; Tue, 22 Mar 2022 19:59:36 -0400 Received: from eggs.gnu.org ([209.51.188.92]:45150) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nWoPV-0003SX-OA for bug-gnu-emacs@gnu.org; Tue, 22 Mar 2022 19:59:33 -0400 Received: from mail-tycjpn01on2100.outbound.protection.outlook.com ([40.107.114.100]:63236 helo=JPN01-TYC-obe.outbound.protection.outlook.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nWoPP-0005F5-AT for bug-gnu-emacs@gnu.org; Tue, 22 Mar 2022 19:59:32 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=bXMtD6J2OCUyKVXixmi/zeyzb1u0DO6y6mY3Yuww3BZFELMDBEuBzawvxPnaRhRXxHf/xJ5fDQABFTs8Hqgh77wD7gQ2VgrM/aKOh9/w8YYHAUM/db/MHbu7bwyfnvsMDIBkBiISBa6FUOr4pbvv7qgNGnFc5xPwqwB5vzJUVGnC6njTcU+dL/9PKrGcg3YEEINmmk598IlFhA+Rzpf+8g8LUZv0sE6IRt6NPuKY9mfZ8G6h/xQNflISAPUT+XYa1dWqOHA68cs0BkwXSmlqKwdGMwICPAcXz25DJeBfTEu+voLBK2rDo645i1xjx9G6vOI3SxYSa12W2zXMGvk2Aw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=u1F/Eaf00zZ8EW8iHfbGPaAeklYH9lZMzRplTRKR1Sc=; b=Tyw8qkz07t2HhAE7lA5GP1QQQIEe1+9DWa/AzTw4kKd/Gknhjyhdlregh5J1n0o6FKXXmXAI1G1047HrUF/gqT1JSCkwqyXZPY7XyJUHykJSDAodtb8o37d97HguktjSQ/+KQAV/qJokgAQ2QWy9iza7rI7mK+7x4ETBh6w/mr1L/NFvqpCeOA5WkGiXDx5CWg42Hsu/voddIh40Yw3v/M3t843bNZIZG7FUgzwKMs8S/DL9458/hU7BjmdHrvFrruzxGtq0h6Xl3NDPGQNhHlQ4yxpTJDFh58blmqVIHP/l8iz/tacGGMox0eIfnU8hmh/IBL3NH0s1vR2BYIQfxA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=u1F/Eaf00zZ8EW8iHfbGPaAeklYH9lZMzRplTRKR1Sc=; b=OcS716RrSnm9Q4dtRYOnkczdk1OI1z9mIqTNbGnXRkKG31LOIEsmt19wcR2Stkh5Obg8EtsxjnIAoONzt8jirVHl6SvxHzdMl4KxrphJvL1r5WzZ0e/QZejwxPW9TpRm1HQyAPCu5iIpSV8iOVHK/KAUgE5c04xDsRrqmycfWDU0gdijaJ480BqFOgZ+DU09RFfHLQ4tfDuYZZz+3JRbb5i0wrm2d+eSFZ875dNq5E8LawBL7apQlfc+H9BEWBjIAYwEk5/TOQD3iaw0/lZ4Hap5isSqHdqLD0rnjMV5u4rILlGs7VW+B+OrmUYKj9U189OmiC1PWV2JZGCtPBhCrw== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by OSZP286MB1275.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:136::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.16; Tue, 22 Mar 2022 23:59:21 +0000 Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717%4]) with mapi id 15.20.5081.023; Tue, 22 Mar 2022 23:59:21 +0000 From: Andrew Cohen Date: Wed, 23 Mar 2022 07:59:11 +0800 Message-ID: <87k0clr12o.fsf@ust.hk> Content-Type: multipart/mixed; boundary="=-=-=" X-ClientProxiedBy: HK2PR0401CA0024.apcprd04.prod.outlook.com (2603:1096:202:2::34) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: a34c0ed6-1236-4ee3-cec0-08da0c5ffae9 X-MS-TrafficTypeDiagnostic: OSZP286MB1275:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: Il9+0BiwQDnKme7a6wZRUUTrS8G80ITCblv3wyPKI2atHP9hgr6ccar2QK9n1izq3QnD8LWQFig+rm6wak4oCqHzW8jWjmkm8ZkxEqS2rXrQppCTVZt2Lu+81B5ibk91MPEM2rCouppf1iWSFpATcB5HdlWOoczI2zKMNFF8EkvZx5BFzna8PYhELlL60YS3XARlqjHwrf1UkkoOo4oxsGViC2sIAxAj3b82J5fWEgTJKqTJhfHeahbdcrjXNBQH67BenJInxN3mU8PPaPVfbN70a4jxYUQ9KrMngfrzqIj18a/WS0mAJXAbjGFz6glQUCxsyxTdgcqqe0tzQEIFX/sTYNRCL2qlZItfoPPYdgvtnhhj8d/xGHkJserYNQKP5U2g+94/BDdSsfjJSy5JPdxfXybzdRj8aOFR3++rxEb5LfSKuhneBqcWLFusO+43eYmupNUlnMGXJAI5ymtAW5hemKOzO4micnixrHO6QHRNDzBzffBoJHD/wSrRL0CfDxKsaVU2yPxws7JsMQOeSlvpw8OGiCdQzxZOHYSmpjPFgfjvzH9DlYELg0vE2a9PtYi/1IX87mTiM2MReSNKzYcW1l5NcbswIcOLTIJocbne/RH88KlEP8e04qaNOi5HL5OlIEBHEEqEtFyPCZcH5Q== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(6916009)(235185007)(8936002)(316002)(786003)(83380400001)(66556008)(8676002)(66476007)(38100700002)(508600001)(2616005)(26005)(186003)(86362001)(33964004)(6666004)(5660300002)(6512007)(6486002)(6506007)(2906002)(66946007)(66574015)(36756003); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: i1YOWkxZ2jEozpymxuQteEOB0D+iIN9YyCu9Oo3d5lGKeqljLe9RVFBT2G2YF/gr4jSK/3syW5QMoGkBO887qKifon8NrJeL5E7QMdhQt6E8A3GkCsyNuv4HaXOuaIND9Ufh1zprFmm1h0H8NBFgizhss/siJzeN/sOGp5bPNhcY7UJRAyJBWnHGHzN0CvDFpbfytS3fAEZ9Yki6b8sxRD3fCIIV2GbJn8bIoif9qOeGjktc01DQ1Ewbr10VnAS8dCMqS+iNgiBOP1/WxbRVJtUEUG+W3c0PYLsV/qpP0OkYAJcUF+cy1ldJ4qRrJrNifJzkZrFMD0yYkMk48dWn1C4tqVJCE32qZimW5zKQBbi08KVNCAgYXTR9Ah2vuz6KNC9guTN1UJwadvBRQt12jt3fKTvkcPFiYVfO8J0ckZ0Sp19lEU7yvSa3T6G5vlS6lMAKKxDTZoUfr8R2yEsh9cCgO4JK8q2a3pDo6UAFJ8aoYGdseSoM2HETp0eD/0RrSos0EM1gZHOzWC2Div9Yt2lO3kNEV+WDYmFmo/qtIKw+a1FP6h+Vxo3A5c8MWmCM/Q9cMvRog5H+/38APEmu9eosM1CUfH0fBjKBNwdR4NK9P95STDTnvFQNGfehjmRoXPJ+qEjS11RV58XFS0VwTKBlePVCsUbvG2Z5Fe++8kFIoIyGnRLtEo3W5TGC99OLEpJuolYCfIrL2OZpbO8IvEG7RmgBWUIXbp1lXQW2jhGmOKO2D2xRYRyccYDtW0wDN1asdOhJsXn0sIZUJzNolGD9PGhS8PRE73WiAQbgN/Wm1iFGn4FomyrbNF9JliODOqJPHrRlS617TY9vgB79+zWJhzsSemnDKPPpp++6cn9BgbsqJ4lgBxCyLut9/BdQjvcToxjkclYHebrfCCnpXpJt21iEKoBrQGmiNbK4cO3ZEIdHWe3yZXMkDz4IAC0rEAQzQns/NiEtfz8zzQIjksSdnFZROJ7mhUbHvoAf7bCGGwODsIK9m5MXux1Pn/3soBUiRtuaAhwhRxKsgI3N6R5JAq/81mbMoghn68DEsCvbw3B8yeXePp0khBxmvkvN+FEXhUpU7VVYRuTTciVLdollHn6lpF+djDY8FC3h7EyIlPq0PZrCaDVyK/wvdohTf/BPhnZ06PFPbgRulE9uOCvig8B/uaYeRl3WHWpTyRrDjQ9Dji0PV05z/J7ekKIACi1Pr6Rr0jdIwGn6FwzbfdDNde8VdT2jTp9I46C8piRb2eY7gLP12+QjnNCEvSBvjHh8xAWwsfeowAS97XyanmWJJ4ZQyt1jDZR/tWuKae7JuUdGrQa9spg1TNZXXxo8F124vlNs+yPmsRLz1FegXpIDHH4ZQDCsaPQeG1Y3s6nSZ1aCTushLGHV0auojAZfc7KE+59N/IN9FlZuw71bnbJFL7nyqjIZbh2MWflAe5kdsVElUvmtPjxYhCraJUog X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: a34c0ed6-1236-4ee3-cec0-08da0c5ffae9 X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 22 Mar 2022 23:59:21.2230 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: X4g28ttKyLv3yURXNmmJ6XXVUaIPKM/yxLcc21Z1kMPL7TivYIsiFCNuGslR+S+h X-MS-Exchange-Transport-CrossTenantHeadersStamped: OSZP286MB1275 Received-SPF: pass client-ip=40.107.114.100; envelope-from=acohen@ust.hk; helo=JPN01-TYC-obe.outbound.protection.outlook.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Tags: patch As discussed on emacs-devel I have been working on a replacement for the current sorting algorithm in Emacs. With the help of Mattias Engdeg=C3=A5rd we have made a lot of progress, and the attached patch implements TIMSORT, the sorting algorithm introduced 20 years ago in python and now used in Android and many other places. This implementation is pretty much always 20% to 30% faster than the current version, and in many cases is an order of magnitude faster. The current Emacs code treats lists and vectors differently, while the new implementation uses a common code path. Some benchmarks (times in microseconds; all lists are length 10K): | | oldlist | oldvec | tim | | (make-random-list 10000) | 2790 | 2123 | 1557 | | (nreverse (make-sorted-list 10000)) | 1417 | 987 | 118 | | (make-sorted-list 10000) | 1310 | 899 | 116 | | (make-swapped-list 10000 3) | 1457 | 1019 | 122 | | (make-plus-list 10000) | 1309 | 899 | 119 | | (make-onepercent-list 10000) | 1764 | 1272 | 183 | | (make-constant-list 10000) | 1292 | 888 | 116 | | (make-evil-list 10000) | 1374 | 946 | 398 | | (make-block-list 10000 100) | 2235 | 1646 | 919 | | (make-block-list 10000 10) | 2598 | 1962 | 1451 | The patch has 4 parts: 1. Add a new `record_unwind_protect_ptr_mark` function for use with C data structures that use the specpdl for clean-up but also contain possibly unique references to Lisp objects. This is needed for the dynamic memory management that the new algorithm uses. 2. The actual sorting change. This removes the old sorting routines and puts the new implementation in a separate file, sort.c 3. A bunch of new unit tests. 4. An optimization that resolves the sorting comparison symbol into the corresponding function before starting the sort. In GNU Emacs 29.0.50 (build 5, x86_64-pc-linux-gnu, GTK+ Version 3.24.33, c= airo version 1.16.0) of 2022-03-22 built on clove Repository revision: c3c1ee56a44541e1eb2fd7e523f7508fd330d635 Repository branch: scratch/local System Description: Debian GNU/Linux bookworm/sid Configured using: 'configure --with-x-toolkit=3Dgtk3 --with-native-compilation --with-pgtk --with-xwidgets' --=-=-= Content-Type: text/patch Content-Disposition: attachment; filename=patch.diff >From daf46703ce83cc652667e89aa50161a36e9a8575 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= Date: Sat, 5 Mar 2022 11:12:54 +0100 Subject: [PATCH 1/4] Add optional GC marking function to specpdl unwind_ptr record Add a new `record_unwind_protect_ptr_mark` function for use with C data structures that use the specpdl for clean-up but also contain possibly unique references to Lisp objects. * src/eval.c (record_unwind_protect_ptr_mark): New. (record_unwind_protect_module, set_unwind_protect_ptr): Set the mark function to NULL. (mark_specpdl): Call the mark function if present. * src/lisp.h (unwind_ptr): Add a mark function pointer to the SPECPDL_UNWIND_PTR case. --- src/eval.c | 20 ++++++++++++++++++++ src/lisp.h | 5 ++++- 2 files changed, 24 insertions(+), 1 deletion(-) diff --git a/src/eval.c b/src/eval.c index 294d79e67a..593cbaba98 100644 --- a/src/eval.c +++ b/src/eval.c @@ -3612,6 +3612,20 @@ record_unwind_protect_ptr (void (*function) (void *), void *arg) specpdl_ptr->unwind_ptr.kind = SPECPDL_UNWIND_PTR; specpdl_ptr->unwind_ptr.func = function; specpdl_ptr->unwind_ptr.arg = arg; + specpdl_ptr->unwind_ptr.mark = NULL; + grow_specpdl (); +} + +/* Like `record_unwind_protect_ptr', but also specifies a function + for GC-marking Lisp objects only reachable through ARG. */ +void +record_unwind_protect_ptr_mark (void (*function) (void *), void *arg, + void (*mark) (void *)) +{ + specpdl_ptr->unwind_ptr.kind = SPECPDL_UNWIND_PTR; + specpdl_ptr->unwind_ptr.func = function; + specpdl_ptr->unwind_ptr.arg = arg; + specpdl_ptr->unwind_ptr.mark = mark; grow_specpdl (); } @@ -3655,6 +3669,7 @@ record_unwind_protect_module (enum specbind_tag kind, void *ptr) specpdl_ptr->kind = kind; specpdl_ptr->unwind_ptr.func = NULL; specpdl_ptr->unwind_ptr.arg = ptr; + specpdl_ptr->unwind_ptr.mark = NULL; grow_specpdl (); } @@ -3783,6 +3798,7 @@ set_unwind_protect_ptr (specpdl_ref count, void (*func) (void *), void *arg) p->unwind_ptr.kind = SPECPDL_UNWIND_PTR; p->unwind_ptr.func = func; p->unwind_ptr.arg = arg; + p->unwind_ptr.mark = NULL; } /* Pop and execute entries from the unwind-protect stack until the @@ -4216,6 +4232,10 @@ mark_specpdl (union specbinding *first, union specbinding *ptr) break; case SPECPDL_UNWIND_PTR: + if (pdl->unwind_ptr.mark) + pdl->unwind_ptr.mark (pdl->unwind_ptr.arg); + break; + case SPECPDL_UNWIND_INT: case SPECPDL_UNWIND_INTMAX: case SPECPDL_UNWIND_VOID: diff --git a/src/lisp.h b/src/lisp.h index deeca9bc86..315fb03fe6 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -3313,8 +3313,9 @@ #define DEFVAR_KBOARD(lname, vname, doc) \ } unwind_array; struct { ENUM_BF (specbind_tag) kind : CHAR_BIT; - void (*func) (void *); + void (*func) (void *); /* Unwind function. */ void *arg; + void (*mark) (void *); /* GC mark function (if non-null). */ } unwind_ptr; struct { ENUM_BF (specbind_tag) kind : CHAR_BIT; @@ -4440,6 +4441,8 @@ xsignal (Lisp_Object error_symbol, Lisp_Object data) extern void record_unwind_protect (void (*) (Lisp_Object), Lisp_Object); extern void record_unwind_protect_array (Lisp_Object *, ptrdiff_t); extern void record_unwind_protect_ptr (void (*) (void *), void *); +extern void record_unwind_protect_ptr_mark (void (*function) (void *), + void *arg, void (*mark) (void *)); extern void record_unwind_protect_int (void (*) (int), int); extern void record_unwind_protect_intmax (void (*) (intmax_t), intmax_t); extern void record_unwind_protect_void (void (*) (void)); -- 2.34.1.575.g55b058a8bb >From d31e7628dfeb111f201161f1363a909123c14a43 Mon Sep 17 00:00:00 2001 From: Andrew G Cohen Date: Thu, 10 Mar 2022 09:30:00 +0800 Subject: [PATCH 2/4] Replace list and vector sorting with TIMSORT algorithm * src/Makefile.in (base_obj): Add sort.o. * src/deps.mk (fns.o): Add sort.c. * src/lisp.h: Add prototypes for inorder, tim_sort. * src/sort.c: New file providing tim_sort. * src/fns.c: Remove prototypes for removed routines. (merge_vectors, sort_vector_inplace, sort_vector_copy): Remove. (sort_list, sort_vector): Use tim_sort. --- src/Makefile.in | 2 +- src/deps.mk | 2 +- src/fns.c | 129 ++----- src/lisp.h | 3 + src/sort.c | 961 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 996 insertions(+), 101 deletions(-) create mode 100644 src/sort.c diff --git a/src/Makefile.in b/src/Makefile.in index 3353fb16d7..e0f18dc352 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -427,7 +427,7 @@ base_obj = minibuf.o fileio.o dired.o \ cmds.o casetab.o casefiddle.o indent.o search.o regex-emacs.o undo.o \ alloc.o pdumper.o data.o doc.o editfns.o callint.o \ - eval.o floatfns.o fns.o font.o print.o lread.o $(MODULES_OBJ) \ + eval.o floatfns.o fns.o sort.o font.o print.o lread.o $(MODULES_OBJ) \ syntax.o $(UNEXEC_OBJ) bytecode.o comp.o $(DYNLIB_OBJ) \ process.o gnutls.o callproc.o \ region-cache.o sound.o timefns.o atimer.o \ diff --git a/src/deps.mk b/src/deps.mk index deffab93ec..39edd5c1dd 100644 --- a/src/deps.mk +++ b/src/deps.mk @@ -279,7 +279,7 @@ eval.o: dispextern.h lisp.h globals.h $(config_h) coding.h composite.h xterm.h \ msdos.h floatfns.o: floatfns.c syssignal.h lisp.h globals.h $(config_h) -fns.o: fns.c commands.h lisp.h $(config_h) frame.h buffer.h character.h \ +fns.o: fns.c sort.c commands.h lisp.h $(config_h) frame.h buffer.h character.h \ keyboard.h keymap.h window.h $(INTERVALS_H) coding.h ../lib/md5.h \ ../lib/sha1.h ../lib/sha256.h ../lib/sha512.h blockinput.h atimer.h \ systime.h xterm.h ../lib/unistd.h globals.h diff --git a/src/fns.c b/src/fns.c index 06a6456380..a064e02eac 100644 --- a/src/fns.c +++ b/src/fns.c @@ -39,9 +39,6 @@ Copyright (C) 1985-1987, 1993-1995, 1997-2022 Free Software Foundation, #include "puresize.h" #include "gnutls.h" -static void sort_vector_copy (Lisp_Object pred, ptrdiff_t len, - Lisp_Object src[restrict VLA_ELEMS (len)], - Lisp_Object dest[restrict VLA_ELEMS (len)]); enum equal_kind { EQUAL_NO_QUIT, EQUAL_PLAIN, EQUAL_INCLUDING_PROPERTIES }; static bool internal_equal (Lisp_Object, Lisp_Object, enum equal_kind, int, Lisp_Object); @@ -2166,8 +2163,11 @@ DEFUN ("reverse", Freverse, Sreverse, 1, 1, 0, return new; } -/* Sort LIST using PREDICATE, preserving original order of elements - considered as equal. */ + +/* Stably sort LIST using PREDICATE. This converts the list to a + vector, sorts the vector using the TIMSORT algorithm, and returns + the result converted back to a list. The input list is + destructively reused to hold the sorted result.*/ static Lisp_Object sort_list (Lisp_Object list, Lisp_Object predicate) @@ -2175,112 +2175,43 @@ sort_list (Lisp_Object list, Lisp_Object predicate) ptrdiff_t length = list_length (list); if (length < 2) return list; - - Lisp_Object tem = Fnthcdr (make_fixnum (length / 2 - 1), list); - Lisp_Object back = Fcdr (tem); - Fsetcdr (tem, Qnil); - - return merge (Fsort (list, predicate), Fsort (back, predicate), predicate); -} - -/* Using PRED to compare, return whether A and B are in order. - Compare stably when A appeared before B in the input. */ -static bool -inorder (Lisp_Object pred, Lisp_Object a, Lisp_Object b) -{ - return NILP (call2 (pred, b, a)); -} - -/* Using PRED to compare, merge from ALEN-length A and BLEN-length B - into DEST. Argument arrays must be nonempty and must not overlap, - except that B might be the last part of DEST. */ -static void -merge_vectors (Lisp_Object pred, - ptrdiff_t alen, Lisp_Object const a[restrict VLA_ELEMS (alen)], - ptrdiff_t blen, Lisp_Object const b[VLA_ELEMS (blen)], - Lisp_Object dest[VLA_ELEMS (alen + blen)]) -{ - eassume (0 < alen && 0 < blen); - Lisp_Object const *alim = a + alen; - Lisp_Object const *blim = b + blen; - - while (true) + else { - if (inorder (pred, a[0], b[0])) + Lisp_Object *result; + USE_SAFE_ALLOCA; + SAFE_ALLOCA_LISP (result, length); + Lisp_Object tail = list; + for (ptrdiff_t i = 0; i < length; i++) { - *dest++ = *a++; - if (a == alim) - { - if (dest != b) - memcpy (dest, b, (blim - b) * sizeof *dest); - return; - } + result[i] = Fcar (tail); + tail = XCDR (tail); } - else + tim_sort (predicate, result, length); + + ptrdiff_t i = 0; + tail = list; + while (CONSP (tail)) { - *dest++ = *b++; - if (b == blim) - { - memcpy (dest, a, (alim - a) * sizeof *dest); - return; - } + XSETCAR (tail, result[i]); + tail = XCDR (tail); + i++; } + SAFE_FREE (); + return list; } } -/* Using PRED to compare, sort LEN-length VEC in place, using TMP for - temporary storage. LEN must be at least 2. */ -static void -sort_vector_inplace (Lisp_Object pred, ptrdiff_t len, - Lisp_Object vec[restrict VLA_ELEMS (len)], - Lisp_Object tmp[restrict VLA_ELEMS (len >> 1)]) -{ - eassume (2 <= len); - ptrdiff_t halflen = len >> 1; - sort_vector_copy (pred, halflen, vec, tmp); - if (1 < len - halflen) - sort_vector_inplace (pred, len - halflen, vec + halflen, vec); - merge_vectors (pred, halflen, tmp, len - halflen, vec + halflen, vec); -} - -/* Using PRED to compare, sort from LEN-length SRC into DST. - Len must be positive. */ -static void -sort_vector_copy (Lisp_Object pred, ptrdiff_t len, - Lisp_Object src[restrict VLA_ELEMS (len)], - Lisp_Object dest[restrict VLA_ELEMS (len)]) -{ - eassume (0 < len); - ptrdiff_t halflen = len >> 1; - if (halflen < 1) - dest[0] = src[0]; - else - { - if (1 < halflen) - sort_vector_inplace (pred, halflen, src, dest); - if (1 < len - halflen) - sort_vector_inplace (pred, len - halflen, src + halflen, dest); - merge_vectors (pred, halflen, src, len - halflen, src + halflen, dest); - } -} - -/* Sort VECTOR in place using PREDICATE, preserving original order of - elements considered as equal. */ +/* Stably sort VECTOR ordered by PREDICATE using the TIMSORT + algorithm. */ static void sort_vector (Lisp_Object vector, Lisp_Object predicate) { - ptrdiff_t len = ASIZE (vector); - if (len < 2) + ptrdiff_t length = ASIZE (vector); + if (length < 2) return; - ptrdiff_t halflen = len >> 1; - Lisp_Object *tmp; - USE_SAFE_ALLOCA; - SAFE_ALLOCA_LISP (tmp, halflen); - for (ptrdiff_t i = 0; i < halflen; i++) - tmp[i] = make_fixnum (0); - sort_vector_inplace (predicate, len, XVECTOR (vector)->contents, tmp); - SAFE_FREE (); + + tim_sort (predicate, XVECTOR (vector)->contents, length); } DEFUN ("sort", Fsort, Ssort, 2, 2, 0, @@ -2326,7 +2257,7 @@ merge (Lisp_Object org_l1, Lisp_Object org_l2, Lisp_Object pred) } Lisp_Object tem; - if (inorder (pred, Fcar (l1), Fcar (l2))) + if (!NILP (call2 (pred, Fcar (l1), Fcar (l2)))) { tem = l1; l1 = Fcdr (l1); diff --git a/src/lisp.h b/src/lisp.h index 315fb03fe6..3801aeec3d 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -3903,6 +3903,9 @@ #define CONS_TO_INTEGER(cons, type, var) \ extern Lisp_Object string_make_unibyte (Lisp_Object); extern void syms_of_fns (void); +/* Defined in sort.c */ +extern void tim_sort (Lisp_Object, Lisp_Object *, const ptrdiff_t); + /* Defined in floatfns.c. */ verify (FLT_RADIX == 2 || FLT_RADIX == 16); enum { LOG2_FLT_RADIX = FLT_RADIX == 2 ? 1 : 4 }; diff --git a/src/sort.c b/src/sort.c new file mode 100644 index 0000000000..e7ccc1c052 --- /dev/null +++ b/src/sort.c @@ -0,0 +1,961 @@ +/* Timsort for sequences. + +Copyright (C) 2022 Free Software Foundation, Inc. + +This file is part of GNU Emacs. + +GNU Emacs is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or (at +your option) any later version. + +GNU Emacs is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Emacs. If not, see . */ + +/* This is a version of the cpython code implementing the TIMSORT + sorting algorithm described in + https://github.com/python/cpython/blob/main/Objects/listsort.txt. + This algorithm identifies and pushes naturally ordered sublists of + the original list, or "runs", onto a stack, and merges them + periodically according to a merge strategy called "powersort". + State is maintained during the sort in a merge_state structure, + which is passed around as an argument to all the subroutines. A + "stretch" structure includes a pointer to the run BASE of length + LEN along with its POWER (a computed integer used by the powersort + merge strategy that depends on this run and the succeeding run.) */ + + +#include +#include "lisp.h" + + +/* MAX_MERGE_PENDING is the maximum number of entries in merge_state's + pending-stretch stack. For a list with n elements, this needs at most + floor(log2(n)) + 1 entries even if we didn't force runs to a + minimal length. So the number of bits in a ptrdiff_t is plenty large + enough for all cases. */ + +#define MAX_MERGE_PENDING (sizeof (ptrdiff_t) * 8) + +/* Once we get into galloping mode, we stay there as long as both runs + win at least GALLOP_WIN_MIN consecutive times. */ + +#define GALLOP_WIN_MIN 7 + +/* A small temp array of size MERGESTATE_TEMP_SIZE is used to avoid + malloc when merging small lists. */ + +#define MERGESTATE_TEMP_SIZE 256 + +struct stretch +{ + Lisp_Object *base; + ptrdiff_t len; + int power; +}; + +struct reloc +{ + Lisp_Object **src; + Lisp_Object **dst; + ptrdiff_t *size; + int order; /* -1 while in merge_lo; +1 while in merg_hi; 0 otherwise. */ +}; + + +typedef struct +{ + Lisp_Object *listbase; + ptrdiff_t listlen; + + /* PENDING is a stack of N pending stretches yet to be merged. + Stretch #i starts at address base[i] and extends for len[i] + elements. */ + + int n; + struct stretch pending[MAX_MERGE_PENDING]; + + /* The variable MIN_GALLOP, initialized to GALLOP_WIN_MIN, controls + when we get *into* galloping mode. merge_lo and merge_hi tend to + nudge it higher for random data, and lower for highly structured + data. */ + + ptrdiff_t min_gallop; + + /* 'A' is temporary storage, able to hold ALLOCED elements, to help + with merges. 'A' initially points to TEMPARRAY, and subsequently + to newly allocated memory if needed. */ + + Lisp_Object *a; + ptrdiff_t alloced; + specpdl_ref count; + Lisp_Object temparray[MERGESTATE_TEMP_SIZE]; + + /* If an exception is thrown while merging we might have to relocate + some list elements from temporary storage back into the list. + RELOC keeps track of the information needed to do this. */ + + struct reloc reloc; + + /* PREDICATE is the lisp comparison predicate for the sort. */ + + Lisp_Object predicate; +} merge_state; + + +/* INORDER returns true iff (PREDICATE A B) is non-nil. */ + +static inline bool +inorder (const Lisp_Object predicate, const Lisp_Object a, const Lisp_Object b) +{ + return !NILP (call2 (predicate, a, b)); +} + + +/* BINARYSORT() is a stable binary insertion sort used for sorting the + list starting at LO and ending at HI. On entry, LO <= START <= HI, + and [LO, START) is already sorted (pass START == LO if you don't + know!). Even in case of error, the output slice will be some + permutation of the input (nothing is lost or duplicated). */ + +static void +binarysort (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, + Lisp_Object *start) +{ + Lisp_Object pred = ms->predicate; + + eassume (lo <= start && start <= hi); + if (lo == start) + ++start; + for (; start < hi; ++start) + { + Lisp_Object *l = lo; + Lisp_Object *r = start; + Lisp_Object pivot = *r; + + eassume (l < r); + do { + Lisp_Object *p = l + ((r - l) >> 1); + if (inorder (pred, pivot, *p)) + r = p; + else + l = p + 1; + } while (l < r); + eassume (l == r); + for (Lisp_Object *p = start; p > l; --p) + p[0] = p[-1]; + *l = pivot; + } +} + + +/* COUNT_RUN() returns the length of the run beginning at LO, in the + slice [LO, HI) with LO < HI. A "run" is the longest + non-decreasing sequence or the longest strictly decreasing + sequence, with the Boolean *DESCENDING set to 0 in the former + case, or to 1 in the latter. The strictness of the definition of + "descending" is needed so that the caller can safely reverse a + descending sequence without violating stability (strict > ensures + there are no equal elements to get out of order). */ + +static ptrdiff_t +count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descending) +{ + Lisp_Object pred = ms->predicate; + + eassume (lo < hi); + *descending = 0; + ++lo; + ptrdiff_t n = 1; + if (lo == hi) + return n; + + n = 2; + if (inorder (pred, lo[0], lo[-1])) + { + *descending = 1; + for (lo = lo + 1; lo < hi; ++lo, ++n) + { + if (!inorder (pred, lo[0], lo[-1])) + break; + } + } + else + { + for (lo = lo + 1; lo < hi; ++lo, ++n) + { + if (inorder (pred, lo[0], lo[-1])) + break; + } + } + + return n; +} + + +/* GALLOP_LEFT() locates the proper position of KEY in a sorted + vector: if the vector contains an element equal to KEY, return the + position immediately to the left of the leftmost equal element. + [GALLOP_RIGHT() does the same except returns the position to the + right of the rightmost equal element (if any).] + + 'A' is a sorted vector with N elements, starting at A[0]. N must be > 0. + + HINT is an index at which to begin the search, 0 <= HINT < N. The closer + HINT is to the final result, the faster this runs. + + The return value is the int k in [0, N] such that + + A[k-1] < KEY <= a[k] + + pretending that *(A-1) is minus infinity and A[N] is plus infinity. IOW, + KEY belongs at index k; or, IOW, the first k elements of A should precede + KEY, and the last N-k should follow KEY. */ + +static ptrdiff_t +gallop_left (merge_state *ms, const Lisp_Object key, Lisp_Object *a, + const ptrdiff_t n, const ptrdiff_t hint) +{ + Lisp_Object pred = ms->predicate; + + eassume (a && n > 0 && hint >= 0 && hint < n); + + a += hint; + ptrdiff_t lastofs = 0; + ptrdiff_t ofs = 1; + if (inorder (pred, *a, key)) + { + /* When a[hint] < key, gallop right until + a[hint + lastofs] < key <= a[hint + ofs]. */ + const ptrdiff_t maxofs = n - hint; /* This is one after the end of a. */ + while (ofs < maxofs) + { + if (inorder (pred, a[ofs], key)) + { + lastofs = ofs; + eassume (ofs <= (PTRDIFF_MAX - 1) / 2); + ofs = (ofs << 1) + 1; + } + else + break; /* Here key <= a[hint+ofs]. */ + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to offsets relative to &a[0]. */ + lastofs += hint; + ofs += hint; + } + else + { + /* When key <= a[hint], gallop left, until + a[hint - ofs] < key <= a[hint - lastofs]. */ + const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ + while (ofs < maxofs) + { + if (inorder (pred, a[-ofs], key)) + break; + /* Here key <= a[hint - ofs]. */ + lastofs = ofs; + eassume (ofs <= (PTRDIFF_MAX - 1) / 2); + ofs = (ofs << 1) + 1; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to use positive offsets relative to &a[0]. */ + ptrdiff_t k = lastofs; + lastofs = hint - ofs; + ofs = hint - k; + } + a -= hint; + + eassume (-1 <= lastofs && lastofs < ofs && ofs <= n); + /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the + right of lastofs but no farther right than ofs. Do a binary + search, with invariant a[lastofs-1] < key <= a[ofs]. */ + ++lastofs; + while (lastofs < ofs) + { + ptrdiff_t m = lastofs + ((ofs - lastofs) >> 1); + + if (inorder (pred, a[m], key)) + lastofs = m + 1; /* Here a[m] < key. */ + else + ofs = m; /* Here key <= a[m]. */ + } + eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ + return ofs; +} + + +/* GALLOP_RIGHT() is exactly like GALLOP_LEFT(), except that if KEY + already exists in A[0:N], it finds the position immediately to the + right of the rightmost equal value. + + The return value is the int k in [0, N] such that + + A[k-1] <= KEY < A[k]. */ + +static ptrdiff_t +gallop_right (merge_state *ms, const Lisp_Object key, Lisp_Object *a, + const ptrdiff_t n, const ptrdiff_t hint) +{ + Lisp_Object pred = ms->predicate; + + eassume (a && n > 0 && hint >= 0 && hint < n); + + a += hint; + ptrdiff_t lastofs = 0; + ptrdiff_t ofs = 1; + if (inorder (pred, key, *a)) + { + /* When key < a[hint], gallop left until + a[hint - ofs] <= key < a[hint - lastofs]. */ + const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ + while (ofs < maxofs) + { + if (inorder (pred, key, a[-ofs])) + { + lastofs = ofs; + eassume (ofs <= (PTRDIFF_MAX - 1) / 2); + ofs = (ofs << 1) + 1; + } + else /* Here a[hint - ofs] <= key. */ + break; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to use positive offsets relative to &a[0]. */ + ptrdiff_t k = lastofs; + lastofs = hint - ofs; + ofs = hint - k; + } + else + { + /* When a[hint] <= key, gallop right, until + a[hint + lastofs] <= key < a[hint + ofs]. */ + const ptrdiff_t maxofs = n - hint; /* Here &a[n-1] is highest. */ + while (ofs < maxofs) + { + if (inorder (pred, key, a[ofs])) + break; + /* Here a[hint + ofs] <= key. */ + lastofs = ofs; + eassume (ofs <= (PTRDIFF_MAX - 1) / 2); + ofs = (ofs << 1) + 1; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to use offsets relative to &a[0]. */ + lastofs += hint; + ofs += hint; + } + a -= hint; + + eassume (-1 <= lastofs && lastofs < ofs && ofs <= n); + /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the + right of lastofs but no farther right than ofs. Do a binary + search, with invariant a[lastofs-1] <= key < a[ofs]. */ + ++lastofs; + while (lastofs < ofs) + { + ptrdiff_t m = lastofs + ((ofs - lastofs) >> 1); + + if (inorder (pred, key, a[m])) + ofs = m; /* Here key < a[m]. */ + else + lastofs = m + 1; /* Here a[m] <= key. */ + } + eassume (lastofs == ofs); /* Now a[ofs-1] <= key < a[ofs]. */ + return ofs; +} + + +static void +merge_init (merge_state *ms, const ptrdiff_t list_size, Lisp_Object *lo, + const Lisp_Object predicate) +{ + eassume (ms != NULL); + + ms->a = ms->temparray; + ms->alloced = MERGESTATE_TEMP_SIZE; + + ms->n = 0; + ms->min_gallop = GALLOP_WIN_MIN; + ms->listlen = list_size; + ms->listbase = lo; + ms->predicate = predicate; + ms->reloc = (struct reloc){NULL, NULL, NULL, 0}; +} + + +/* The dynamically allocated memory may hold lisp objects during + merging. MERGE_MARKMEM marks them so they aren't reaped during + GC. */ + +static void +merge_markmem (void *arg) +{ + merge_state *ms = arg; + eassume (ms != NULL); + + if (ms->reloc.size != NULL && *ms->reloc.size > 0) + { + eassume (ms->reloc.src != NULL); + mark_objects (*ms->reloc.src, *ms->reloc.size); + } +} + + +/* CLEANUP_MEM frees all temp storage. If an exception occurs while + merging it will first relocate any lisp elements in temp storage + back to the original array. */ + +static void +cleanup_mem (void *arg) +{ + merge_state *ms = arg; + eassume (ms != NULL); + + /* If we have an exception while merging, some of the list elements + might only live in temp storage; we copy everything remaining in + the temp storage back into the original list. This ensures that + the original list has all of the original elements, although + their order is unpredictable. */ + + if (ms->reloc.order != 0 && *ms->reloc.size > 0) + { + eassume (*ms->reloc.src != NULL && *ms->reloc.dst != NULL); + ptrdiff_t n = *ms->reloc.size; + ptrdiff_t shift = ms->reloc.order == -1 ? 0 : n - 1; + memcpy (*ms->reloc.dst - shift, *ms->reloc.src, n * word_size); + } + + /* Free any remaining temp storage. */ + xfree (ms->a); +} + + +/* MERGE_GETMEM() ensures availability of enough temp memory for NEED + array slots. Any previously allocated memory is first freed, and a + cleanup routine is registered to free memory at the very end, or on + exception. */ + +static void +merge_getmem (merge_state *ms, const ptrdiff_t need) +{ + eassume (ms != NULL); + + if (ms->a == ms->temparray) + { + /* We only get here if alloc is needed and this is the first + time, so we set up the unwind. */ + specpdl_ref count = SPECPDL_INDEX (); + record_unwind_protect_ptr_mark (cleanup_mem, ms, merge_markmem); + ms->count = count; + } + else + { + /* We have previously alloced storage. Since we don't care + what's in the block we don't use realloc which would waste + cycles copying the old data. We just free and alloc + again. */ + xfree (ms->a); + } + ms->a = xmalloc (need * word_size); + ms->alloced = need; +} + + +static inline void +needmem (merge_state *ms, ptrdiff_t na) +{ + if (na > ms->alloced) + merge_getmem (ms, na); +} + + +/* MERGE_LO() stably merges the NA elements starting at SSA with the + NB elements starting at SSB = SSA + NA, in-place. NA and NB must + be positive. We also require that SSA[NA-1] belongs at the end of + the merge, and should have NA <= NB. */ + +static void +merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, + ptrdiff_t nb) +{ + Lisp_Object pred = ms->predicate; + + eassume (ms && ssa && ssb && na > 0 && nb > 0); + eassume (ssa + na == ssb); + needmem (ms, na); + memcpy (ms->a, ssa, na * word_size); + Lisp_Object *dest = ssa; + ssa = ms->a; + + ms->reloc = (struct reloc){&ssa, &dest, &na, -1}; + + *dest++ = *ssb++; + --nb; + if (nb == 0) + goto Succeed; + if (na == 1) + goto CopyB; + + ptrdiff_t min_gallop = ms->min_gallop; + for (;;) + { + ptrdiff_t acount = 0; /* This holds the # of consecutive times A won. */ + + ptrdiff_t bcount = 0; /* This holds the # of consecutive times B won. */ + + for (;;) + { + eassume (na > 1 && nb > 0); + if (inorder (pred, *ssb, *ssa)) + { + *dest++ = *ssb++ ; + ++bcount; + acount = 0; + --nb; + if (nb == 0) + goto Succeed; + if (bcount >= min_gallop) + break; + } + else + { + *dest++ = *ssa++; + ++acount; + bcount = 0; + --na; + if (na == 1) + goto CopyB; + if (acount >= min_gallop) + break; + } + } + + /* One run is winning so consistently that galloping may be a huge + win. We try that, and continue galloping until (if ever) + neither run appears to be winning consistently anymore. */ + ++min_gallop; + do { + eassume (na > 1 && nb > 0); + min_gallop -= min_gallop > 1; + ms->min_gallop = min_gallop; + ptrdiff_t k = gallop_right (ms, ssb[0], ssa, na, 0); + acount = k; + if (k) + { + memcpy (dest, ssa, k * word_size); + dest += k; + ssa += k; + na -= k; + if (na == 1) + goto CopyB; + /* While na==0 is impossible now if the comparison function is + consistent, we shouldn't assume that it is. */ + if (na == 0) + goto Succeed; + } + *dest++ = *ssb++ ; + --nb; + if (nb == 0) + goto Succeed; + + k = gallop_left (ms, ssa[0], ssb, nb, 0); + bcount = k; + if (k) + { + memmove (dest, ssb, k * word_size); + dest += k; + ssb += k; + nb -= k; + if (nb == 0) + goto Succeed; + } + *dest++ = *ssa++; + --na; + if (na == 1) + goto CopyB; + } while (acount >= GALLOP_WIN_MIN || bcount >= GALLOP_WIN_MIN); + ++min_gallop; /* Apply a penalty for leaving galloping mode. */ + ms->min_gallop = min_gallop; + } + Succeed: + ms->reloc = (struct reloc){NULL, NULL, NULL, 0}; + + if (na) + memcpy (dest, ssa, na * word_size); + return; + CopyB: + eassume (na == 1 && nb > 0); + ms->reloc = (struct reloc){NULL, NULL, NULL, 0}; + + /* The last element of ssa belongs at the end of the merge. */ + memmove (dest, ssb, nb * word_size); + dest[nb] = ssa[0]; +} + + +/* MERGE_HI() stably merges the NA elements starting at SSA with the + NB elements starting at SSB = SSA + NA, in-place. NA and NB must + be positive. We also require that SSA[NA-1] belongs at the end of + the merge, and should have NA >= NB. */ + +static void +merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, + Lisp_Object *ssb, ptrdiff_t nb) +{ + Lisp_Object pred = ms->predicate; + + eassume (ms && ssa && ssb && na > 0 && nb > 0); + eassume (ssa + na == ssb); + needmem (ms, nb); + Lisp_Object *dest = ssb; + dest += nb - 1; + memcpy(ms->a, ssb, nb * word_size); + Lisp_Object *basea = ssa; + Lisp_Object *baseb = ms->a; + ssb = ms->a + nb - 1; + ssa += na - 1; + + ms->reloc = (struct reloc){&baseb, &dest, &nb, 1}; + + *dest-- = *ssa--; + --na; + if (na == 0) + goto Succeed; + if (nb == 1) + goto CopyA; + + ptrdiff_t min_gallop = ms->min_gallop; + for (;;) { + ptrdiff_t acount = 0; /* This holds the # of consecutive times A won. */ + ptrdiff_t bcount = 0; /* This holds the # of consecutive times B won. */ + + for (;;) { + eassume (na > 0 && nb > 1); + if (inorder (pred, *ssb, *ssa)) + { + *dest-- = *ssa--; + ++acount; + bcount = 0; + --na; + if (na == 0) + goto Succeed; + if (acount >= min_gallop) + break; + } + else + { + *dest-- = *ssb--; + ++bcount; + acount = 0; + --nb; + if (nb == 1) + goto CopyA; + if (bcount >= min_gallop) + break; + } + } + + /* One run is winning so consistently that galloping may be a huge + win. Try that, and continue galloping until (if ever) neither + run appears to be winning consistently anymore. */ + ++min_gallop; + do { + eassume (na > 0 && nb > 1); + min_gallop -= min_gallop > 1; + ms->min_gallop = min_gallop; + ptrdiff_t k = gallop_right (ms, ssb[0], basea, na, na - 1); + k = na - k; + acount = k; + if (k) + { + dest += -k; + ssa += -k; + memmove(dest + 1, ssa + 1, k * word_size); + na -= k; + if (na == 0) + goto Succeed; + } + *dest-- = *ssb--; + --nb; + if (nb == 1) + goto CopyA; + + k = gallop_left (ms, ssa[0], baseb, nb, nb - 1); + k = nb - k; + bcount = k; + if (k) + { + dest += -k; + ssb += -k; + memcpy(dest + 1, ssb + 1, k * word_size); + nb -= k; + if (nb == 1) + goto CopyA; + /* While nb==0 is impossible now if the comparison function + is consistent, we shouldn't assume that it is. */ + if (nb == 0) + goto Succeed; + } + *dest-- = *ssa--; + --na; + if (na == 0) + goto Succeed; + } while (acount >= GALLOP_WIN_MIN || bcount >= GALLOP_WIN_MIN); + ++min_gallop; /* Apply a penalty for leaving galloping mode. */ + ms->min_gallop = min_gallop; + } + Succeed: + ms->reloc = (struct reloc){NULL, NULL, NULL, 0}; + if (nb) + memcpy (dest - nb + 1, baseb, nb * word_size); + return; + CopyA: + eassume (nb == 1 && na > 0); + ms->reloc = (struct reloc){NULL, NULL, NULL, 0}; + /* The first element of ssb belongs at the front of the merge. */ + memmove (dest + 1 - na, ssa + 1 - na, na * word_size); + dest += -na; + ssa += -na; + dest[0] = ssb[0]; +} + + +/* MERGE_AT() merges the two runs at stack indices I and I+1. */ + +static void +merge_at (merge_state *ms, const ptrdiff_t i) +{ + eassume (ms != NULL); + eassume (ms->n >= 2); + eassume (i >= 0); + eassume (i == ms->n - 2 || i == ms->n - 3); + + Lisp_Object *ssa = ms->pending[i].base; + ptrdiff_t na = ms->pending[i].len; + Lisp_Object *ssb = ms->pending[i + 1].base; + ptrdiff_t nb = ms->pending[i + 1].len; + eassume (na > 0 && nb > 0); + eassume (ssa + na == ssb); + + /* Record the length of the combined runs; if i is the 3rd-last run + now, also slide over the last run (which isn't involved in this + merge). The current run i+1 goes away in any case. */ + ms->pending[i].len = na + nb; + if (i == ms->n - 3) + ms->pending[i + 1] = ms->pending[i + 2]; + --ms->n; + + /* Where does b start in a? Elements in a before that can be + ignored (they are already in place). */ + ptrdiff_t k = gallop_right (ms, *ssb, ssa, na, 0); + eassume (k >= 0); + ssa += k; + na -= k; + if (na == 0) + return; + + /* Where does a end in b? Elements in b after that can be ignored + (they are already in place). */ + nb = gallop_left (ms, ssa[na - 1], ssb, nb, nb - 1); + if (nb == 0) + return; + eassume (nb > 0); + /* Merge what remains of the runs using a temp array with size + min(na, nb) elements. */ + if (na <= nb) + merge_lo (ms, ssa, na, ssb, nb); + else + merge_hi (ms, ssa, na, ssb, nb); +} + + +/* POWERLOOP() computes the "power" of the first of two adjacent runs + begining at index S1, with the first having length N1 and the + second (starting at index S1+N1) having length N2. The list has + total length N. */ + +static int +powerloop (const ptrdiff_t s1, const ptrdiff_t n1, const ptrdiff_t n2, + const ptrdiff_t n) +{ + eassume (s1 >= 0); + eassume (n1 > 0 && n2 > 0); + eassume (s1 + n1 + n2 <= n); + /* The midpoints a and b are + a = s1 + n1/2 + b = s1 + n1 + n2/2 = a + (n1 + n2)/2 + + These may not be integers because of the "/2", so we work with + 2*a and 2*b instead. It makes no difference to the outcome, + since the bits in the expansion of (2*i)/n are merely shifted one + position from those of i/n. */ + ptrdiff_t a = 2 * s1 + n1; + ptrdiff_t b = a + n1 + n2; + int result = 0; + /* Emulate a/n and b/n one bit a time, until their bits differ. */ + for (;;) + { + ++result; + if (a >= n) + { /* Both quotient bits are now 1. */ + eassume (b >= a); + a -= n; + b -= n; + } + else if (b >= n) + { /* a/n bit is 0 and b/n bit is 1. */ + break; + } /* Otherwise both quotient bits are 0. */ + eassume (a < b && b < n); + a <<= 1; + b <<= 1; + } + return result; +} + + +/* FOUND_NEW_RUN() updates the state when a run of length N2 has been + identified. If there's already a stretch on the stack, apply the + "powersort" merge strategy: compute the topmost stretch's "power" + (depth in a conceptual binary merge tree) and merge adjacent runs + on the stack with greater power. */ + +static void +found_new_run (merge_state *ms, const ptrdiff_t n2) +{ + eassume (ms != NULL); + if (ms->n) + { + eassume (ms->n > 0); + struct stretch *p = ms->pending; + ptrdiff_t s1 = p[ms->n - 1].base - ms->listbase; + ptrdiff_t n1 = p[ms->n - 1].len; + int power = powerloop (s1, n1, n2, ms->listlen); + while (ms->n > 1 && p[ms->n - 2].power > power) + { + merge_at (ms, ms->n - 2); + } + eassume (ms->n < 2 || p[ms->n - 2].power < power); + p[ms->n - 1].power = power; + } +} + + +/* MERGE_FORCE_COLLAPSE() unconditionally merges all stretches on the + stack until only one remains, and returns 0 on success. This is + used at the end of the mergesort. */ + +static void +merge_force_collapse (merge_state *ms) +{ + struct stretch *p = ms->pending; + + eassume (ms != NULL); + while (ms->n > 1) + { + ptrdiff_t n = ms->n - 2; + if (n > 0 && p[n - 1].len < p[n + 1].len) + --n; + merge_at (ms, n); + } +} + + +/* MERGE_COMPUTE_MINRUN() computes a good value for the minimum run + length; natural runs shorter than this are boosted artificially via + binary insertion. + + If N < 64, return N (it's too small to bother with fancy stuff). + Otherwise if N is an exact power of 2, return 32. Finally, return + an int k, 32 <= k <= 64, such that N/k is close to, but strictly + less than, an exact power of 2. */ + +static ptrdiff_t +merge_compute_minrun (ptrdiff_t n) +{ + ptrdiff_t r = 0; /* r will become 1 if any non-zero bits are + shifted off. */ + + eassume (n >= 0); + while (n >= 64) + { + r |= n & 1; + n >>= 1; + } + return n + r; +} + + +static void +reverse_vector (Lisp_Object *s, const ptrdiff_t n) +{ + for (ptrdiff_t i = 0; i < n >> 1; i++) + { + Lisp_Object tem = s[i]; + s[i] = s[n - i - 1]; + s[n - i - 1] = tem; + } +} + +/* TIM_SORT sorts the array SEQ with LENGTH elements in the order + determined by PREDICATE. */ + +void +tim_sort (Lisp_Object predicate, Lisp_Object *seq, const ptrdiff_t length) +{ + merge_state ms; + Lisp_Object *lo = seq; + + merge_init (&ms, length, lo, predicate); + + + /* March over the array once, left to right, finding natural runs, + and extending short natural runs to minrun elements. */ + const ptrdiff_t minrun = merge_compute_minrun (length); + ptrdiff_t nremaining = length; + do { + bool descending; + + /* Identify the next run. */ + ptrdiff_t n = count_run (&ms, lo, lo + nremaining, &descending); + if (descending) + reverse_vector (lo, n); + /* If the run is short, extend it to min(minrun, nremaining). */ + if (n < minrun) + { + const ptrdiff_t force = nremaining <= minrun ? + nremaining : minrun; + binarysort (&ms, lo, lo + force, lo + n); + n = force; + } + eassume (ms.n == 0 || ms.pending[ms.n - 1].base + + ms.pending[ms.n - 1].len == lo); + found_new_run (&ms, n); + /* Push the new run on to the stack. */ + eassume (ms.n < MAX_MERGE_PENDING); + ms.pending[ms.n].base = lo; + ms.pending[ms.n].len = n; + ++ms.n; + /* Advance to find the next run. */ + lo += n; + nremaining -= n; + } while (nremaining); + + merge_force_collapse (&ms); + eassume (ms.n == 1); + eassume (ms.pending[0].len == length); + lo = ms.pending[0].base; + + if (ms.a != ms.temparray) + unbind_to (ms.count, Qnil); +} -- 2.34.1.575.g55b058a8bb >From 2aaa288f8209bb8d55244e1499c8da40ab3f77f4 Mon Sep 17 00:00:00 2001 From: Andrew G Cohen Date: Thu, 17 Mar 2022 16:50:11 +0800 Subject: [PATCH 3/4] Add more sorting unit tests * test/src/fns-tests.el (fns-tests-sort): New sorting unit tests. --- test/src/fns-tests.el | 70 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el index 723ef4c710..5b252e184f 100644 --- a/test/src/fns-tests.el +++ b/test/src/fns-tests.el @@ -204,6 +204,76 @@ fns-tests-sort [-1 2 3 4 5 5 7 8 9])) (should (equal (sort (vector 9 5 2 -1 5 3 8 7 4) (lambda (x y) (> x y))) [9 8 7 5 5 4 3 2 -1])) + ;; Sort a reversed list and vector. + (should (equal + (sort (reverse (number-sequence 1 1000)) (lambda (x y) (< x y))) + (number-sequence 1 1000))) + (should (equal + (sort (reverse (vconcat (number-sequence 1 1000))) + (lambda (x y) (< x y))) + (vconcat (number-sequence 1 1000)))) + ;; Sort a constant list and vector. + (should (equal + (sort (make-vector 100 1) (lambda (x y) (> x y))) + (make-vector 100 1))) + (should (equal + (sort (append (make-vector 100 1) nil) (lambda (x y) (> x y))) + (append (make-vector 100 1) nil))) + ;; Sort a long list and vector with every pair reversed. + (let ((vec (make-vector 100000 nil)) + (logxor-vec (make-vector 100000 nil))) + (dotimes (i 100000) + (aset logxor-vec i (logxor i 1)) + (aset vec i i)) + (should (equal + (sort logxor-vec (lambda (x y) (< x y))) + vec)) + (should (equal + (sort (append logxor-vec nil) (lambda (x y) (< x y))) + (append vec nil)))) + ;; Sort a list and vector with seven swaps. + (let ((vec (make-vector 100 nil)) + (swap-vec (make-vector 100 nil))) + (dotimes (i 100) + (aset vec i (- i 50)) + (aset swap-vec i (- i 50))) + (mapc (lambda (p) + (let ((tmp (elt swap-vec (car p)))) + (aset swap-vec (car p) (elt swap-vec (cdr p))) + (aset swap-vec (cdr p) tmp))) + '((48 . 94) (75 . 77) (33 . 41) (92 . 52) + (10 . 96) (1 . 14) (43 . 81))) + (should (equal + (sort (copy-sequence swap-vec) (lambda (x y) (< x y))) + vec)) + (should (equal + (sort (append swap-vec nil) (lambda (x y) (< x y))) + (append vec nil)))) + ;; Check for possible corruption after GC. + (let* ((size 3000) + (complex-vec (make-vector size nil)) + (vec (make-vector size nil)) + (counter 0) + (my-counter (lambda () + (if (< counter 500) + (cl-incf counter) + (setq counter 0) + (garbage-collect)))) + (rand 1) + (generate-random + (lambda () (setq rand + (logand (+ (* rand 1103515245) 12345) 2147483647))))) + ;; Make a complex vector and its sorted version. + (dotimes (i size) + (let ((r (funcall generate-random))) + (aset complex-vec i (cons r "a")) + (aset vec i (cons r "a")))) + ;; Sort it. + (should (equal + (sort complex-vec + (lambda (x y) (funcall my-counter) (< (car x) (car y)))) + (sort vec 'car-less-than-car)))) + ;; Check for sorting stability. (should (equal (sort (vector -- 2.34.1.575.g55b058a8bb >From e0443500e7d4b8e50a5e5af01eda1ac48f0b0f7e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= Date: Wed, 16 Mar 2022 17:33:07 +0100 Subject: [PATCH 4/4] Resolve sort predicate ahead of time * src/sort.c (tim_sort): If the sort predicate is a symbol, find the corresponding function before starting the sort. This is especially beneficial if the predicate was an alias (`string<`, for example). --- src/sort.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/src/sort.c b/src/sort.c index e7ccc1c052..48e106e92d 100644 --- a/src/sort.c +++ b/src/sort.c @@ -913,12 +913,24 @@ reverse_vector (Lisp_Object *s, const ptrdiff_t n) void tim_sort (Lisp_Object predicate, Lisp_Object *seq, const ptrdiff_t length) { + if (SYMBOLP (predicate)) + { + /* Attempt to resolve the function as far as possible ahead of time, + to avoid having to do it for each call. */ + Lisp_Object fun = XSYMBOL (predicate)->u.s.function; + if (SYMBOLP (fun)) + /* Function was an alias; use slow-path resolution. */ + fun = indirect_function (fun); + /* Don't resolve to an autoload spec; that would be very slow. */ + if (!NILP (fun) && !(CONSP (fun) && EQ (XCAR (fun), Qautoload))) + predicate = fun; + } + merge_state ms; Lisp_Object *lo = seq; merge_init (&ms, length, lo, predicate); - /* March over the array once, left to right, finding natural runs, and extending short natural runs to minrun elements. */ const ptrdiff_t minrun = merge_compute_minrun (length); -- 2.34.1.575.g55b058a8bb --=-=-=-- From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Lars Ingebrigtsen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 12:03:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164803695812980 (code B ref 54532); Wed, 23 Mar 2022 12:03:02 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 12:02:38 +0000 Received: from localhost ([127.0.0.1]:42965 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nWzhF-0003NI-P6 for submit@debbugs.gnu.org; Wed, 23 Mar 2022 08:02:37 -0400 Received: from quimby.gnus.org ([95.216.78.240]:45302) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nWzhD-0003N2-RY for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 08:02:36 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Content-Type:MIME-Version:Message-ID:In-Reply-To:Date: References:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=4yuWLiIrzjwBc5jQuusBdovQ9BCWcoWlpNqI4JD1zLo=; b=gI705Jd3QgPFArfOm3He1w493G aPoiey5YjAP5v2Z9JpW5BpuDHipncFfN/OkPKWxm6CmHUWcPe/KbKyKm3UcwFI5HeCCkCiEvubO/z izGS99BVEzGet9iB4WmgAUwot7Ol+szQgr1XrmDDdbO7r+VNWrJjekAMG9QYagUC+278=; Received: from 109.179.236.69.tmi.telenormobil.no ([109.179.236.69] helo=xo) by quimby.gnus.org with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nWzh5-0003HV-D7; Wed, 23 Mar 2022 13:02:29 +0100 From: Lars Ingebrigtsen References: <87k0clr12o.fsf@ust.hk> Date: Wed, 23 Mar 2022 13:02:26 +0100 In-Reply-To: <87k0clr12o.fsf@ust.hk> (Andrew Cohen's message of "Wed, 23 Mar 2022 07:59:11 +0800") Message-ID: <87ils4ancd.fsf@gnus.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: Andrew Cohen writes: > | | oldlist | oldvec | tim | > | (make-random-list 10000) | 2790 | 2123 | 1557 | > | (nreverse (make-sorted-list 10000)) | 1417 | 987 | 118 | > | (make-sorted-list 10000) | 1310 | 899 | 116 | > | (m [...] Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP 0.0 TVD_RCVD_IP Message was received from an IP address -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Andrew Cohen writes: > | | oldlist | oldvec | tim | > | (make-random-list 10000) | 2790 | 2123 | 1557 | > | (nreverse (make-sorted-list 10000)) | 1417 | 987 | 118 | > | (make-sorted-list 10000) | 1310 | 899 | 116 | > | (make-swapped-list 10000 3) | 1457 | 1019 | 122 | > | (make-plus-list 10000) | 1309 | 899 | 119 | > | (make-onepercent-list 10000) | 1764 | 1272 | 183 | > | (make-constant-list 10000) | 1292 | 888 | 116 | > | (make-evil-list 10000) | 1374 | 946 | 398 | > | (make-block-list 10000 100) | 2235 | 1646 | 919 | > | (make-block-list 10000 10) | 2598 | 1962 | 1451 | Wow, great! A tenfold speed increase on (mostly-)sorted lists (which is a common use case in my experience) is impressive. Reading the code, I don't really have any comments (but then again, I don't really understand the timsort algorithm anyway). -- (domestic pets only, the antidote for overdose, milk.) bloggy blog: http://lars.ingebrigtsen.no From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 13:31:06 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164804226410360 (code B ref 54532); Wed, 23 Mar 2022 13:31:06 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 13:31:04 +0000 Received: from localhost ([127.0.0.1]:43161 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX14q-0002gl-4I for submit@debbugs.gnu.org; Wed, 23 Mar 2022 09:31:04 -0400 Received: from eggs.gnu.org ([209.51.188.92]:44226) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX14n-0002b8-UF for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 09:31:02 -0400 Received: from [2001:470:142:3::e] (port=36320 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX14h-0000FG-G3; Wed, 23 Mar 2022 09:30:56 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=gHAguLYdlXidlEcV9U66AwtMEGu7tE+BKqq5tamEV5w=; b=VSm/pISHzW4v DuEgW+GVCYCkz0L1tmDuV+RWJYqxIb2RV6jbxfdvmX9NdejNHYxzHn9Dz02dP5/+LjQlfvLzvuKX3 UqqWl+GwCCCGwJm0dj46kAe5qwQYaT4j58h+0k0rFbeePOPa4jy4YVP95ENWBNYoBxQhiyHSIia+l loxikJvKBqFJHL4ItBQtGwTCnOhw/MctaROAnWQn3g5w93xK1PwssGxlYaMOdZ7sVYoHocz4QyVsC sib7h93ubgh0zN6FK/uOmiLu+Bi5HAj72JAutpCQFwjE6ipfHsq6A2UfmUQ81mtntSFjsmVoi6mGI I2q2ue4hmM2ZZHDVLCzQwQ==; Received: from [87.69.77.57] (port=1595 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX14g-0004mA-ST; Wed, 23 Mar 2022 09:30:55 -0400 Date: Wed, 23 Mar 2022 15:30:44 +0200 Message-Id: <83ee2seqyj.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <87k0clr12o.fsf@ust.hk> (message from Andrew Cohen on Wed, 23 Mar 2022 07:59:11 +0800) References: <87k0clr12o.fsf@ust.hk> X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Andrew Cohen > Date: Wed, 23 Mar 2022 07:59:11 +0800 > > 1. Add a new `record_unwind_protect_ptr_mark` function for use with C data > structures that use the specpdl for clean-up but also contain possibly > unique references to Lisp objects. This is needed for the dynamic > memory management that the new algorithm uses. Can you tell more why this was needed? Emacs has conservative stack marking, so any Lisp object that is referred by some stack-based variable should be protected from GC. Why isn't that enough in this case? > 4. An optimization that resolves the sorting comparison symbol into the > corresponding function before starting the sort. Any reasons this is a separate patch? Thanks a lot for working on this. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 13:47:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164804320522889 (code B ref 54532); Wed, 23 Mar 2022 13:47:02 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 13:46:45 +0000 Received: from localhost ([127.0.0.1]:43183 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX1K1-0005ws-GG for submit@debbugs.gnu.org; Wed, 23 Mar 2022 09:46:45 -0400 Received: from eggs.gnu.org ([209.51.188.92]:48242) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX1Jz-0005rL-K2 for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 09:46:43 -0400 Received: from [2001:470:142:3::e] (port=36534 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX1Jt-0004pd-2b; Wed, 23 Mar 2022 09:46:37 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=V9qmUVYSxYCwBkCtoNrPeyA8XXtmfqNAw9k+DlHxRLU=; b=KuuMrCcfel17 zw3/XzdBwhjFSweQ81HCuMEmosaQzd7AsdKnbKHiU6HDz7RsP41eDvtw+lC9XBU11u+sUMZsMRufB nANGGyN1WlyyKczhXvr0SnogBQHymWpa3s8xGN0p4Yi6Gw6lNKiLhRsElsg6yDPZseVp+22yl5LFQ CmCsmd6i7/TRUIEhjfslrgTSKhSVyNmFH/ybnCbTnjAfwtzzc3P3vFcrV6Qob5T/NBAZvyPqQLigv i50AKmYVsLf6IDeHKXPmfNcR0z49uTKMhaHwxKhiaTub9k1FC7jRdNHmVQxhzFTSUAtCl1qkxERMz 6wQxi62TBPA0lFNvcCwhBA==; Received: from [87.69.77.57] (port=2560 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nX1Js-0002Ph-FK; Wed, 23 Mar 2022 09:46:36 -0400 Date: Wed, 23 Mar 2022 15:46:25 +0200 Message-Id: <83cziceq8e.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <87k0clr12o.fsf@ust.hk> (message from Andrew Cohen on Wed, 23 Mar 2022 07:59:11 +0800) References: <87k0clr12o.fsf@ust.hk> X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Andrew Cohen > Date: Wed, 23 Mar 2022 07:59:11 +0800 > > The patch has 4 parts: > > 1. Add a new `record_unwind_protect_ptr_mark` function for use with C data > structures that use the specpdl for clean-up but also contain possibly > unique references to Lisp objects. This is needed for the dynamic > memory management that the new algorithm uses. > 2. The actual sorting change. This removes the old sorting routines and > puts the new implementation in a separate file, sort.c > 3. A bunch of new unit tests. > 4. An optimization that resolves the sorting comparison symbol into the > corresponding function before starting the sort. Thanks, a few minor stylistic issues: > +/* BINARYSORT() is a stable binary insertion sort used for sorting the > + list starting at LO and ending at HI. On entry, LO <= START <= HI, > + and [LO, START) is already sorted (pass START == LO if you don't > + know!). Even in case of error, the output slice will be some > + permutation of the input (nothing is lost or duplicated). */ Our style of such comments is to phrase them as doc strings. Which means, among other things: . no need to name the function, since the comment is right in front of it; . the style should be imperative mood: "sort the list starting at LO and ending and HI using a stable binary insertion sort algorithm", etc. One other nit: we dislike the FOO() style to mean that FOO is a function. That's because FOO() looks like a call to a function with no arguments, which is not what you mean. We use 'FOO' instead. (Not that you should need to refer to functions too much if you follow our style conventions.) Please fix your commentary that documents functions with the above rules in mind. > +static ptrdiff_t > +count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descending) This line is too long, please break it in two. > + eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ > + return ofs; > +} Is this really eassume, or is eassert better here? From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting References: <87k0clr12o.fsf@ust.hk> In-Reply-To: <87k0clr12o.fsf@ust.hk> Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 20:25:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: Andrew Cohen , 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.16480670667446 (code B ref 54532); Wed, 23 Mar 2022 20:25:02 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 20:24:26 +0000 Received: from localhost ([127.0.0.1]:46162 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX7Ws-0001w1-9h for submit@debbugs.gnu.org; Wed, 23 Mar 2022 16:24:26 -0400 Received: from mail155c50.megamailservers.eu ([91.136.10.165]:44870 helo=mail51c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nX7Wp-0001vr-Na for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 16:24:24 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1648067061; bh=BzU3hhMnekcRCkMlnXMr0wK/Sw1lmzYv5SqNQn5cya0=; h=From:Subject:Date:Cc:To:From; b=IMetwREp3nLVHvOeJqk4GbJnQSkNtVTax6DdHyVKe9rkgmuamthWxUyOeaG/+y2b3 TdTVm9ly41lQVCynDCD+q3oTlW5NwQxkRiIUrk8t9gthU/bOo7lv0g5XyWHCForNLL qLWQJLoV0EypL+rbwANcuuC5fsWGtJFK1jFEmixM= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail51c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 22NKOHSX026112; Wed, 23 Mar 2022 20:24:18 +0000 From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Message-Id: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> Date: Wed, 23 Mar 2022 21:24:16 +0100 X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F27.623B81F5.000A, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 1.3 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: > Can you tell more why this was needed? Emacs has conservative stack marking, so any Lisp object that is referred by some stack-based variable should be protected from GC. Why isn't that enough in th [...] Content analysis details: (1.3 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) -0.0 T_SCC_BODY_TEXT_LINE No description available. 0.3 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) > Can you tell more why this was needed? Emacs has conservative stack = marking, so any Lisp object that is referred by some stack-based = variable should be protected from GC. Why isn't that enough in this = case? Because Lisp values are temporarily moved out to a heap allocated buffer = which isn't traversed by the stack scanner. = `record_unwind_protect_ptr_mark` can be seen as a generalisation of = `record_unwind_protect_ptr` (because that's what it is). > Is this really eassume, or is eassert better here? No, eassume is appropriate here. It provides more optimisation = opportunities. In fact, most uses of eassert are better or just as good as eassume as = long as there are no function calls or tricky memory dereferences. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 23:33:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 54532@debbugs.gnu.org, Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , larsi Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.16480783232012 (code B ref 54532); Wed, 23 Mar 2022 23:33:01 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 23:32:03 +0000 Received: from localhost ([127.0.0.1]:46314 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXASR-0000WO-Gd for submit@debbugs.gnu.org; Wed, 23 Mar 2022 19:32:03 -0400 Received: from mail-os0jpn01on2101.outbound.protection.outlook.com ([40.107.113.101]:38341 helo=JPN01-OS0-obe.outbound.protection.outlook.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXASP-0000Vu-1V for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 19:32:02 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dW8rkXe7ojjJfdpCoXcqa3SArxwNaX4Src2d4EhLwzW8j+DXSxYqRzghknAoJTPVRDIKAwbffNtW8sLFSAsFzCzIyZt5csZaDCYPvcLyXuCA5+ppnCF/6Nu0g9cRXznQR/uvNmixJSXoIBhNwS1P6mLyWmoafgLPIo/OxIe2UsxzLTlQqtMsN/KCQUsCfTl4MuAvnLvrhAHCBLvzD/XqzkX6uj14jXWQe0cE7TkGn8buwXX1SMyCg9i3peWUErYe9MPHuZ57Qw01U3p4o2+CnO2T42lpf3ON+/g0qtuidUS3dmSZJp7IFgAPDJNnEabI8AR2ho67nFc3pgv4UX6qlQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=7Fz/PxUdzUjY2w4J7r/zr+gny46AGSYhw0LIZLaP+tU=; b=S2VdqWMKml4bOsVY/Ebh4+e2uFZVzQbCM3JhTz30SLHYNhZdFi9axIghh6SPbWdakWvmeFdYeCSCA1v9MLmeRTL/69pthOeBJtiYSlhjxOkwTeYJWqzW70CpBTmSnALweVJqz/wvv3Dkb5+FTELKLCD6h+SvEN2kNcjbNTMYtYdt8MY9Id7kn2zk3tWHtW0R9+ChjbrEgEufe1qDK1Nw56I6qmqMlGpn7Rvc5TxJVCk5xWySBKbkxYR9q5IteUY8fkg8sA/3q3UVlVLHOgwcjiued4vjFNt5whwP/eraAz9vcvCveTtDGw/c8HoJONEzpzlX8OebHODf1uu5Nr9qxA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=7Fz/PxUdzUjY2w4J7r/zr+gny46AGSYhw0LIZLaP+tU=; b=xKmuay+ejIMfm6JKQXAFFKnaek39IOXJ7NYppqXgsOobsGtuJNx3dyuz7THyqX8rVxlO9tRxxnxjalBEQ6BrnoHQ8MvHRumS8jRpnWTWDgQt+SUP6zR1yjW2eXklFFCD8EYTJOzuWS3IC9IRBtSpx2bdjBsh3f62PDS4tc0uM3+utUZ26Q8ofFun2sf/BVsqNJhT79Prbj2oJyP5uI5HPE6am643ekp6g+JD3zH7+xRFgx80lKNIExyqjsMoyNtzPc9upT0l5W3cB8abNe/Ucf8izg1yavpICsa2dESwQLpcttlh2XRQRcAl0l6byYitk/o40ULyJGRCP5Jshah/hQ== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:167::9) by OS3P286MB0707.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:e5::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.17; Wed, 23 Mar 2022 23:31:53 +0000 Received: from OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM ([fe80::134:8477:848b:b601]) by OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM ([fe80::134:8477:848b:b601%3]) with mapi id 15.20.5102.017; Wed, 23 Mar 2022 23:31:53 +0000 From: Andrew Cohen References: <87k0clr12o.fsf@ust.hk> <83cziceq8e.fsf@gnu.org> Date: Thu, 24 Mar 2022 07:31:41 +0800 In-Reply-To: <83cziceq8e.fsf@gnu.org> (Eli Zaretskii's message of "Wed, 23 Mar 2022 09:46:38 -0400") Message-ID: <871qysgs9u.fsf@ust.hk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Content-Type: text/plain X-ClientProxiedBy: HK2PR04CA0070.apcprd04.prod.outlook.com (2603:1096:202:15::14) To OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:167::9) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 80795e3f-cce1-4c7b-fa45-08da0d254fa3 X-MS-TrafficTypeDiagnostic: OS3P286MB0707:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: qUh9FqzLk5T4NIVAknMj3sVaL4I9rcPHlce9JqP/1rY7qBLP1/NDon9SKlz5R55YDplonRow/m2JBkDz9iwFv+QA6LuB0iJJ7HMG9QpralrxPclJskbiBVO2+3/Zjhhs7N08vwxY4gxETD9h0zIrv+TjPw6afARPhfStk+oVxCQcal8EFFu170z8E3hMREM2379sEYT2657QaftSGcVGfIRhV5f+RebLhr4888GfCVY2ldOF2rk4sZobw6jQoTBcU+xreFdz+L1NQw6qWvs0boDKhHGaeo2m99viK7Xm/38Wk6b7+geHk65/CX+S2HFdLHBvAWtLchjaEvcgyH/75IKV8AGd2f9IAYbW5A4UW66ioPr7rsbtPQDHiFt+fsb1tZ26ONQSf6DP8BPF30YBM7Yk5s+9N4k437ZART1VjC6BHaiSK66MbV1XrC2cydaBxTPj80G5FEM9rpWNFaWGpKFzdwzyfFgEM4y0KqJtgozFDUSHBQM1CfVo9po8FIej6L0NvyAmiybukMMwbPgVvumUJZG410UcFN7OMfdF4cXNQ0yjKuAo11UqteO6wuIGKCyrBueXgLfY7YrOvYhGdTqhU5ygR8zCqsBGrZ+sRgy7XulFeX0BIcN0Hkd1DA6cTVbI+0akJs6r8zEk0/pDAA== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(6512007)(2616005)(6486002)(508600001)(5660300002)(8936002)(6666004)(6506007)(36756003)(186003)(26005)(38100700002)(6916009)(54906003)(786003)(66556008)(316002)(4744005)(4326008)(8676002)(2906002)(86362001)(66946007)(66476007); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: HA+AD+jYjk1JOXrMfdjW3uN9mePMR+CXwx99YMO7uyeFE/97a+xyJdeUlal+nx1S7ocI7muWcXC29tff3qFq+kGmNL4J5+95QEVvDWE8PdoaPYm7WYzcFZgmV20zvYND4ra6ogJzUx8GA/1hnpUpezlhc+sJCJyUtBoSIkLx9nTEGvFsUwuTdyTgBlTQAseTrGHPRVcez3RTxEJ65aiCFWzFh8FZA5++VahtLct0jV8hsDWsUPjmowkiT5o4AbryA5p1ItT93CCKhuCjMfEw7Uuf7KYN87+VCU+iE45MxLDwSLElPV/vXu/KaKbCXrd6jhYpGocjuv4QJ+cP5AFi2hXyGCe+yyqf9EEVkyho+PgPxT71hH34C/EjR7bLHRAm1LhD4P49Cb03ZL/tYTf4iCNWUuQSNa6o1iZ6lPvfsl27uu632WQ0B2Ad5rwNwHOh2zr/tQ8bCcLcAqUc6cw4xalW7c6q3/ZA3mrtOI4UcsdsfOv1st7NZyyOzJg+Q08glAw6tgiO0fseihmfGIaSXW7QX4JBGkzbqiMH9GnzDqdgteDCLmOH1KfYBXoCS7nWVgfg3+gimzU0HS4VTNIIhiYZvyCxMiWrDQD61dq5+5F47Tu2YPGQhGHjGe/QumMVx6vOcBQZA3nkdLZ52H7ZAZ3+4rQ+urR4MF+3m/rQzD7/LfUfdPOuDxHE+z/vWPYPqlyi/ErYkUtY0vBMGL5TufGD0pUFsCgVvE4ESJ1A8ksbe4C+9QYzz2L+Kuxe7Zzm/brS3Z8alCEEND1e9K6+295TQUdTganu6uoepaxP88bx040L7kWMXncjSsGXGnJ6dAHaUiQuSOebpdrLrr+VZf6XRlDtcBIy+jBlU9HVMVTZeRpPdhMSDcXPAdEBz7YkQ+hBHRrLGFCjpYFHiGwiGcqoyH/vnTrgs9JFcz6NRr1AIMeAv1O+87mK9k+EOoQVM8Gtg41P+zky++de7YDUOy6ViYaAZ0H9Ul9o6T/Ea8vIH5gxaVgiQnP2EpR2cE/9+qSuaBkZJIpXQfrCJo78ZWfLeMt/ZRK7sLGQpVLvRDjSjNUItTrCZe1+fm0ufzK5/RffrBzXJuYYhcr6owVm8R6RMIl1fy7RBzzvyfW0SLso8QMsph51KlbqGCoJ/5p48HllgXCgcjzv3UUytFCIa3a42cn9oxyl48aQGa9UtDTHy988pIb9VLhHvkTNNIYq3cladILDKdpoOJw+7ZzP5eK+Pb8WL01ykrW9DlS22uX4JwqxGnFAR4xPwzSRJDGovSzwGZ7lCTS6//KtdPFs+OTNN5VW/nGisczdppE/Zj2VdfQh9xpbPpCjXQyo6WC1VrPjvDK+Fed9I4foxs99CAzyKDki2Z23rIQxJ3kz5Epp5kbGZpPCf9YCcnhzG+G9+bnH6gbIhVQPRLJZYysFSP7mDDJeVmGy3W88AZzkTUg= X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: 80795e3f-cce1-4c7b-fa45-08da0d254fa3 X-MS-Exchange-CrossTenant-AuthSource: OSZP286MB1870.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Mar 2022 23:31:53.0869 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: C0cK1mJ49uX/iIwnUxVy+OQGkUVPXffpfNpC6DDsvUyI9Asa+3Z0GRl00oUT7Xsm X-MS-Exchange-Transport-CrossTenantHeadersStamped: OS3P286MB0707 X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) >>>>> "EZ" == Eli Zaretskii writes: >> From: Andrew Cohen Date: Wed, 23 Mar 2022 >> 07:59:11 +0800 >> >> The patch has 4 parts: [...] EZ> Thanks, a few minor stylistic issues: [...] EZ> Please fix your commentary that documents functions with the EZ> above rules in mind. Will do. >> +static ptrdiff_t +count_run (merge_state *ms, Lisp_Object *lo, >> const Lisp_Object *hi, bool *descending) EZ> This line is too long, please break it in two. Yes. >> + eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ >> + return ofs; +} EZ> Is this really eassume, or is eassert better here? See the comment by Mattias (this is outside my area of expertise). -- Andrew Cohen From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 23 Mar 2022 23:44:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii , Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , larsi Cc: 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.16480790063011 (code B ref 54532); Wed, 23 Mar 2022 23:44:01 +0000 Received: (at 54532) by debbugs.gnu.org; 23 Mar 2022 23:43:26 +0000 Received: from localhost ([127.0.0.1]:46325 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXAdS-0000mU-Ic for submit@debbugs.gnu.org; Wed, 23 Mar 2022 19:43:26 -0400 Received: from mail-os0jpn01on2132.outbound.protection.outlook.com ([40.107.113.132]:63810 helo=JPN01-OS0-obe.outbound.protection.outlook.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXAdQ-0000mE-KJ for 54532@debbugs.gnu.org; Wed, 23 Mar 2022 19:43:25 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=gaYWG1rBWgHdwKwZ5lm32MVhRvxT97XbpRlKm8Z8nl5KrDmah+hBO3hWpLUAGC2gVjrzn3skevwBZ43zxWivemdbx2dWybiCnAzj7YBFaf96/BoopHCFcLBotH1UJvVBKjeaQkNCjqeovOX3hFkcplEVH1dfq5Fv1wqWbGfsI3mo1aN1VllMoHGkJRWu2pgELNdA6NkiOHDfLb0WNnBSQvOSU8Cp+kHEx8OIH7a2K3+OUoo8w1x/ohRJAhk0SRkhR6zkHq9Jc8faBQLDfhLq2jXJwKOBcjva7TadozeTbsBtZLziUu7wMXyFkjfoxU+YdSxesXLH6au4E18qtDIoew== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=UKA7HgMSOAa0JyqVqa6k2krO3SwCmbzsNTDbRGXqneA=; b=Us6d/MhdvP1NPc0b4TPwyfr8yXqHVQoTGUV6hADfEN9GKKftMiz5XnEofFcCUbapo/eJ7qkq067fn05eYv5KzmeQi5TMj5TMPba8AgczKq2yvih8g3Ej71Ps3kz1RScFNvauBOuo7Z3wmmev/b1jNbbR6pVvWcm1L4WxsHz+3C0j2A63riZgdKLrxyurMVTlohAXaEevSSJyKqoj2kyoU3vXDZS9eYrpqHYVkB212TTaek4I0Ek8RZ2cFTTiXDA62k59QPlYxLQRrjz0LqAOu6leUuq+NTxq6UFD21wQ0GPe1XRxQXb8MxT6AL/vFEXAkzWaW2UcJx2CNNdtGP0zHQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=UKA7HgMSOAa0JyqVqa6k2krO3SwCmbzsNTDbRGXqneA=; b=heuCGIde/fVLZe2dYZb9zKfOuW+iL3wFqKeu6+CvrDWk/FxsRK/RvIjiCbzxdsZ7VDSgesZO2UFTDHlrWQ6v5NNgLGCNrVQmOJdp9oekWiJeT1H3YN0NO0eIXN30fk0tHO38xhiFVhuMqPynEhdE6J2B5sWi/1LzKDmnq9Ll74LqN17rEwSDINocAmc3+Jc3xAl0ylHuuo9zb6ce6q4jRX4nRiORSGO6xB8p2FkC6cpAwyBgJ8X3K1dmWtJw5StSrgWGcPCsWGEuhiZv39A4PqfLGk29BqK2ffOq+35n1TcPVQjd80+rq5JO2ksvrJ7CGyjT5DGXRPXY6so/ejipIQ== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by OS3P286MB1687.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:161::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.16; Wed, 23 Mar 2022 23:43:16 +0000 Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717%4]) with mapi id 15.20.5081.025; Wed, 23 Mar 2022 23:43:16 +0000 From: Andrew Cohen References: <87k0clr12o.fsf@ust.hk> <83ee2seqyj.fsf@gnu.org> Date: Thu, 24 Mar 2022 07:43:03 +0800 In-Reply-To: <83ee2seqyj.fsf@gnu.org> (Eli Zaretskii's message of "Wed, 23 Mar 2022 09:30:56 -0400") Message-ID: <87wngkfd6g.fsf@ust.hk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Content-Type: text/plain X-ClientProxiedBy: HK2PR0302CA0011.apcprd03.prod.outlook.com (2603:1096:202::21) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 7e77d0de-d632-4462-9183-08da0d26e606 X-MS-TrafficTypeDiagnostic: OS3P286MB1687:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: mUhucQWWwvPsK/SsXpucnxk6MhhYwcZwa/JDmNLQd3TrQQyK03CZc1/2Bd9/3OQBtdM1dSdw+FYbaynfcRHVdpmNxpGREw/99ea0oXQOC1pTrAJMpqBsbURl9Rle00BOjsSskryUiLDr8eh6gqKt81h/suojhjdWDS73oxAChs9ybz/dEt/TEH6GhGULsKq9MTIfO7fVH/eixp13EXicALbRjKhWVMnelRSpCqNeeVBRF1LaYjkr/kXXfnNOC9LWlv40iFeX3AuPXmlkB3VYEApn9/DGCtP6/MVEPmEW6W6yYg07ToQj0BjKK6aYFtVAwGkaYtvxigZsTJTpWLiaC6lSVSIl9sgloED0KjjKW/RmxojWTdzAX41HPoANvZy9kbimlKvdtQYQ82QV8yG6BrdvWkdWRS84rnIKc2rONbA8hjFV4IsZHHzd/FiAO9/Ut65ggScRMULUO84RxVqmosBU1ZD8CTUnndhiTmIw9WEzbMvCxcEX3izVOuz4PsKBAixqvGD+FbhorM76DDF7DrZKJMCavEhB7Zv6oal/zY1JIk+porgw7TV21Suzx2480U7fYsIuaM2+4Mf1SRWXv/4fdam4q+J+pWCwfALReWPALW3VfziisK9WCszrIUsLaiAmts9zcNjxYWXh7Vbwrg== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(86362001)(66476007)(786003)(36756003)(316002)(2906002)(8936002)(38100700002)(5660300002)(6486002)(6512007)(186003)(26005)(66556008)(6666004)(2616005)(110136005)(6506007)(508600001)(8676002)(66946007)(4326008); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: it9/+MIGMvkQBipFe5jqboH2BsCzfsO9l6+6YGUw2D5TQvxLkVvBl6/5hWjddjBYBMXOzJgWuBh2Ooe5pyLF7Qgqgb62taNKBB2jJiOcw2vBVdl4dTBhZzivK5Gtf53hYDhebiFJfVXMbG6pO49+pEpH0GDobxJjDSj8wbMyPxfjsfNPuSsJNS7WtK4tQA5NiEvfdEyPJoFk71Uqh9nolZiHp0kJPi5gBdCBjYqb5N5cnuVapy/8XS3WkU41v6MU9HFJsFnyEtkdmHnvz+jNxKjyQf2XwXWN5Z6/3H6pbS/lZXz02oH41kUH4+ztqPw0lkoguEvl4UqOsLxP6LFE1/rofQRIqAp26IylIZhlNKqzMRnJxeecbJyn19KeZFmKkt8R4VbLsjLkwubXNpPu7WGlwTn8b3hv/6XuwZ+l+e8TSXrxkUDLUYS8nTjySJdaHuG3f3S2cLonFLy/9nXMpV8JNIZUK2/liW5kaY1ODcALrAxhEtRP+cSU7bJHLTSfpWi2Utjp+RTUcH1Y5+h0ZEkEDlYLSzbOuL2BuusoJDRjsAuxb7D603YG1FNr3Nq5vBOp2MJNSefq+D8djdSdqYTJt8PcKaZdZuTEHuejhe8xTKjOlafyPVPX5zx0MEE6+XauYSTK2tOdTsuByjbVU2TZNiN+AJ4Xg0XERitYTpSYIvW6PrAJ0IcdnHTnGvZyii2pTxv8ClaF1kXFqjn2ygouXVP3C2IvuMA+O4DAFQC3BwCEVKbyY3wbhsdy5W6V/mKPSkUzWxTnPF1nO6Sq2+7CGbuwcKM3MtOq04T07d6H1yUuba8AKjIK90O6pkSGZJ/8JseRnS5II/D0zSEujCs6oo2aSSn/3tEvT6/K9955qKaaLzz51hTf/zuUiiozEvteHWmXxPPfDm48UToe+mf02gTIGOqtqDw+bgALFvHlE/IgNeRkG4cbwmdtNSMA8fDhH624Dxht88JvX4vXAE4wLMZ7KSxn/rEZxMLuFTVNwR42rypKcm053LV1kIZkwGf9bMGljzGZBQJn8YsjPvp3/BEBT0NgDw4vY0WN/pwmFYetP97jgN3MCHxeEsNO3UaQ5+9KU2V7Tugixl0m4YZqQuc0v+h6GgePYHbLCT6t+aBwGuWA8EUg+V1SzX7yRSU97R+lS4PwKp7YnyYq7bVXpK/OF8h3Jgcgq6zcfRthZ0Qva/+sYeTnFlbw7ie6HJW0qAm4bwvrhlMbWx+kVl6gNhw1ANpJsplORgCdsWjYf9bAouHQmemXgIwiYGya8pA907bJwPuqZnpp1r98JSMFJ3lWbawNBch/oJBhSDAZw6IVR2mwnDBUOXi04OADy5SzuPTZ8pr5SL+MVYJ2qPyI2/zRSetcKtr9aU8bOd6IYChv5ZirSiDrrXDwqmovRd3m2BD+TfieI9GeIghOKNhWjCCLxjaOQ26bjfOaZiA= X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: 7e77d0de-d632-4462-9183-08da0d26e606 X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Mar 2022 23:43:15.2097 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: 44MaYvBM2xBoLyr1M+y2IQZT5bhB2ff8o6oN4eZbe1YP6O6st1U1LOlag1uIhy/t X-MS-Exchange-Transport-CrossTenantHeadersStamped: OS3P286MB1687 X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) >>>>> "EZ" == Eli Zaretskii writes: >> From: Andrew Cohen Date: Wed, 23 Mar 2022 >> 07:59:11 +0800 >> >> 1. Add a new `record_unwind_protect_ptr_mark` function for use >> with C data structures that use the specpdl for clean-up but also >> contain possibly unique references to Lisp objects. This is >> needed for the dynamic memory management that the new algorithm >> uses. EZ> Can you tell more why this was needed? Emacs has conservative EZ> stack marking, so any Lisp object that is referred by some EZ> stack-based variable should be protected from GC. Why isn't EZ> that enough in this case? Mattias responded, but just to recap---during the merging of sublists additional memory is dynamically xalloc'ed (and later xfree'd) on the heap, and there can be brief periods where the original Lisp_Objects exist /only/ in the heap. The alternative (which we mentioned briefly in earlier discussions) would be to allocate the maximum amount of needed memory at the outset with SAFE_ALLOCA_LISP. This is what the current sorting routine does. But for many (maybe most?) actual calls to timsort no additional memory is needed so the dynamic allocation makes significantly better use of resources. Mattias explained the issue to me and once I understood it found it was easy to trigger; there is a specific test in the unit test patch to check for this issue. >> 4. An optimization that resolves the sorting comparison symbol >> into the corresponding function before starting the sort. EZ> Any reasons this is a separate patch? Just to make it easier to look at the rather lengthy code by segregating things that are self-contained. If/when we decide to put this in I would probably squash down to two (or maybe 3) commits. Thanks for the thorough look at the code, I continue to learn a lot! Best, Andy -- Andrew Cohen From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 06:43:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Cc: acohen@ust.hk, 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164810417612884 (code B ref 54532); Thu, 24 Mar 2022 06:43:02 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 06:42:56 +0000 Received: from localhost ([127.0.0.1]:46652 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXHBP-0003Lk-KB for submit@debbugs.gnu.org; Thu, 24 Mar 2022 02:42:55 -0400 Received: from eggs.gnu.org ([209.51.188.92]:57004) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXHBO-0003LS-2L for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 02:42:54 -0400 Received: from [2001:470:142:3::e] (port=51008 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nXHBH-0005FB-Vb; Thu, 24 Mar 2022 02:42:47 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=QGmdfVyMay5+o/rTHPbchVzlOGAie77yTEsfy2/aWwY=; b=BkY8WYI2D5KBOH4j3ogN f4wl8c0CwZ4EsurGgVcTo5lgtUgbn+FbdJg5tz8+4wUJjo5j28CBkUg7ojkz5PT/kknQkn0oPNxXC 0w03f9nNv7zUi1XLzCLKlvdC4AE3dYGVUF63rmfx3C9cGAPqGd+WpbsQybouDnlTBV2LgQgrUikxP 7lIPufqY5pAOZAJmN9+LDG4nNme32Rfy83kzx43zcTuecf0x6KTP3kZv8ZZ7mzrhmMmvY629wfyeT kvJ5AE6YG8eskq6YNUWri3AZxpQZkJwZgL+8l20IGBWNiJJheVSTMORdKJ/R00Yf2rnrIaYX05kSh fIZzDKDWbvKhoQ==; Received: from [87.69.77.57] (port=2930 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nXHBH-00080z-BM; Thu, 24 Mar 2022 02:42:47 -0400 Date: Thu, 24 Mar 2022 08:42:39 +0200 Message-Id: <831qyretr4.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> (message from Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= on Wed, 23 Mar 2022 21:24:16 +0100) References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Mattias EngdegÃ¥rd > Date: Wed, 23 Mar 2022 21:24:16 +0100 > Cc: Andrew Cohen , 54532@debbugs.gnu.org > > > Can you tell more why this was needed? Emacs has conservative stack marking, so any Lisp object that is referred by some stack-based variable should be protected from GC. Why isn't that enough in this case? > > Because Lisp values are temporarily moved out to a heap allocated buffer which isn't traversed by the stack scanner. `record_unwind_protect_ptr_mark` can be seen as a generalisation of `record_unwind_protect_ptr` (because that's what it is). I understand that these objects are on the heap, but AFAIU a reference to them is on the stack, isn't it? > > Is this really eassume, or is eassert better here? > > No, eassume is appropriate here. It provides more optimisation opportunities. > In fact, most uses of eassert are better or just as good as eassume as long as there are no function calls or tricky memory dereferences. I asked about a specific instance, not in general. That instance was at the end of the function, right before it returns, and I wonder what kind of optimization opportunities that could present. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 07:24:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 54532@debbugs.gnu.org, Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164810658917001 (code B ref 54532); Thu, 24 Mar 2022 07:24:02 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 07:23:09 +0000 Received: from localhost ([127.0.0.1]:46695 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXHoK-0004Q7-O9 for submit@debbugs.gnu.org; Thu, 24 Mar 2022 03:23:08 -0400 Received: from mail-tycjpn01on2116.outbound.protection.outlook.com ([40.107.114.116]:13265 helo=JPN01-TYC-obe.outbound.protection.outlook.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXHoJ-0004PX-3H for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 03:23:07 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=hcR66FcAdBMsViJiQQAQNjfb7vtVzXkNjS45/QN3Cj9LFY8J4lb38HdGBNsSVkijkCfikRkQTn6qzuxFbbvjqc24apCsacEqP5ZbOjIULAxWH2anqeckUjyyt8Wk++ZkJMN5Z5qy/Sx1+vzPvT4L0p8wexm4j//o6xp2BY/kOJr9K9892CusXBw22830M/Z5fYRSKg8szohd6dqrE02uUbXJGDRgsuVnFnFfS2vrMN5EXJbl14ZV9HSOKFHf4Br0AeqNMVl/NEff0k6mhdG9Um0AynLfIxoBghwAjhpwH0GQvneymhRDP87/fyxgSor2BM4cKm2OZ9K1XMvCKu4ZMg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=uYS2galQHTDESGZZ22A6zjy03cud5jToIkmAE2pzad0=; b=HAjb+EzsPdzpvPY2t7uqZyb8QD96+uVQ+CNwT51JQ4iUo+Acu6vKDzEk3hEItXYvhp1ratnG/gfsRdt1N0HYqOZyiT4vwceFhiktOlrjF4fgkAmYc6JXZDut1RWDY4Cbt18XvAWVInonPmtphvof4sqbFTt9oIDkxddRf01b1+PsnHuSQ1C3Dk+N3DNBR18yH1Lo+GYpDdrzSsd+cgsrWoIgtHC425jyM8Y6uVdg4AxhH0owdSjAT2jIqNPvSVtsq1XPpeF/To/OG81OdqRa56scA727Fs2/IqXXW+VpftAe1Y+K5IlkogjU6cCd8g6K3dywaCF6/jU7NrilTuvueA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=uYS2galQHTDESGZZ22A6zjy03cud5jToIkmAE2pzad0=; b=EDPWG2EtKgmh2NNTda/LR24QKg/H7Q7FHcLbTSj/UCMk3aUb6kUD9og6y6A96Ghosr9arbwYyxmhJCXIp81nOfpJCD2Y3aYUA4xvrSvwhY0gIAiJmCKV0Rly3s2W+cOkUV0DP3ugCKe9WIi0GPel5ukTyXON6dbTGMVizh6i2VtOjZIlvQ3QsRkiHdnj50L+B/v359XPW/mRlbFwZKkl+zvv/ntqNhE2ut7YWJidvn+0+5uW2XyAA5gLFH9Fjw4wqMTW4DTpqTMG+VDR0HnXvjrrsiOCh2qJftD/Y9AFfHTImqXijEpjBkQG4hvmkzm26bRSFFKKycRNycrYy5OIig== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by TYAP286MB0075.JPNP286.PROD.OUTLOOK.COM (2603:1096:404:8033::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.17; Thu, 24 Mar 2022 07:22:58 +0000 Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717%4]) with mapi id 15.20.5081.025; Thu, 24 Mar 2022 07:22:58 +0000 From: Andrew Cohen References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> Date: Thu, 24 Mar 2022 15:22:50 +0800 In-Reply-To: <831qyretr4.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 24 Mar 2022 02:42:48 -0400") Message-ID: <87fsn7erw5.fsf@ust.hk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Content-Type: text/plain X-ClientProxiedBy: HK2P15301CA0017.APCP153.PROD.OUTLOOK.COM (2603:1096:202:1::27) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: cab747d1-b6ef-47c6-e136-08da0d671f44 X-MS-TrafficTypeDiagnostic: TYAP286MB0075:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 16na04KHv9Ge3pc63LBSFUS5ZhubPa3Y5P2fNciWqikpGksBIpaX5viDJ/Q7J738yvHfv2c4D3dRbuFCiF/5L+Cr6sbuZ2+WJQ37+E5Yn1dE0uDEAHw1FI0kjKU3dYH8v6eOqBaDDTK8mmroIIilo4CUjBJGV81gCjlFJcczSg1ZxSnYA+WwMXrDfOIALFNeZHMyjMMyS/qk6gn+XZWJpbwlgy3xpsTqLzIPzO/Qtk67lBxRhL6uPQ/lRbb7ObOlvsFokdkA0iS/dEJ9pLcuokK4sor9qggBIpphvrqTZVZy54+QP4w2iCuum7DdJLF7098TqlB3cs4qSumxUiRVFfDWEzo+6TcHYSl7+x8DsUafMjgGqxAToOwgltWha4jag3D+asQ/BYyJboHhEtR7st0NBEaVMzsVeFpXQ8RuvZeq5kkghEVYgx65JNpfBCWMF6UlvSek9Z3LG+NkY1lylFRNVdwDA0nTc26kqegyv9mrYlbTOo/3asdGRkqTW8rfqZItJLSJNtgdcOUxCfcLyV3QpJ6b+QyCAIiSUB8RbgE1NOuEF27QvGZ96nCg0oBx/EFpYa8jwq6Ym/MXhKqmPP2iUYaY27MRLYQXQLLurlH8kqTYodzAkT9ryRBpjBmQ09QIn54MUDiA+GdNJNwkiw== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(38100700002)(786003)(316002)(8676002)(66476007)(4326008)(6916009)(36756003)(66556008)(66946007)(6506007)(2906002)(6512007)(6666004)(2616005)(508600001)(6486002)(86362001)(26005)(186003)(5660300002)(8936002)(83380400001); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: vlNIeHGuG6NFnrdqRolADqLxBwONbQoo7vT9aeQK3BFSNX4/rhk1RTXqcwXn2wKBNd+j21bZgCs91ib1D5MZD/vXwsoOZfMLD9LYDN27AMKiZm6h8qPAbi2eQncrAuICMCaBuFu5otS7W4uA0YU4IqBo0uX/eOFOe95bNVo8zK+i+sU5/lPFEegwe49DHCp6mLlg9/WGYKerquOL4brzoStL1sj4HtMfmMW/QSN3Ci0L0JDREvkMXUs/ehzLwDmSIDgnvaYYB80UVNb6KP2IJ6Mg1wVSvfcWiVzX9tCu4+sgh5uRRvkvKqLOQq3v8DEHW7W5XWbTacwtIryXYkh6e+UJXfxC7oTQ5gavMytIynQTj3nwbJ6+1t3heOTETMuN7E2LYjcTOLJ0AZTp5NeDIcfF3JoaSrVelR2tzx23sPxJmvOA/+OXD15wqbdF20oHk05+QimmIc5dq/6miowm5pEVPrwldHkCirl8+Dn6AjvMO/1ZeLDlFvovPcYJBDawmNCN1oyb0So7yZJmA63Fgadm46di8RzUGEj7R4Lab8XaWEEs/MwAzee5xUm60vV6KKySmQ0Q8WzC6Dqe1dLL0dhcPJ1OweNqv8etzryvT4Rxm2yVm/NHJfi9zMt/nw9C2T2s+OUtTJApv71FQTWXrl51H5dbJktzhXtypPZG+EW/MitxejJDhAbFZmMRQmiTiQVsDH6cjVKJ0kvl7n7hEBoMkjIjkTWxIoaHJIlKZpoFBKP6HTICF16gVEn0vTKoYLTxgqhYK4ZvZr9wtFUhFRJham9PKO50kbgk/UPJIfkRseuhCE1jxJ8GhPq9aNVA5wsWQBNqz8aZ8mJM+Cu3ZPmJRrpX4UgzULSTwGMPCCIW4D33Gt4lc+JaX+B3qq9UEZpRMJvM5oou6uUuGAtAKDHzU8NNIgGMK8PTlG4FrquLwqt41kAhYGjKW9m15ZYZkvADWtoJhN483wkX906ybnkFZzGavufy0yRkuY/1uKdnsqCoF1D5s0E7EpoDD8OYR0AVWpkquxVEBHByZGKHLwYi7sV21OX4inzqD/9G898X8s5SsEcPW2bWXcL0RcEgaNn/R5ddeZSDNenCuLKxcMtxGVvXHdmTOvToMOSUC8uo6Vou6m7Ecynk3CNMFx9r1Os5oeiNllimWAAw93b9MdNM/3ORc6TYM4hkJOKANL+dGsr9epHCarlzlPkzrz0E711HtPmKU7QhYJFIdh+DYXCd/rORRyn46iOjb86CDMctGC3wOuGA2kSZeF7K0M9UGd8zLJL7Fnby5e9j51uR08lpfhyu3B0gT7xpueKtr1SZEEidNTd9TdeXZj/gEhLcEGcMSYeitInzBlCiLGKZxVrcv4RRz/iMg5WhEHQL7eETh0QYm6sH1ghpb+qsQ7XP2s38rao/q57pQQjw8S+VWvpiaIALAN9zl18Li56mZmLrdKrJbzZUA31G12rSZ+xS/bcnOjW2CiDzfgI96VOh0Y9eO966SmcEJWAYbwAa4r9+FKMDmBtA4iXS4nhLvBM/F33HfM4agHcETYKoPdq462Xr5ziOIZLkcXVZs3k66Aj57MvHZnSpwlscpQJGLbQf9LyGS7UiFW+zTnJfBXaRzE78VarmrOMCC0BApoz0GIdwXzxxD7MDKDTOKAH6HQ370yxYOQsOTflr3dHoB1LIj+GfOKva7mHc4vyUpYOys5Zv3wMjeCun0OLT2ZT3VGGW X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: cab747d1-b6ef-47c6-e136-08da0d671f44 X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Mar 2022 07:22:58.8433 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: S4dndHOzppPIYnO/SnUxapljjZhFFsTW3UZQpPlZO5p03nGSUNBat2/5GnIE8YOy X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYAP286MB0075 X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) >>>>> "EZ" == Eli Zaretskii writes: [...] >> Because Lisp values are temporarily moved out to a heap allocated >> buffer which isn't traversed by the stack >> scanner. `record_unwind_protect_ptr_mark` can be seen as a >> generalisation of `record_unwind_protect_ptr` (because that's >> what it is). EZ> I understand that these objects are on the heap, but AFAIU a EZ> reference to them is on the stack, isn't it? Not always. The algorithm merges sublists A and B (which are adjacent to each other on the stack). Doing this entirely in place is very slow (lots of swaps) so we use temp memory of size A (assume A is the shorter list). The idea is to copy the A list to the heap memory, and then use the standard merge algorithm between the heap version of A and (stack version of) B, filling in the space where A used to reside in the stack. The issue is that since we are filling in areas in the stack that were once occupied by A we can end up with some of the original Lisp_Objects residing only in the /copy/ of A on the heap. Once the merging is done, everyone is at home back on the stack. Maybe a simple example: A = (A1, A2) and B=(B1, B2) with merged ordering (A1, B1, A2, B2). Here is the merge sequence: (A1, A2, B1, B2) (start) (A1, A2, B1, B2) (copy A1 from the heap to the first space) (A1, B1, B1, B2) (copy B1 from the stack to the second place) (A1, B1, A2, B2) (copy A2 from the heap to the third place and finish) Notice that in the third step A2 exists only in the heap copy. Best, Andy -- Andrew Cohen From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 08:57:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org, mattiase@acm.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.16481121692152 (code B ref 54532); Thu, 24 Mar 2022 08:57:02 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 08:56:09 +0000 Received: from localhost ([127.0.0.1]:46768 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJGL-0000Ye-FZ for submit@debbugs.gnu.org; Thu, 24 Mar 2022 04:56:09 -0400 Received: from eggs.gnu.org ([209.51.188.92]:56064) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJGJ-0000YP-JR for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 04:56:07 -0400 Received: from [2001:470:142:3::e] (port=52382 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nXJGD-0004OM-Gq; Thu, 24 Mar 2022 04:56:01 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=iaIkWG1PeLkH4jV/DnsUB5Z6ZWwtiLdaq69uNaRo+P4=; b=B3+Cyvf7Ymp9iJMpkm4e aoztSm43W+EtKF7+Nzgmzm5EN4ZMVjGSgw7zl/SwE19JmcNOfHP0AJTGewuajN5kksbNIKnV+qELm sKdNGIm7NwEAGIzDLLLQfnADVq406x29vIF3szGPL9V4ogphp/3JSQs7PMKRiR23qIn57iL/KnEOY k20CJE4D4QBobXNrXVxTD6GkpUjp7lHos5u1Sbe1WihdE9FGIWwgKeMwEBIL/DjhaVfPSt7xtwG9m 9raqqZDYGwOCs+iTyiim8lCjhlIHvcYZia9ARfDm59Odxmm06Jy3JJHIxGMLDLBn2we5qbmxhKJPo YD1Aeus2dIpLBw==; Received: from [87.69.77.57] (port=3387 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nXJG9-0003NU-OU; Thu, 24 Mar 2022 04:55:58 -0400 Date: Thu, 24 Mar 2022 10:55:48 +0200 Message-Id: <83wngjd90r.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <87fsn7erw5.fsf@ust.hk> (message from Andrew Cohen on Thu, 24 Mar 2022 15:22:50 +0800) References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> <87fsn7erw5.fsf@ust.hk> MIME-version: 1.0 Content-type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Andrew Cohen > Cc: Mattias Engdegård , > 54532@debbugs.gnu.org > Date: Thu, 24 Mar 2022 15:22:50 +0800 > > EZ> I understand that these objects are on the heap, but AFAIU a > EZ> reference to them is on the stack, isn't it? > > Not always. The algorithm merges sublists A and B (which are adjacent to > each other on the stack). Doing this entirely in place is very slow > (lots of swaps) so we use temp memory of size A (assume A is the shorter > list). The idea is to copy the A list to the heap memory, and then use > the standard merge algorithm between the heap version of A and (stack > version of) B, filling in the space where A used to reside in the > stack. The issue is that since we are filling in areas in the stack that > were once occupied by A we can end up with some of the original > Lisp_Objects residing only in the /copy/ of A on the heap. Once the > merging is done, everyone is at home back on the stack. If this is just temporary, then how about disabling GC (using inhibit_garbage_collection) during this stage instead? Do we expect to have a lot of garbage generated while this particular part of the code runs? Does this code call some Lisp about whose consing behavior which we cannot assume anything? If we can be certain we won't have a lot of garbage during this stage, disabling GC is just TRT, IMO. In general, having marked Lisp objects should be avoided, because examining those objects in GDB is tricky at best, and because some functions/macros will hit assertions if passed such an object. Two examples are ASIZE and ASET. When inside GC, the use of marked objects is unavoidable, but AFAIU this patch also marks those Lisp objects while they are in the heap, and GC is not necessarily running, is that right? So from my POV we should try to avoid this quite unusual practice, if that's feasible. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 09:18:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 54532@debbugs.gnu.org, mattiase@acm.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164811344812204 (code B ref 54532); Thu, 24 Mar 2022 09:18:02 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 09:17:28 +0000 Received: from localhost ([127.0.0.1]:46815 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJax-0003AU-Dg for submit@debbugs.gnu.org; Thu, 24 Mar 2022 05:17:27 -0400 Received: from mail-os0jpn01on2125.outbound.protection.outlook.com ([40.107.113.125]:1046 helo=JPN01-OS0-obe.outbound.protection.outlook.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJav-00034d-Iw for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 05:17:26 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Vro20CyCFsmNAMfWDXrBIvTJsfaQ6jNzB4YIv/5LMaclbNtXWt54NH7QoYf6MTfogwJpKMwOGpVqlC/Lqz82Nk9OdulELDDyFD8HB0G1G7u7RmIzxSg9f5OmIxl9jVy6JuOTEFR6l6l4YmAJxu5i7DwyDC5WSkpRJERE5sCvA7g8CmLvsvs47Matg3VRHJ63MolWImBxsKxTB2VQ+IToHaWTbWflJhlynvlQ7kOlfG/K0t017JPk/fN4q8sCV+NDsS6duvnwUVZLZ1XniP/vPvpmYhKcIFwhxUFYfL1gBYarcD0e/nxNvWPJ40mAEmI37QnN2VC1nxDKsU3XXNcnYQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=ktcYKqY19iJgUyNaPLCw5tKyeiEERAql3+SyE2N5zr4=; b=NGwX/c/i5cdrRYQijazgx4+ETgeKl1X3Ter5z6GH70lPCWTPd9w9U2OIEqfJBEgGUKV48xcvEo4K3SkcvHS8yz1sa6ye6Nty7ttqN+yZNwzHYfZ1BYRlec5LitvqAtx5h4d4sCXgQ7+eT++oR47un2QLSRH4Mjyag/y7M1vuGFgNywyFTcNfTzDMHnizbDFqJATAeGIaqnWgJyg6qG0fCC5yzSm69AckIWiONduXrePZTiTBX0lXK2OFGYGvP3tx8/RjJyPwa+Hcpb0CWhF6PqG1t0Hsf3gbaWQl9QLGzywV4RSsDTGWUbqbpIrWYfi4/B91YX+lpneNsYd6tr9zKg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=ktcYKqY19iJgUyNaPLCw5tKyeiEERAql3+SyE2N5zr4=; b=U+Oj/UPgT1pUj6UeEdS63cW/vMsRuLrQnpNzWdN8/gKyCgQV9Rglb3/Fvu2IjfrsTBX9HSjzZXlvo5FBckMThXtK6nWuj8Q2YO5o10Wj2jNv9/SNWSOTKPXetIi5V2jR2rwgx8T+6gDubXzDBmQs7hjIfa2RYjityRS0ftnoLMNp6YWuOLnq/uBSnulaPnVw7A73Bmi5bfxIfdwt+qHrHidKrTAl5RgACv0BoNlC0mm0v+T3ASc/9kjAYt0fivmcD/6Qzp0WRnqz45ZCMZ+xpZSt/vUs6Ho7A2rPHx4RAqjiB/Hx6t0r5SEetYmMsdUhVtHOCfC6DHkbLpTqQ6xawg== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by OS3P286MB1060.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:f8::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5102.17; Thu, 24 Mar 2022 09:17:18 +0000 Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717%4]) with mapi id 15.20.5081.025; Thu, 24 Mar 2022 09:17:18 +0000 From: Andrew Cohen References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> <87fsn7erw5.fsf@ust.hk> <83wngjd90r.fsf@gnu.org> Date: Thu, 24 Mar 2022 17:17:08 +0800 In-Reply-To: <83wngjd90r.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 24 Mar 2022 04:56:02 -0400") Message-ID: <871qyrlnfv.fsf@ust.hk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Content-Type: text/plain X-ClientProxiedBy: HK2PR0401CA0001.apcprd04.prod.outlook.com (2603:1096:202:2::11) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 52c845a3-f013-4a81-85c2-08da0d7717b8 X-MS-TrafficTypeDiagnostic: OS3P286MB1060:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: t3hajSVx7HbvcSDUatFX/OItr4ZMpxmeess8ruL0ZvZ6SSsydaN+iki7aKrKA5BoKjs/WnctV5ABaEPMv7/4djURxa6klEsMagOVlQL4rUee1kzXN8umFD3d+cnwd3Br0BfbaCKQYoPLxG1NdCj0AVTyr1/vegohhZXwgw4iLKaO/17SEnsjHI2eNIW3fAbeex99QylDvIpsn65G3HShojWxf9IN4+n9WtKlyuGavuAasLEQQhnOA7rNUCzYMPquDWnSsuSBVRx3ee41EGIC6ESv0y4+tOSfrXyovK1LGzhqC3Biubz0RjU3O+E1aC4AvPdP6rHKLmu/LE8RbUUtY6puXUNAYQwARALWyWh46wHAMK6w/PpIHsvzee1cQ0Ges5426RxPWYnuja7hsL2ByO22DT0aoVR5ovN/fiAgyz6liM5rzrM4gH9+SapyTlmS0n58gZapx7Xx8ZZTFfTPC3kc2PqtY1Sk1gfvC4nijvwhKYPBbMQSv+hvRPVPKwyIQNMRri2vEI0013/+lsJC22sZEMkEd9sg+KvAYVVVhrS3mYXaLj8S6Ve+d6vEsupqbKubwmxdhh+FWXjHVKdXfoAvQ7Re2A5VM8FDpX51TLeQ7x33xPR6d7Fkydk5H9EQDGEmnHgb/Z0UWK9VxmH9Mw== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(66556008)(66476007)(5660300002)(8936002)(4326008)(8676002)(66946007)(6512007)(2906002)(2616005)(316002)(786003)(6916009)(86362001)(6666004)(6486002)(6506007)(38100700002)(26005)(186003)(36756003)(508600001); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: eZ2QDL3Bojat8YlzsMgmCUsfT8cCZ7P7sevhtjDcA7Le3Z1C5s75SHZlcwmRyHE7flwXpCiP2NDXAELKygIIdObYnaSL+W1obKBx5PnRcjVhq/AvMIaK7O0Mu+rSSdt5eoT+5kacSSGwGOyXWamxwL9y2CC9CLPE0yc6heJXz2PEYKHgLNYumA+J+o1cUfsxI7D9lIW5C0H/3EqhQ3SN2MRS9ax6UMc6byKlkCyxxNPZ6ojqLeTHMa6HudFWeXvz7HseuGQE1VpgzVUPaqpQA5BDq6ZG9GtK61MS+ZC2H1LM30mjXjh8yxFFTS+w9HeyKmYgmFNoaltZwPrd/AIvUyz8a4JgKTuzB2N4rqQie4YpmLLSKbLwuTEuDzZWnUBLfafzBK11ckKXCKdL3E7ZoilL3wM/R/Rc3dw+9a6CsBdW9FEoe7SowpbPeH3K2hJKW72xxe/kfzJWozEamO3ckN6DWS3ORbdm4BhCWVgZyWc22vF+nMTGLK1KtbcHzpMAY6G9Daxd73LnLy0sG8QjeCX2Ihc/1oTzWBY/cb76x8jzV3/UYheel/Y6Puzzzp+SewHlmDwIqT/VrrOF+d7+kv5JPhLicjdQrOKYXEGn0IvTcZM9VPRfSDcjCPfHdCvGKpdHUDIGubYNVvRJ0k/HjRM312p191Qglyms+KTCe3ca6fAxDq27eZZrsr1UVpJz8Jw+Ck9EKBo3wrA2b9UuD6auBdcT/PvMSJpoKf+Qpyk4X5x08LJj/R93dZVMQLOrVMQpNfu+FHe2am3gaoprBmdhGZldQTQYobHagP7Mpm178DDwlJLjVUfo/JuSKwn5msaqkW4lRmT2+T+KzemvFFSY2xlvx2k3OLSUMEiDRwIMiuvNn2HiIILV+uBiE4UT33oTr9jSG4TIfXTWnuOC4lm6LpHGDiAQFZPnB38SE015PsNQDpPxBts0gSlR6y36UHmI65+6LidXtHriJXkFnhdvzwEF7v2mlx5ZiSg8kloJCbwGL6WA/GJ+ttgll3Jdd/PDbgN0w6FgQvEky7xNfl/xOjqZ29Qm9AUPzpDMMcLa4eVD7MAlWn5meis5sBrgpANJd8KOt7v/jpmXr171KVXb2i+tPz+WwfB2X3b/ICjyyhOoA8uw7ycGjzoWY8UfrU9C/1yK9IYfA82bLhRgfeJgM+CwPHLpMjmv1cNcYJa8gC4uqVm1hkk72WsOCQPNyLxwEwEPNtS5MhVGavI6eV4mLgtAr51rBA3mtOPVktcBMlo+V+xo0qwFREEnQm7VQko4qjaDXtnuvbAPtMOSbWK+eU2nZGP4pzQR/ZueCbprEBrWe3b4NkYuzoHBcr/CudZh7LlKIlDf+IBmZKIMaOmwiRljkiFhDR/ay7ltld7hqB8sCwu9aHOkdOq4zHg2J9ItTeLqeJOeSb0x4jrp0LvRPH0JvPB6XVODbw0taLU= X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: 52c845a3-f013-4a81-85c2-08da0d7717b8 X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Mar 2022 09:17:17.7677 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: n4ajt4eYne2/B+43hSYTdaZC3wzw+ecKYUZJpYiq//DKfr9yZTjKFYfI8F1MnfMW X-MS-Exchange-Transport-CrossTenantHeadersStamped: OS3P286MB1060 X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) >>>>> "EZ" == Eli Zaretskii writes: [...] EZ> If this is just temporary, then how about disabling GC (using EZ> inhibit_garbage_collection) during this stage instead? I don't see why that wouldn't work, but I would defer to others who understand these issues better then me. EZ> Do we expect to have a lot of garbage generated while this EZ> particular part of the code runs? Does this code call some Lisp EZ> about whose consing behavior which we cannot assume anything? EZ> If we can be certain we won't have a lot of garbage during this EZ> stage, disabling GC is just TRT, IMO. The only lisp that gets called is the predicate used in the merging (deciding which element precedes and which follows); in principle this predicate can be any lisp code so I don't think we can assume much about its behavior, and while doing a lot of consing is probably rare I don't think we can rule it out. EZ> In general, having marked Lisp objects should be avoided, EZ> because examining those objects in GDB is tricky at best, and EZ> because some functions/macros will hit assertions if passed such EZ> an object. Two examples are ASIZE and ASET. When inside GC, EZ> the use of marked objects is unavoidable, but AFAIU this patch EZ> also marks those Lisp objects while they are in the heap, and GC EZ> is not necessarily running, is that right? No, I think they only get marked during the marking phase of a GC. Mattias' implementation simply adds a callback to do the actual marking that is invoked in mark_specpdl: case SPECPDL_UNWIND_PTR: if (pdl->unwind_ptr.mark) pdl->unwind_ptr.mark (pdl->unwind_ptr.arg); break; Best, Andy -- Andrew Cohen From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 09:38:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: acohen@ust.hk, 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164811463214472 (code B ref 54532); Thu, 24 Mar 2022 09:38:01 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 09:37:12 +0000 Received: from localhost ([127.0.0.1]:46820 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJtp-0003km-EP for submit@debbugs.gnu.org; Thu, 24 Mar 2022 05:37:12 -0400 Received: from mail208c50.megamailservers.eu ([91.136.10.218]:57782 helo=mail194c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXJtn-0003kc-1H for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 05:36:56 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1648114612; bh=f5eGMIqO5WyEzSRmJKZIpvWT1hBs5jb/f9ujuspCcxw=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=G0rUqftdrTkwKoDCZzxs8Jwon+L++uNjETSLF4rzo8l5JeYTMzEP6Uz3aurHUco55 eYrBqYbY6XCof2QMEMM5TvYa0+oxj9caT92Q33gxNLxE3yiXKohYd8vAn+z2ZmGZm0 CwzyDGi1fbpqU3g/vOcAYZBzSC4Sj+6E+pS2V7T8= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail194c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 22O9anYZ004945; Thu, 24 Mar 2022 09:36:51 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= In-Reply-To: <831qyretr4.fsf@gnu.org> Date: Thu, 24 Mar 2022 10:36:49 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: <63887D60-7631-4583-A76C-B051FE5D9B78@acm.org> References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F1A.623C3BB4.005E, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 0.3 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 24 mars 2022 kl. 07.42 skrev Eli Zaretskii : > That instance was > at the end of the function, right before it returns, and I wonder what > kind of optimization opportunities that could present. I don't think we need to justify every single `eassume` on the concrete = utility for a compiler; in general, the more information we give it, the = better code it can produce. It just doesn't hurt to do so. In fact, the only reason we have `eassert` at all is for assertions that = may be time-consuming or otherwise affect the execution (that is, = expressions that the compiler just can't optimise away). For anything = else, `eassume` is strictly better since it does all that `eassert` = does, but with the extra optimisation hints. Now in this concrete case, we state that `lastofs` and `ofs` are equal = at the point when we are about to return `ofs`, and that gives the = compiler the option to return `lastofs` instead, should that be more = convenient in some way. The compiler also knows that lastofs >=3D ofs because of the loop = condition, which means that it can deduce that lastofs > ofs can never = occur which can have various uses -- for example, in the statement ptrdiff_t m =3D lastofs + ((ofs - lastofs) >> 1); it would know that the argument being shifted is nonnegative, which = might be useful in instruction selection. And so on. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 24 Mar 2022 09:56:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org, Eli Zaretskii Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164811571716334 (code B ref 54532); Thu, 24 Mar 2022 09:56:01 +0000 Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 09:55:17 +0000 Received: from localhost ([127.0.0.1]:46850 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXKBZ-0004FO-BN for submit@debbugs.gnu.org; Thu, 24 Mar 2022 05:55:17 -0400 Received: from mail1478c50.megamailservers.eu ([91.136.14.78]:60862 helo=mail118c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nXKBW-0004F4-J2 for 54532@debbugs.gnu.org; Thu, 24 Mar 2022 05:55:15 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1648115707; bh=vbyTWcz4P5CPHrZ0FB8IRHtpihQ/PvDGaepsxSrf96Y=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=pv+isnbEtEawhlG+6TfXybT8RVdlobhSG43jpcUVxlh9tY8KChaczKUVTsml7MSmj W2K8Hh5IS+tST5kcBdky+mY+4HpBvBoy8JElGXmU/x2YJb4NrJV4D7HMiOWV3v/vQ6 KsXbMUfb6vG9Imqt8FbP03kDUlLomHSRYOdQZTBA= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail118c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 22O9t403030452; Thu, 24 Mar 2022 09:55:06 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= In-Reply-To: <871qyrlnfv.fsf@ust.hk> Date: Thu, 24 Mar 2022 10:55:03 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> <87fsn7erw5.fsf@ust.hk> <83wngjd90r.fsf@gnu.org> <871qyrlnfv.fsf@ust.hk> X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F15.623C3FFB.000C, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 0.3 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) 24 mars 2022 kl. 10.17 skrev Andrew Cohen : > No, I think they only get marked during the marking phase of a > GC. Mattias' implementation simply adds a callback to do the actual = marking > that is invoked in mark_specpdl: >=20 > case SPECPDL_UNWIND_PTR: > if (pdl->unwind_ptr.mark) > pdl->unwind_ptr.mark (pdl->unwind_ptr.arg); > break; Right -- it's really just a generalisation of the existing = `record_unwind_protect_ptr` and fills a gap that wasn't properly handled = before. The other unwind handlers in the family already take care of = marking: record_unwind_protect: takes a single Lisp_Object, which is marked. record_unwind_protect_array: takes a heap-allocated array of Lisp_Objects, which are all marked. record_unwind_protect_int: takes an int, which does not need marking. and so on. `record_unwind_protect_ptr` stands out because it takes a = generic pointer and unwind function, but does not account for the = possibility that anything referred to by that pointer may need marking. = `record_unwind_protect_ptr_mark` plugs that hole in a very natural way. I don't think we should disable the GC during sorting; the predicate = function is not restricted in what it can do. It could build data = structures, throw, call sort on another sequence, switch threads, and so = on. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Lars Ingebrigtsen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 31 Mar 2022 12:04:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org, Eli Zaretskii Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164872819730762 (code B ref 54532); Thu, 31 Mar 2022 12:04:01 +0000 Received: (at 54532) by debbugs.gnu.org; 31 Mar 2022 12:03:17 +0000 Received: from localhost ([127.0.0.1]:38169 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nZtWG-000800-Kb for submit@debbugs.gnu.org; Thu, 31 Mar 2022 08:03:16 -0400 Received: from quimby.gnus.org ([95.216.78.240]:53484) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nZtWF-0007zg-I2 for 54532@debbugs.gnu.org; Thu, 31 Mar 2022 08:03:15 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Content-Type:MIME-Version:Message-ID:In-Reply-To:Date: References:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=6dxgBruS0N4qzQnnw4ouSUFvF3R53HX9kDdbPz4bzdQ=; b=pI4JEZSrctKgRnLioOgnJ3xcAx ot2ExJ2gwPpWcQEse7L0W5gmsghg5KfylBUDVo4d4A8Kr10lYqFoD/7mOzsc3flU031mhxWgvMJLr w9LCSm/u1kDRI9BkkWlJI+GtGAhl4TZn/f+Bs/7wbyNHXMetovv8Gv/gFlXso1Kf0aRs=; Received: from [84.212.220.105] (helo=xo) by quimby.gnus.org with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nZtW5-0003G0-W6; Thu, 31 Mar 2022 14:03:08 +0200 From: Lars Ingebrigtsen References: <87k0clr12o.fsf@ust.hk> Date: Thu, 31 Mar 2022 14:03:05 +0200 In-Reply-To: <87k0clr12o.fsf@ust.hk> (Andrew Cohen's message of "Wed, 23 Mar 2022 07:59:11 +0800") Message-ID: <871qyi72iu.fsf@gnus.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: Re-skimming this thread, it seems like Eli's questions were answered (but there were a couple of very minor stylistic issues to be fixed). So I guess this is ready for merging now (after fixing those couple issues)? Eli? Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Re-skimming this thread, it seems like Eli's questions were answered (but there were a couple of very minor stylistic issues to be fixed). So I guess this is ready for merging now (after fixing those couple issues)? Eli? -- (domestic pets only, the antidote for overdose, milk.) bloggy blog: http://lars.ingebrigtsen.no From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 31 Mar 2022 13:59:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Lars Ingebrigtsen Cc: acohen@ust.hk, 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164873513527210 (code B ref 54532); Thu, 31 Mar 2022 13:59:02 +0000 Received: (at 54532) by debbugs.gnu.org; 31 Mar 2022 13:58:55 +0000 Received: from localhost ([127.0.0.1]:39344 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nZvKB-00074o-G8 for submit@debbugs.gnu.org; Thu, 31 Mar 2022 09:58:55 -0400 Received: from eggs.gnu.org ([209.51.188.92]:39586) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nZvK9-00074Z-G7 for 54532@debbugs.gnu.org; Thu, 31 Mar 2022 09:58:53 -0400 Received: from [2001:470:142:3::e] (port=58190 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nZvK3-00004s-P7; Thu, 31 Mar 2022 09:58:47 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=ijyIxH5KCmhaSzPvxZk0vzJYvoWjkHIo3zwruQ8OMls=; b=nzzrUZ60wdH1 ab7qU18TteXdB1Kq8sp9cVIPu1fR5ESeZ+LmqwdvgR9jeNPeotl1cwRz1iYLmcpIrqvCPtZejclcp s2mRn64tBTW9Z/tfLjHSRZ51GI5Uh9D+F6ORPhdeX2mumqRnN9PgxuwOaGaWX5h3UT1MH3mJaQG8N LwQJDC2FEdWALvSBQ8rh6+nDiXNB7GWweGPH9a8l6LMSHyFDufmbPMpS1z4toCEbjGUoisfqbx2x+ JdIH8a0DDc5q2/HEcmroKVhBGbwdUN/3mFT2HZ2az5QA1icREV1l/0ButsDo60dIH/OAxtDY9EldI DpdT+pBfxwH68tCer4xl/g==; Received: from [87.69.77.57] (port=2314 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nZvK3-0005wc-5R; Thu, 31 Mar 2022 09:58:47 -0400 Date: Thu, 31 Mar 2022 16:58:57 +0300 Message-Id: <83bkxm6x5q.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <871qyi72iu.fsf@gnus.org> (message from Lars Ingebrigtsen on Thu, 31 Mar 2022 14:03:05 +0200) References: <87k0clr12o.fsf@ust.hk> <871qyi72iu.fsf@gnus.org> X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Lars Ingebrigtsen > Cc: 54532@debbugs.gnu.org, Eli Zaretskii > Date: Thu, 31 Mar 2022 14:03:05 +0200 > > Re-skimming this thread, it seems like Eli's questions were answered > (but there were a couple of very minor stylistic issues to be fixed). > > So I guess this is ready for merging now (after fixing those couple > issues)? Eli? Yes, I think as soon as Andrew comes up with an updated patch, we can install this. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Andrew Cohen Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 31 Mar 2022 23:48:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: 54532@debbugs.gnu.org, Lars Ingebrigtsen Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164877046422196 (code B ref 54532); Thu, 31 Mar 2022 23:48:02 +0000 Received: (at 54532) by debbugs.gnu.org; 31 Mar 2022 23:47:44 +0000 Received: from localhost ([127.0.0.1]:40162 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1na4Vz-0005ln-0x for submit@debbugs.gnu.org; Thu, 31 Mar 2022 19:47:44 -0400 Received: from mail-tycjpn01on2104.outbound.protection.outlook.com ([40.107.114.104]:48801 helo=JPN01-TYC-obe.outbound.protection.outlook.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1na4Vv-0005kn-Ku for 54532@debbugs.gnu.org; Thu, 31 Mar 2022 19:47:41 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Vn1amLmIU386aa46LnCzPD2/sLZ3LP76xmfMVYXYBu0gypDjCLhM3InLBEJqWgzxTpdYGu4K6576daxv85Sb9S/lK4U4Gf4Lfq5G8hOm48nVaYA5nEj3g8UAsVvz6Qt8aiImXoVWNjqYyX0+uFSNaIo9Nxu514NcQn49YnzMsR5w94GdGw1kpnok1Q7RQEabisgHr7MRYwKUK60qYIkxwf32iu/IyoVM/CmCaN7MXXRuY8sm93LzHC/7ymUkGFZk9pgu/ORXUpofFbWfIVIGxThmw0i83gLwxugcAz87eMNrL+5L/O325jfqoJzSqcmupbtlnrjwQ5ZyWnlq0tUjhg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=vIEZYS75oATuve1iHTGqP2aQheJn+dAebd83PXC8anw=; b=V/rTcaRCaRo1gZKqDP5liH44m9sZCtftdhRuuxjbIzPWrWu6RKH/luNoXZgiUjARlx1els4ds7Ly3xi6sokMXojB5/fcxYff3U8Leof4Dh02SlegZCHAis//i/OubA9j2/PvcuHbK8sp73qxJXz199TJ4zygbp7qSQpYOmVNt7b56Vv7y7yAMQahdPVR3CGf4LNqgC1QKGjA7F8LRd1jydd+0E31OnMtfiUbru8pLG/7CLueFB0/K1ZX6IrjC+jZCflO06NUgdWXMfTo5CKkJ4pihJmdDe++afa164NR2CbHlr4qEk/M/7vzMX6R17mzjNPLguZukeuG8EPqx+SJkw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=vIEZYS75oATuve1iHTGqP2aQheJn+dAebd83PXC8anw=; b=BimMfMxDyL6Yo24D3dzgRAyZhDZM5sJK5Rvbmg7xffYAAJlFkWOCTC6KU8I2n2Kht8/eSwJIFiYw+666WckHigeuTJ7QjqldVqktArz89cz8/npOvtbR0SIr5NdvHagJFrPNGTQDr548CkROTSRgvTK1NXQyBgPGInZIEknmbWflcOTmm09jy2Av4t3D0+XVSZ2OuxfeozP4WCa1R48/Nm3oCMjsbepDq3hVIJEeuDj2BrBHxLTofy76D00gvaRwybnRASLgvhZNeutaAK/DRVRqB8SQoM3XLRfS6DwAIXv7WU+qKwHZD3HDsQI2E9eXM/C/B6h/abTw1SP1zEy/Jw== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by TYYP286MB1422.JPNP286.PROD.OUTLOOK.COM (2603:1096:400:de::8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5123.25; Thu, 31 Mar 2022 23:47:31 +0000 Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::255f:b27f:3eaf:717%5]) with mapi id 15.20.5123.025; Thu, 31 Mar 2022 23:47:31 +0000 From: Andrew Cohen References: <87k0clr12o.fsf@ust.hk> <871qyi72iu.fsf@gnus.org> <83bkxm6x5q.fsf@gnu.org> Date: Fri, 01 Apr 2022 07:47:27 +0800 In-Reply-To: <83bkxm6x5q.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 31 Mar 2022 09:58:48 -0400") Message-ID: <87mth5ofao.fsf@ust.hk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Content-Type: multipart/mixed; boundary="=-=-=" X-ClientProxiedBy: HK2P15301CA0016.APCP153.PROD.OUTLOOK.COM (2603:1096:202:1::26) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: f718f248-f16b-4064-479b-08da1370d1f3 X-MS-TrafficTypeDiagnostic: TYYP286MB1422:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: /9nvVccNjf4UKpOoTAYA0ydMYgJKxD/E7B6bp18jS0nx3xtCjLx2D+9MrbLzMj2eHmkjQKO29p3X1wdZ1EjDTpK/0FHilT/UWNutVjPIyoJWuyXrxa9y4xrcZzyeryuQCRe34T62UnOwTtkKkm5DyB/yNAKaE1MISXKksJvmizD76/NoFHv3R13FQJBq+zW5Qi/cT3I3NIPQDqN+C66qjh4X5D0ts7mK12uJok63pnK5T5qlJ8LD03VAG2TdEkqv4ksAmAjaC6ys5+mIUDHeQ7PYxuYknqV82u1CTyEuv+GxBUrwTr5mO2CxyP9KNKhnzkpGU00/X2msBfvz9kp6ot+4V448z8brQTBcfD2rd7rj4f02U2WMniSlBLgPu+2bqZfmBSbiDN6Z3uLQO9QNLuGHxC8LjF8ZeQplHnqKpq+my/V8Bkz3ZOlJXNzHcxDqbHZtkacohmNhpha3TIBFrKDRdvfzK43HSQIst9lf2rYUsBlgkIzrXZdjJFiAHfvgXDfG5lwxG3aq3J2c98sCp8Iw1vnOaoBKCYct7N7NP3sHvifLYJzvZIHlCzPj/OX4Pegx37kurPkxYwqDJ0mt6Jcys9inGybYBb9m/RUHbqxIZzzcybpkb7iZoFsd3NA7dK7MZohAFl1r0rLXdifaKg== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(83380400001)(2616005)(36756003)(186003)(26005)(45080400002)(6512007)(6666004)(53546011)(786003)(316002)(6506007)(6916009)(508600001)(6486002)(86362001)(30864003)(8936002)(2906002)(66556008)(66476007)(5660300002)(8676002)(66946007)(4326008)(38100700002); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: bbW4FF9NeRvug9aDlOAs6rCmQHQ8HpbXVnMOgX6hpWuxEjBmqEY7aKuN1bMq9u1cX7iG4tiHpmYgdsHt2pgnCCFQhRl5Zu9CF3IsEknMVhminGhVrJUVhqqjy3v5w934aAac2/6vH36n+G/9/6zjaYz90Qh1z3Zq5wEDTCxn2uJeMx3W6xdE6RpC6r37UGF6dDeoMoRJTNmX3WC8EMIojQ6hT9Jq6K0QLeNOsYVZY4Q4VRB1tzEj17XT23k6+loUbOU6LJ2sbZ27Xhpk8Lu47+ZUVjM+fZXZXSOz/RQmYzTQLjk5BBkv46H3Ii3pwRnvtTGuytu5NktbGEas/Go2cYSWOfKZcVfhIPzrMYSXcM8R5nqhRL1yC9i6b+94uov6P71MCM7xiQVz/oWXSqhjU9DdYO4DHPBVTJlIlmtF90/xW6wOJBN4u21sV770q0j5NvhFeGPiY6IvcD1wwnJXxWktuh/WSYve4A7zTUJuH2vswPN5Q4/+/6ES++D2P0QfvbO5tclnKpMnRGqC1ATZ2El6ZpR8bDdhbzHCaIbAZ6Vb3sXNmqj+zlBES4jCZrvbLE0g5lON9AF6tl0ukNt+FBjyQOXNl/1m1iZalxhEnY+Baga6Na83lK8oBrWZt+o/k4ukyjvIcDy1GJVJv4Xb3nAiDMivsoH5z5Kza5UZ6P7BiIBGrjPrf6nuKkYoz3s2Egbhpv1F/B2Po5LLokgl4ohntd0yB/Oy1yr0mCTp1bLhvWTrj1V6ijQYgp34b5fY7qb9oU+frAW4r9wqLFD2IBlXJbn0ZsJyxC46ShBmBUnQV1s2xFP5Gb38Loyc0Fe7fa63M8LCBqCHMbFM9KVWz5hB2PKFIvPaPrNsZS6zjlBpSDw7BxQDyh7PPESvZVXoWn/eiU4D7iDFtt5HzxJRy7QCI+7bfaEER2VLYp+MTu+gABey+yB4UqVhbBppKTySRdHPoDnQKfWutYcFm3LYTZ82ER/Wg/v+7q40VkDr7KXA19HOMALK1Sl/7PZTwsSiUOaiNRKA+Z9NGj41Uva0omwgbvD9MUGOnk2T3yH6IKfVePaZ1FxskeedBE/jt4pDMC6Lf7IWhmKoylvXhk+4pRpAk6Jpgcc+q9QhzRTc0h5yUsgowm7Sl4GIn5WeLSfFZv/a3PW+tI/DyvRCw4+RyFD+U+RJVuA3O0gFM69pI/0AMjCT3HYYTA6Dqrt/v9vjTnnFv9pSREe4xHkN+UrjLQ3n8udZvgMV1Fvbc0517cnva7Bi4rBlpx323raWqaBfmHhKWDJzEXCVazVKVd62354E/O+DvLe9Lcs1ZBAZWNkLLKNU5D5vSKjul9gbshkvJX6BmRMxlTuAJT60932TeZ2+Qcd2Y2iA0fi7JZNv6w/BtE2Tuky/oNcBuaOO37xdWKZ17GTm1vLfLos9XsujzTWByIxSLkyaHJJ7pBnXBh7dp8uimDazfAgv06nXTFzLTsBy4GJvDwz2S9rlYQlMFd19xigDZiy1DuPHlKkjraUJSNzrV6hWBcofAD3tdivH7GGiLhJPc/vuHQ2L6go7MQd7wyupvTOHF0UTg/p3eiFTeLrqCNGme/hTLKcJgQL8lijNTMv8+nONP1puRg4DmUr4J2K3TNlsLL2kCoUrb5n5lj3M6u/xexwqFJyZ4BEhH41KcHu0X0y3HwiRFZXUVF0TL+brm58f2e49yC0sV8Kv2AA8/QZPM+kb9/y1JW3zRUpb2dOeTmfeK2ubkge2Xw== X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: f718f248-f16b-4064-479b-08da1370d1f3 X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Mar 2022 23:47:30.8180 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: 77yTWFFvX7ibwD2aXMu1g5Umg2BAS3DUHI4LvsZ4LJi8fnxRda6HYEjWsXSAFuCF X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYYP286MB1422 X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) --=-=-= Content-Type: text/plain >>>>> "EZ" == Eli Zaretskii writes: [...] EZ> Yes, I think as soon as Andrew comes up with an updated patch, EZ> we can install this. Attached is the patch for the items that Eli identified earlier (improvements in comments and breaking one long line). I'll wait for any further changes/comments. Then I think its best to squash this down to 2 commits: one for the GC marking, and all the rest related to sorting. (I'm happy to use more commits if you think the predicate resolution or the unit tests deserve their own patches). Best, Andy --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=patch.diff Content-Description: sort.c diff >From 551352052021c92bf75001b07ad714454aad7706 Mon Sep 17 00:00:00 2001 From: Andrew G Cohen Date: Fri, 1 Apr 2022 07:38:48 +0800 Subject: [PATCH] ; * src/sort.c: Improve comments. --- src/sort.c | 155 +++++++++++++++++++++++++++-------------------------- 1 file changed, 78 insertions(+), 77 deletions(-) diff --git a/src/sort.c b/src/sort.c index 48e106e92d..694d826853 100644 --- a/src/sort.c +++ b/src/sort.c @@ -117,10 +117,10 @@ inorder (const Lisp_Object predicate, const Lisp_Object a, const Lisp_Object b) } -/* BINARYSORT() is a stable binary insertion sort used for sorting the - list starting at LO and ending at HI. On entry, LO <= START <= HI, - and [LO, START) is already sorted (pass START == LO if you don't - know!). Even in case of error, the output slice will be some +/* Sort the list starting at LO and ending at HI using a stable binary + insertion sort algorithm. On entry the sublist [LO, START) (with + START between LO and HIGH) is known to be sorted (pass START == LO + if you are unsure). Even in case of error, the output will be some permutation of the input (nothing is lost or duplicated). */ static void @@ -154,17 +154,18 @@ binarysort (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, } -/* COUNT_RUN() returns the length of the run beginning at LO, in the - slice [LO, HI) with LO < HI. A "run" is the longest +/* Find and return the length of the "run" (the longest non-decreasing sequence or the longest strictly decreasing sequence, with the Boolean *DESCENDING set to 0 in the former - case, or to 1 in the latter. The strictness of the definition of - "descending" is needed so that the caller can safely reverse a - descending sequence without violating stability (strict > ensures - there are no equal elements to get out of order). */ + case, or to 1 in the latter) beginning at LO, in the slice [LO, + HI) with LO < HI. The strictness of the definition of + "descending" ensures there are no equal elements to get out of + order so the caller can safely reverse a descending sequence + without violating stability. */ static ptrdiff_t -count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descending) +count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, + bool *descending) { Lisp_Object pred = ms->predicate; @@ -198,23 +199,24 @@ count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descen } -/* GALLOP_LEFT() locates the proper position of KEY in a sorted +/* Locate and return the proper insertion position of KEY in a sorted vector: if the vector contains an element equal to KEY, return the position immediately to the left of the leftmost equal element. - [GALLOP_RIGHT() does the same except returns the position to the + [GALLOP_RIGHT does the same except it returns the position to the right of the rightmost equal element (if any).] - 'A' is a sorted vector with N elements, starting at A[0]. N must be > 0. + 'A' is a sorted vector of N elements. N must be > 0. - HINT is an index at which to begin the search, 0 <= HINT < N. The closer - HINT is to the final result, the faster this runs. + Elements preceding HINT, a non-negative index less than N, are + skipped. The closer HINT is to the final result, the faster this + runs. The return value is the int k in [0, N] such that A[k-1] < KEY <= a[k] - pretending that *(A-1) is minus infinity and A[N] is plus infinity. IOW, - KEY belongs at index k; or, IOW, the first k elements of A should precede + pretending that *(A-1) precedes all values and *(A+N) succeeds all + values. In other words, the first k elements of A should precede KEY, and the last N-k should follow KEY. */ static ptrdiff_t @@ -254,7 +256,7 @@ gallop_left (merge_state *ms, const Lisp_Object key, Lisp_Object *a, { /* When key <= a[hint], gallop left, until a[hint - ofs] < key <= a[hint - lastofs]. */ - const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ + const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ while (ofs < maxofs) { if (inorder (pred, a[-ofs], key)) @@ -283,18 +285,19 @@ gallop_left (merge_state *ms, const Lisp_Object key, Lisp_Object *a, ptrdiff_t m = lastofs + ((ofs - lastofs) >> 1); if (inorder (pred, a[m], key)) - lastofs = m + 1; /* Here a[m] < key. */ + lastofs = m + 1; /* Here a[m] < key. */ else ofs = m; /* Here key <= a[m]. */ } - eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ + eassume (lastofs == ofs); /* Then a[ofs-1] < key <= a[ofs]. */ return ofs; } -/* GALLOP_RIGHT() is exactly like GALLOP_LEFT(), except that if KEY - already exists in A[0:N], it finds the position immediately to the - right of the rightmost equal value. +/* Locate and return the proper position of KEY in a sorted vector + exactly like GALLOP_LEFT, except that if KEY already exists in + A[0:N] find the position immediately to the right of the rightmost + equal value. The return value is the int k in [0, N] such that @@ -315,7 +318,7 @@ gallop_right (merge_state *ms, const Lisp_Object key, Lisp_Object *a, { /* When key < a[hint], gallop left until a[hint - ofs] <= key < a[hint - lastofs]. */ - const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ + const ptrdiff_t maxofs = hint + 1; /* Here &a[0] is lowest. */ while (ofs < maxofs) { if (inorder (pred, key, a[-ofs])) @@ -338,7 +341,7 @@ gallop_right (merge_state *ms, const Lisp_Object key, Lisp_Object *a, { /* When a[hint] <= key, gallop right, until a[hint + lastofs] <= key < a[hint + ofs]. */ - const ptrdiff_t maxofs = n - hint; /* Here &a[n-1] is highest. */ + const ptrdiff_t maxofs = n - hint; /* Here &a[n-1] is highest. */ while (ofs < maxofs) { if (inorder (pred, key, a[ofs])) @@ -368,9 +371,9 @@ gallop_right (merge_state *ms, const Lisp_Object key, Lisp_Object *a, if (inorder (pred, key, a[m])) ofs = m; /* Here key < a[m]. */ else - lastofs = m + 1; /* Here a[m] <= key. */ + lastofs = m + 1; /* Here a[m] <= key. */ } - eassume (lastofs == ofs); /* Now a[ofs-1] <= key < a[ofs]. */ + eassume (lastofs == ofs); /* Now a[ofs-1] <= key < a[ofs]. */ return ofs; } @@ -411,9 +414,9 @@ merge_markmem (void *arg) } -/* CLEANUP_MEM frees all temp storage. If an exception occurs while - merging it will first relocate any lisp elements in temp storage - back to the original array. */ +/* Free all temp storage. If an exception occurs while merging, + relocate any lisp elements in temp storage back to the original + array. */ static void cleanup_mem (void *arg) @@ -440,9 +443,9 @@ cleanup_mem (void *arg) } -/* MERGE_GETMEM() ensures availability of enough temp memory for NEED - array slots. Any previously allocated memory is first freed, and a - cleanup routine is registered to free memory at the very end, or on +/* Allocate enough temp memory for NEED array slots. Any previously + allocated memory is first freed, and a cleanup routine is + registered to free memory at the very end of the sort, or on exception. */ static void @@ -453,7 +456,7 @@ merge_getmem (merge_state *ms, const ptrdiff_t need) if (ms->a == ms->temparray) { /* We only get here if alloc is needed and this is the first - time, so we set up the unwind. */ + time, so we set up the unwind protection. */ specpdl_ref count = SPECPDL_INDEX (); record_unwind_protect_ptr_mark (cleanup_mem, ms, merge_markmem); ms->count = count; @@ -479,10 +482,10 @@ needmem (merge_state *ms, ptrdiff_t na) } -/* MERGE_LO() stably merges the NA elements starting at SSA with the - NB elements starting at SSB = SSA + NA, in-place. NA and NB must - be positive. We also require that SSA[NA-1] belongs at the end of - the merge, and should have NA <= NB. */ +/* Stably merge (in-place) the NA elements starting at SSA with the NB + elements starting at SSB = SSA + NA. NA and NB must be positive. + Require that SSA[NA-1] belongs at the end of the merge, and NA <= + NB. */ static void merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, @@ -509,9 +512,9 @@ merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, ptrdiff_t min_gallop = ms->min_gallop; for (;;) { - ptrdiff_t acount = 0; /* This holds the # of consecutive times A won. */ + ptrdiff_t acount = 0; /* The # of consecutive times A won. */ - ptrdiff_t bcount = 0; /* This holds the # of consecutive times B won. */ + ptrdiff_t bcount = 0; /* The # of consecutive times B won. */ for (;;) { @@ -540,9 +543,10 @@ merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, } } - /* One run is winning so consistently that galloping may be a huge - win. We try that, and continue galloping until (if ever) - neither run appears to be winning consistently anymore. */ + /* One run is winning so consistently that galloping may be a + huge speedup. We try that, and continue galloping until (if + ever) neither run appears to be winning consistently + anymore. */ ++min_gallop; do { eassume (na > 1 && nb > 0); @@ -558,8 +562,8 @@ merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, na -= k; if (na == 1) goto CopyB; - /* While na==0 is impossible now if the comparison function is - consistent, we shouldn't assume that it is. */ + /* While na==0 is impossible for a consistent comparison + function, we shouldn't assume that it is. */ if (na == 0) goto Succeed; } @@ -603,10 +607,10 @@ merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, } -/* MERGE_HI() stably merges the NA elements starting at SSA with the - NB elements starting at SSB = SSA + NA, in-place. NA and NB must - be positive. We also require that SSA[NA-1] belongs at the end of - the merge, and should have NA >= NB. */ +/* Stably merge (in-place) the NA elements starting at SSA with the NB + elements starting at SSB = SSA + NA. NA and NB must be positive. + Require that SSA[NA-1] belongs at the end of the merge, and NA >= + NB. */ static void merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, @@ -636,8 +640,8 @@ merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, ptrdiff_t min_gallop = ms->min_gallop; for (;;) { - ptrdiff_t acount = 0; /* This holds the # of consecutive times A won. */ - ptrdiff_t bcount = 0; /* This holds the # of consecutive times B won. */ + ptrdiff_t acount = 0; /* The # of consecutive times A won. */ + ptrdiff_t bcount = 0; /* The # of consecutive times B won. */ for (;;) { eassume (na > 0 && nb > 1); @@ -666,8 +670,8 @@ merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, } /* One run is winning so consistently that galloping may be a huge - win. Try that, and continue galloping until (if ever) neither - run appears to be winning consistently anymore. */ + speedup. Try that, and continue galloping until (if ever) + neither run appears to be winning consistently anymore. */ ++min_gallop; do { eassume (na > 0 && nb > 1); @@ -701,8 +705,8 @@ merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, nb -= k; if (nb == 1) goto CopyA; - /* While nb==0 is impossible now if the comparison function - is consistent, we shouldn't assume that it is. */ + /* While nb==0 is impossible for a consistent comparison + function we shouldn't assume that it is. */ if (nb == 0) goto Succeed; } @@ -730,7 +734,7 @@ merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, } -/* MERGE_AT() merges the two runs at stack indices I and I+1. */ +/* Merge the two runs at stack indices I and I+1. */ static void merge_at (merge_state *ms, const ptrdiff_t i) @@ -747,9 +751,9 @@ merge_at (merge_state *ms, const ptrdiff_t i) eassume (na > 0 && nb > 0); eassume (ssa + na == ssb); - /* Record the length of the combined runs; if i is the 3rd-last run - now, also slide over the last run (which isn't involved in this - merge). The current run i+1 goes away in any case. */ + /* Record the length of the combined runs. The current run i+1 goes + away after the merge. If i is the 3rd-last run now, slide the + last run (which isn't involved in this merge) over to i+1. */ ms->pending[i].len = na + nb; if (i == ms->n - 3) ms->pending[i + 1] = ms->pending[i + 2]; @@ -779,10 +783,9 @@ merge_at (merge_state *ms, const ptrdiff_t i) } -/* POWERLOOP() computes the "power" of the first of two adjacent runs - begining at index S1, with the first having length N1 and the - second (starting at index S1+N1) having length N2. The list has - total length N. */ +/* Compute the "power" of the first of two adjacent runs begining at + index S1, with the first having length N1 and the second (starting + at index S1+N1) having length N2. The run has total length N. */ static int powerloop (const ptrdiff_t s1, const ptrdiff_t n1, const ptrdiff_t n2, @@ -824,11 +827,11 @@ powerloop (const ptrdiff_t s1, const ptrdiff_t n1, const ptrdiff_t n2, } -/* FOUND_NEW_RUN() updates the state when a run of length N2 has been - identified. If there's already a stretch on the stack, apply the - "powersort" merge strategy: compute the topmost stretch's "power" - (depth in a conceptual binary merge tree) and merge adjacent runs - on the stack with greater power. */ +/* Update the state upon identifying a run of length N2. If there's + already a stretch on the stack, apply the "powersort" merge + strategy: compute the topmost stretch's "power" (depth in a + conceptual binary merge tree) and merge adjacent runs on the stack + with greater power. */ static void found_new_run (merge_state *ms, const ptrdiff_t n2) @@ -851,9 +854,8 @@ found_new_run (merge_state *ms, const ptrdiff_t n2) } -/* MERGE_FORCE_COLLAPSE() unconditionally merges all stretches on the - stack until only one remains, and returns 0 on success. This is - used at the end of the mergesort. */ +/* Unconditionally merge all stretches on the stack until only one + remains. */ static void merge_force_collapse (merge_state *ms) @@ -871,9 +873,8 @@ merge_force_collapse (merge_state *ms) } -/* MERGE_COMPUTE_MINRUN() computes a good value for the minimum run - length; natural runs shorter than this are boosted artificially via - binary insertion. +/* Compute a good value for the minimum run length; natural runs + shorter than this are boosted artificially via binary insertion. If N < 64, return N (it's too small to bother with fancy stuff). Otherwise if N is an exact power of 2, return 32. Finally, return @@ -907,8 +908,8 @@ reverse_vector (Lisp_Object *s, const ptrdiff_t n) } } -/* TIM_SORT sorts the array SEQ with LENGTH elements in the order - determined by PREDICATE. */ +/* Sort the array SEQ with LENGTH elements in the order determined by + PREDICATE. */ void tim_sort (Lisp_Object predicate, Lisp_Object *seq, const ptrdiff_t length) -- 2.34.1.575.g55b058a8bb --=-=-= Content-Type: text/plain -- Andrew Cohen --=-=-=-- From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 01 Apr 2022 06:28:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org, larsi@gnus.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164879442514834 (code B ref 54532); Fri, 01 Apr 2022 06:28:02 +0000 Received: (at 54532) by debbugs.gnu.org; 1 Apr 2022 06:27:05 +0000 Received: from localhost ([127.0.0.1]:40637 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1naAkS-0003rC-Uf for submit@debbugs.gnu.org; Fri, 01 Apr 2022 02:27:05 -0400 Received: from eggs.gnu.org ([209.51.188.92]:42516) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1naAkR-0003qi-79 for 54532@debbugs.gnu.org; Fri, 01 Apr 2022 02:27:03 -0400 Received: from [2001:470:142:3::e] (port=47774 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1naAkJ-0007Po-TR; Fri, 01 Apr 2022 02:26:56 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=5yCMCnZZtI7sgwqDjiOosRf2Cm8+GMU4TQHExYN5UaI=; b=hx2kL8uSai4t ReydYXKRpHa3Bt8bFi4HrNiwiNxH7tgOjS4TcuxkTrjH4eiR/nmhg0fLYyAnOZude54kWqcaNMild bbRm9RJjyT1O2/fJoalj1ijVbikEJxXcpmweHMQa6tPz2ua4gDWZ14fx9YOvir8I7sGAwJvecGVBP AkJcqO2W+2ZlYJ9em0aJmOYaSTNOQpTOLRsL3aehGOsv4dcxkNfjkP1ILLGZPOJIDBY64fxBx1Ybo 0eCZEIdl+SZ9atnOBawtbaYIuqCvxBZ+2sgRQLhAZYd5oPWWIA0xZK+iWvozs32rpQhApiWaHbB7W 7Y9qjUgcQSe+cWUzNa76ig==; Received: from [87.69.77.57] (port=4467 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1naAk4-0008En-TE; Fri, 01 Apr 2022 02:26:46 -0400 Date: Fri, 01 Apr 2022 09:26:52 +0300 Message-Id: <83pmm15nf7.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: <87mth5ofao.fsf@ust.hk> (message from Andrew Cohen on Fri, 01 Apr 2022 07:47:27 +0800) References: <87k0clr12o.fsf@ust.hk> <871qyi72iu.fsf@gnus.org> <83bkxm6x5q.fsf@gnu.org> <87mth5ofao.fsf@ust.hk> X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Andrew Cohen > Cc: Lars Ingebrigtsen , 54532@debbugs.gnu.org > Date: Fri, 01 Apr 2022 07:47:27 +0800 > > EZ> Yes, I think as soon as Andrew comes up with an updated patch, > EZ> we can install this. > > Attached is the patch for the items that Eli identified earlier > (improvements in comments and breaking one long line). They are fine by me, thanks. > I'll wait for any > further changes/comments. Then I think its best to squash this down to 2 > commits: one for the GC marking, and all the rest related to > sorting. (I'm happy to use more commits if you think the predicate > resolution or the unit tests deserve their own patches). I think even a single commit is okay, unless you care about the history of the development of this. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Stefan Kangas Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 07 Jun 2022 07:07:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: Andrew Cohen , 54532@debbugs.gnu.org, larsi@gnus.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.165458556925978 (code B ref 54532); Tue, 07 Jun 2022 07:07:02 +0000 Received: (at 54532) by debbugs.gnu.org; 7 Jun 2022 07:06:09 +0000 Received: from localhost ([127.0.0.1]:37399 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyTI1-0006kv-G5 for submit@debbugs.gnu.org; Tue, 07 Jun 2022 03:06:09 -0400 Received: from mail-pj1-f41.google.com ([209.85.216.41]:45756) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyTHz-0006kX-Oe for 54532@debbugs.gnu.org; Tue, 07 Jun 2022 03:06:08 -0400 Received: by mail-pj1-f41.google.com with SMTP id w2-20020a17090ac98200b001e0519fe5a8so14619859pjt.4 for <54532@debbugs.gnu.org>; Tue, 07 Jun 2022 00:06:07 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:in-reply-to:references:user-agent :mime-version:date:message-id:subject:to:cc; bh=/QlRW6lcYC8Y2j+/S3VazqwDW3AiKU3iUJmCPqs7oYU=; b=N7jVaP9tK/fbv0NtcI8bHQRYRIXbreSwFEFthNIIvuLr9KgtQvoictGMHchZTjLRVa gVVZQ3xxk18UgGwJT+Jukc+rK7uy+bviqRnAHVpUHiUH6lpW/vaDaQCo2lfBShNj0sN+ OYLzjb6AoWj3fSin6h2VaFLckKQ6zKwO+aO2JeNNdmML4RgokpGtIPDPepr/nYfP99su p3eJocHEbrsjmVpFrjxfcANoNbJeveA6utUyzQd1Msmf0HI2luSerCcAf+dQny7wxODO dUGT4/ciFcL5dZAptejmxNh88X3dS4hFevDqKmKV7iSGCez3R25ZJby4E6VP4H38lUqa 1P8g== X-Gm-Message-State: AOAM530are+x3D5sMP+SpBR15OvmssnwM/u9MCPtVn8IM78Ut6hXPVwX 76cdjP86agJJ6Rv046rJ9fmTpSPNoFfhiVa+XNk= X-Google-Smtp-Source: ABdhPJypUCOcbcSNQtvYWp9IZoYu7feFyoU8Zk1+nEu8rb/HDjCxyc6cKFdmdmwyfCccVPY/qx4svoZqtF5aeUemtLs= X-Received: by 2002:a17:902:e74b:b0:166:4d34:3be3 with SMTP id p11-20020a170902e74b00b001664d343be3mr23818459plf.102.1654585561032; Tue, 07 Jun 2022 00:06:01 -0700 (PDT) Received: from 753933720722 named unknown by gmailapi.google.com with HTTPREST; Tue, 7 Jun 2022 02:06:00 -0500 From: Stefan Kangas In-Reply-To: <83pmm15nf7.fsf@gnu.org> (Eli Zaretskii's message of "Fri, 01 Apr 2022 09:26:52 +0300") References: <87k0clr12o.fsf@ust.hk> <871qyi72iu.fsf@gnus.org> <83bkxm6x5q.fsf@gnu.org> <87mth5ofao.fsf@ust.hk> <83pmm15nf7.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Date: Tue, 7 Jun 2022 02:06:00 -0500 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.5 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.5 (/) Eli Zaretskii writes: >> From: Andrew Cohen >> Cc: Lars Ingebrigtsen , 54532@debbugs.gnu.org >> Date: Fri, 01 Apr 2022 07:47:27 +0800 >> >> EZ> Yes, I think as soon as Andrew comes up with an updated patch, >> EZ> we can install this. >> >> Attached is the patch for the items that Eli identified earlier >> (improvements in comments and breaking one long line). > > They are fine by me, thanks. > >> I'll wait for any >> further changes/comments. Then I think its best to squash this down to 2 >> commits: one for the GC marking, and all the rest related to >> sorting. (I'm happy to use more commits if you think the predicate >> resolution or the unit tests deserve their own patches). > > I think even a single commit is okay, unless you care about the > history of the development of this. That was 9 weeks ago. Any news here? It would be great to get this installed. Thanks in advance. From unknown Sat Aug 16 12:43:38 2025 X-Loop: help-debbugs@gnu.org Subject: bug#54532: [PATCH] sorting Resent-From: Stefan Kangas Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 07 Jun 2022 09:08:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 54532 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Andrew Cohen Cc: 54532@debbugs.gnu.org Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.165459284413327 (code B ref 54532); Tue, 07 Jun 2022 09:08:01 +0000 Received: (at 54532) by debbugs.gnu.org; 7 Jun 2022 09:07:24 +0000 Received: from localhost ([127.0.0.1]:37578 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyVBM-0003Ss-6K for submit@debbugs.gnu.org; Tue, 07 Jun 2022 05:07:24 -0400 Received: from mail-pl1-f181.google.com ([209.85.214.181]:33293) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyVBJ-0003SQ-V4 for 54532@debbugs.gnu.org; Tue, 07 Jun 2022 05:07:22 -0400 Received: by mail-pl1-f181.google.com with SMTP id f9so3852168plg.0 for <54532@debbugs.gnu.org>; Tue, 07 Jun 2022 02:07:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=+HFC1Rh6iHMHulbKkoCWljSgPVlv9gshWq++6eHFcjw=; b=U8t+J00/fATjjzslsqdbJp5etM5rf85aPed8gP83qV/mnMI1DJXlMU4oM2GtivrMqH +DyltHaAaaMOrjco/jvIHSU9ly8OOnpHg8c3q1FaMoqwi5y0KOVFblr2YLYORsGh54pn aKGTTqs/xzi0vW0wdV9rnp6/Jr06de94DU6QCrHonf7YAhabSVXcX/wLvjunexG+dRsh rQLq8OsHpvZpJ4fg29RZPXrZigNuAb+meyimrQjqIITF0oPoCDj+7oKEQODJWXU3dA4a 7oPBr/abAWptXPnXbTxeSZQA1ZplhUI6MW2sIxrs6djUo83fRRgVD3wG4gLEYP2RyNX0 NBMw== X-Gm-Message-State: AOAM533nulVNHIPhPCRPf8luSMtoRGw066+m24bZAB9VEV/lm4YMspUP 04HV1vHV/u11Xv1e1G7v/pVT6poKlzW0JB+h0Ig= X-Google-Smtp-Source: ABdhPJwpBAKhstPvZUYabJscpKR4hYzCwxfu8Wo61H6R829ba1kMQCl6z5UxFYtekFqn0OPvWiSTlRsdE7hh0mqcVKg= X-Received: by 2002:a17:903:248:b0:155:e660:b774 with SMTP id j8-20020a170903024800b00155e660b774mr28599860plh.174.1654592836211; Tue, 07 Jun 2022 02:07:16 -0700 (PDT) MIME-Version: 1.0 References: <87k0clr12o.fsf@ust.hk> <871qyi72iu.fsf@gnus.org> <83bkxm6x5q.fsf@gnu.org> <87mth5ofao.fsf@ust.hk> <83pmm15nf7.fsf@gnu.org> <877d5tgd11.fsf@ust.hk> In-Reply-To: <877d5tgd11.fsf@ust.hk> From: Stefan Kangas Date: Tue, 7 Jun 2022 11:07:04 +0200 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.5 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.5 (/) close 54532 29.1 thanks Andrew Cohen writes: > This has been in master for some time :) > > Commit 9ff2f0be32be621 on Apr 4. Thanks, I'm therefore closing this bug report. From debbugs-submit-bounces@debbugs.gnu.org Tue Jun 07 05:10:43 2022 Received: (at control) by debbugs.gnu.org; 7 Jun 2022 09:10:43 +0000 Received: from localhost ([127.0.0.1]:37616 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyVEZ-0003ZQ-Ge for submit@debbugs.gnu.org; Tue, 07 Jun 2022 05:10:43 -0400 Received: from mail-pj1-f52.google.com ([209.85.216.52]:56172) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nyVEY-0003ZC-7C for control@debbugs.gnu.org; Tue, 07 Jun 2022 05:10:42 -0400 Received: by mail-pj1-f52.google.com with SMTP id e9so4583227pju.5 for ; Tue, 07 Jun 2022 02:10:42 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=S/AhQqZIbVB53ILnoFgAM2kSQBCdhtwy7PPHFaMFr38=; b=f6NSVRFMId01nZZnOzPIUCL+RD4FKwfdfKaeyditVQE6GCXdrySI1qyfOiwLv7wzNw SjKakXQ9F6X8kHV6/FC1KVSWFGYixeqLz9/UJa6KMNwBzb2uLO85DK/CgimGofjBEVYn rDaUAmp0g8ew0FfVHfGAbPPO28hStzoDyaGeTJeHVCLKK5gmFzyNnqHrd4Wh3KxN5bGw hgp4GAhMNfdXuc5b/5/MiZySwb+6ZVtVR+leaGT0pX+vc84FOv9yB2l8d8y/eOcgh3+J lEq1pTBZHgk644I29DLb4Kyk/ip/CtD771SaiJtFNpnACfI4ryUVa3oYZOjIfSlXP0df RWWg== X-Gm-Message-State: AOAM531FYtFQ5X09sZlyl5SBZzUmcy4GtJpjaUwox0cBxZQamQkPlZIU hU8qwbkA4x1piDp/9g6cuVDp4d7mzNECON1dbFrSjI/0V3E= X-Google-Smtp-Source: ABdhPJw2VVvM0mjlTOza+dVlL/i8QPJsoyrSntd5ttmupg3oqAifEdelena0v/11sBmwnJDrjuMKwHvzlO3nKgYSS7o= X-Received: by 2002:a17:90a:b001:b0:1dd:30b9:1a45 with SMTP id x1-20020a17090ab00100b001dd30b91a45mr67083540pjq.132.1654593036518; Tue, 07 Jun 2022 02:10:36 -0700 (PDT) MIME-Version: 1.0 From: Stefan Kangas Date: Tue, 7 Jun 2022 11:10:25 +0200 Message-ID: Subject: To: control Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 3.5 (+++) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: retitle 54532 Faster sorting severity 54532 wishlist thanks Content analysis details: (3.5 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.2 HEADER_FROM_DIFFERENT_DOMAINS From and EnvelopeFrom 2nd level mail domains are different -0.0 SPF_PASS SPF: sender matches SPF record 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (stefankangas[at]gmail.com) -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [209.85.216.52 listed in list.dnswl.org] 0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [209.85.216.52 listed in wl.mailspike.net] 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders 1.0 PDS_TONAME_EQ_TOLOCAL_VSHORT Very short body and From looks like 2 different emails 2.0 BLANK_SUBJECT Subject is present but empty 0.2 FREEMAIL_FORGED_FROMDOMAIN 2nd level domains in From and EnvelopeFrom freemail headers are different -0.0 T_SCC_BODY_TEXT_LINE No description available. X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 2.5 (++) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: retitle 54532 Faster sorting severity 54532 wishlist thanks Content analysis details: (2.5 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at https://www.dnswl.org/, no trust [209.85.216.52 listed in list.dnswl.org] 0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [209.85.216.52 listed in wl.mailspike.net] 0.2 HEADER_FROM_DIFFERENT_DOMAINS From and EnvelopeFrom 2nd level mail domains are different -0.0 SPF_PASS SPF: sender matches SPF record 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (stefankangas[at]gmail.com) 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders 1.0 PDS_TONAME_EQ_TOLOCAL_VSHORT Very short body and From looks like 2 different emails 2.0 BLANK_SUBJECT Subject is present but empty 0.2 FREEMAIL_FORGED_FROMDOMAIN 2nd level domains in From and EnvelopeFrom freemail headers are different -0.0 T_SCC_BODY_TEXT_LINE No description available. -1.0 MAILING_LIST_MULTI Multiple indicators imply a widely-seen list manager retitle 54532 Faster sorting severity 54532 wishlist thanks