From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andrew Cohen Newsgroups: gmane.emacs.bugs Subject: bug#54532: [PATCH] sorting Date: Thu, 24 Mar 2022 15:22:50 +0800 Message-ID: <87fsn7erw5.fsf@ust.hk> References: <320D86FD-5B2E-4177-9570-A8004A942E8C@acm.org> <831qyretr4.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16256"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: 54532@debbugs.gnu.org, Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Mar 24 08:24:14 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nXHpM-000410-5k for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 24 Mar 2022 08:24:13 +0100 Original-Received: from localhost ([::1]:34192 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nXHpK-0004XA-J0 for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 24 Mar 2022 03:24:10 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:39640) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nXHpC-0004Ww-RM for bug-gnu-emacs@gnu.org; Thu, 24 Mar 2022 03:24:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:52798) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nXHpC-0006Ui-I7 for bug-gnu-emacs@gnu.org; Thu, 24 Mar 2022 03:24:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nXHpC-0004Rb-DT for bug-gnu-emacs@gnu.org; Thu, 24 Mar 2022 03:24:02 -0400 X-Loop: help-debbugs@gnu.org 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 Original-Received: via spool by 54532-submit@debbugs.gnu.org id=B54532.164810658917001 (code B ref 54532); Thu, 24 Mar 2022 07:24:02 +0000 Original-Received: (at 54532) by debbugs.gnu.org; 24 Mar 2022 07:23:09 +0000 Original-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 Original-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; Original-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 Original-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 In-Reply-To: <831qyretr4.fsf@gnu.org> (Eli Zaretskii's message of "Thu, 24 Mar 2022 02:42:48 -0400") X-ClientProxiedBy: HK2P15301CA0017.APCP153.PROD.OUTLOOK.COM (2603:1096:202:1::27) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) 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/MitxejJDhAbFZmMRQmiTiQVsDH6cjVKJ0kvl7n7hEBoMkjIjkTWxIoaHJIlKZpoFBKP6HTICF16gVE n0vTKoYLTxgqhYK4ZvZr9wtFUhFRJham9PKO50kbgk/UPJIfkRseuhCE1jxJ8GhPq9aNVA5wsWQBNqz8aZ8mJM+Cu3ZPmJRrpX 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-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:228861 Archived-At: >>>>> "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