From unknown Sat Jun 14 18:03:34 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#68271 <68271@debbugs.gnu.org> To: bug#68271 <68271@debbugs.gnu.org> Subject: Status: [PATCH 0/3] Make some deduplicating speedups. Reply-To: bug#68271 <68271@debbugs.gnu.org> Date: Sun, 15 Jun 2025 01:03:34 +0000 retitle 68271 [PATCH 0/3] Make some deduplicating speedups. reassign 68271 guix-patches submitter 68271 Christopher Baines severity 68271 normal tag 68271 patch thanks From debbugs-submit-bounces@debbugs.gnu.org Fri Jan 05 15:50:53 2024 Received: (at submit) by debbugs.gnu.org; 5 Jan 2024 20:50:53 +0000 Received: from localhost ([127.0.0.1]:58025 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLr9Z-00040d-Gw for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:50:53 -0500 Received: from lists.gnu.org ([2001:470:142::17]:57158) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLr9U-00040M-7T for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:50:52 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rLr9I-0005Pb-R4 for guix-patches@gnu.org; Fri, 05 Jan 2024 15:50:37 -0500 Received: from mira.cbaines.net ([212.71.252.8]) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rLr9H-0002ym-Ea for guix-patches@gnu.org; Fri, 05 Jan 2024 15:50:36 -0500 Received: from localhost (unknown [217.155.61.229]) by mira.cbaines.net (Postfix) with ESMTPSA id D1BE627BBE2 for ; Fri, 5 Jan 2024 20:50:33 +0000 (GMT) Received: from felis (localhost [127.0.0.1]) by localhost (OpenSMTPD) with ESMTP id ec58259b for ; Fri, 5 Jan 2024 20:50:33 +0000 (UTC) User-agent: mu4e 1.10.7; emacs 29.1 From: Christopher Baines To: guix-patches@gnu.org Subject: [PATCH 0/3] Make some deduplicating speedups. Date: Fri, 05 Jan 2024 20:50:02 +0000 Message-ID: <87h6jrqzc7.fsf@cbaines.net> MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha512; protocol="application/pgp-signature" Received-SPF: pass client-ip=212.71.252.8; envelope-from=mail@cbaines.net; helo=mira.cbaines.net X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, 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: 0.9 (/) X-Debbugs-Envelope-To: submit 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.1 (/) --=-=-= Content-Type: text/plain Christopher Baines (3): guix: utils: Add delete-duplicates/sort. guix: derivations: Use delete-duplicates/sort. guix: packages: Speed up deduplicating inputs. guix/derivations.scm | 10 ++++++---- guix/packages.scm | 23 +++++++++++++++++++---- guix/utils.scm | 28 ++++++++++++++++++++++++++++ 3 files changed, 53 insertions(+), 8 deletions(-) --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQKlBAEBCgCPFiEEPonu50WOcg2XVOCyXiijOwuE9XcFAmWYa5hfFIAAAAAALgAo aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDNF ODlFRUU3NDU4RTcyMEQ5NzU0RTBCMjVFMjhBMzNCMEI4NEY1NzcRHG1haWxAY2Jh aW5lcy5uZXQACgkQXiijOwuE9Xd0ww//a5t0bHlFnCTiDMFqHSdw22JQ2UGs+HHb Fu3n2KFmFBkmkcnRehpnm1AM3s5EvKPL54CIIgIa79feW3pvNPKov+tCLE8xszzg lTjlEr8E3M8zr1kyfAgPwASZ1+DHmyIlfLeAViwnhLShx1Oj3tR5vIuLYdvrt4JA 5IRCSTnua7bleSm3zXOXaHFyblcau1EN64nD0z2lhBQXdzkyYfcr14+Qv/m7YlXH NdaOTnpI51BkUTPEw1msH29/S2X2qGoju7hMEo6a5RCg/ZerCGR4kuKdyMqrueXP XjhA4qTZZP/Bk4qx0SDq7vmGLG02bc03h4RUn0FUhK/6/bLbwU4VBJ3bppYPlSK5 kr8j0UmxgUUGBh6xcJ17ShkTc1F1+uIcjhpQKApQdH5It0IjTydMH+fabrW9ggOc K3y/LWYRRp/ZO0vz9oMqq8YJ2ORYKWKEG0lLUCGkvGFzzDgsYdeWKGZB163+aujC 6IEwg5fMH950fW09LTaV+MZPDQgYGKgkRW8QfiLcknqJ4Ap46y2thusZE1euJtIk zX0/FaBWQ9dGljdpG64RxU9e7KxCvBZs4Nr0C3ZUvqMTFPzMwLMdNte8ilF/5LD2 5TxTSsK3dHJsQFxz80p9I4IlreMw0ihg43ydN5cspKSMiyroF17xduBWsSbLLk61 VJ90VerJmbA= =iBqK -----END PGP SIGNATURE----- --=-=-=-- From debbugs-submit-bounces@debbugs.gnu.org Fri Jan 05 15:53:31 2024 Received: (at 68271) by debbugs.gnu.org; 5 Jan 2024 20:53:31 +0000 Received: from localhost ([127.0.0.1]:58036 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC7-00045b-Ep for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:31 -0500 Received: from mira.cbaines.net ([212.71.252.8]:43068) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC5-00045K-90 for 68271@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:30 -0500 Received: from localhost (unknown [217.155.61.229]) by mira.cbaines.net (Postfix) with ESMTPSA id 94C4E27BBE2 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:23 +0000 (GMT) Received: from localhost (localhost [local]) by localhost (OpenSMTPD) with ESMTPA id 3df7c8f0 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:22 +0000 (UTC) From: Christopher Baines To: 68271@debbugs.gnu.org Subject: [PATCH 1/3] guix: utils: Add delete-duplicates/sort. Date: Fri, 5 Jan 2024 20:53:20 +0000 Message-ID: X-Mailer: git-send-email 2.41.0 MIME-Version: 1.0 X-Debbugs-Cc: Christopher Baines , Josselin Poiret , Ludovic Courtès , Mathieu Othacehe , Ricardo Wurmus , Simon Tournier , Tobias Geerinckx-Rice Content-Transfer-Encoding: 8bit X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 68271 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 (-) Similar to delete-duplicates, but sorts the list first and then compares the pairs in the list. This is faster than delete-duplicates for larger lists. * guix/utils.scm (delete-duplicates): New procedure. Change-Id: Ibc2897cdb7c76be0d0e099bc47fee005a88bea2e --- guix/utils.scm | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) diff --git a/guix/utils.scm b/guix/utils.scm index e4e9d922e7..c1c967ee6c 100644 --- a/guix/utils.scm +++ b/guix/utils.scm @@ -146,6 +146,8 @@ (define-module (guix utils) edit-expression delete-expression + delete-duplicates/sort + filtered-port decompressed-port call-with-decompressed-port @@ -502,6 +504,32 @@ (define (delete-expression source-properties) "Delete the expression specified by SOURCE-PROPERTIES." (edit-expression source-properties (const "") #:include-trailing-newline? #t)) + +;;; +;;; Lists. +;;; + +(define* (delete-duplicates/sort unsorted-lst less #:optional (equal? eq?)) + (if (null? unsorted-lst) + unsorted-lst + (let ((sorted-lst (sort unsorted-lst + ;; Sort in the reverse order + (lambda (a b) (eq? #f (less a b)))))) + (let loop ((lst (cdr sorted-lst)) + (last-element (car sorted-lst)) + (result (list (car sorted-lst)))) + (if (null? lst) + result + (let ((current-element (car lst))) + (if (equal? current-element last-element) + (loop (cdr lst) + last-element + result) + (loop (cdr lst) + current-element + (cons current-element + result))))))))) + ;;; ;;; Keyword arguments. base-commit: deeb7d1f53d7ddfa977b3eadd760312bbd0a2509 -- 2.41.0 From debbugs-submit-bounces@debbugs.gnu.org Fri Jan 05 15:53:32 2024 Received: (at 68271) by debbugs.gnu.org; 5 Jan 2024 20:53:32 +0000 Received: from localhost ([127.0.0.1]:58038 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC7-00045h-Py for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:32 -0500 Received: from mira.cbaines.net ([212.71.252.8]:43070) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC5-00045L-8w for 68271@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:30 -0500 Received: from localhost (unknown [217.155.61.229]) by mira.cbaines.net (Postfix) with ESMTPSA id E941127BBE9 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:23 +0000 (GMT) Received: from localhost (localhost [local]) by localhost (OpenSMTPD) with ESMTPA id 8acfac1b for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:22 +0000 (UTC) From: Christopher Baines To: 68271@debbugs.gnu.org Subject: [PATCH 2/3] guix: derivations: Use delete-duplicates/sort. Date: Fri, 5 Jan 2024 20:53:21 +0000 Message-ID: X-Mailer: git-send-email 2.41.0 In-Reply-To: References: MIME-Version: 1.0 X-Debbugs-Cc: Christopher Baines , Josselin Poiret , Ludovic Courtès , Mathieu Othacehe , Ricardo Wurmus , Simon Tournier , Tobias Geerinckx-Rice Content-Transfer-Encoding: 8bit X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 68271 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 (-) As this seems to be a small speedup, as tested by computing derivations for all packages targeting i586-pc-gnu. * guix/derivations.scm (derivation/masked-inputs): Use delete-duplicates/sort. Change-Id: I9ec963c10e67a525037c346f44c92a87376935c5 --- guix/derivations.scm | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/guix/derivations.scm b/guix/derivations.scm index 9fec7f4f0b..29c7ef9a5c 100644 --- a/guix/derivations.scm +++ b/guix/derivations.scm @@ -745,10 +745,12 @@ (define (derivation/masked-inputs drv) (make-derivation-input hash sub-drvs)))) inputs))) (make-derivation outputs - (sort (delete-duplicates inputs) - (lambda (drv1 drv2) - (string) id 1rLrCC-00045z-5h for submit@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:51 -0500 Received: from mira.cbaines.net ([2a01:7e00:e000:2f8:fd4d:b5c7:13fb:3d27]:47199) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rLrC7-00045N-B8 for 68271@debbugs.gnu.org; Fri, 05 Jan 2024 15:53:34 -0500 Received: from localhost (unknown [217.155.61.229]) by mira.cbaines.net (Postfix) with ESMTPSA id 30C1B27BBEA for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:24 +0000 (GMT) Received: from localhost (localhost [local]) by localhost (OpenSMTPD) with ESMTPA id 0c47e6c0 for <68271@debbugs.gnu.org>; Fri, 5 Jan 2024 20:53:23 +0000 (UTC) From: Christopher Baines To: 68271@debbugs.gnu.org Subject: [PATCH 3/3] guix: packages: Speed up deduplicating inputs. Date: Fri, 5 Jan 2024 20:53:22 +0000 Message-ID: <7bb6eeca77516fdd01e9b0b98eb9e21ac87c7509.1704488002.git.mail@cbaines.net> X-Mailer: git-send-email 2.41.0 In-Reply-To: References: MIME-Version: 1.0 X-Debbugs-Cc: Christopher Baines , Josselin Poiret , Ludovic Courtès , Mathieu Othacehe , Ricardo Wurmus , Simon Tournier , Tobias Geerinckx-Rice Content-Transfer-Encoding: 8bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 68271 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 (-) Use delete-duplicates/sort rather than delete-duplicates, as this seems to perform a little better, at least when testing by computing derivations targeting i586-pc-gnu for all packages. * guix/packages.scm (inputcross-derivation): Use deduplicate-inputs. Change-Id: Ic47b50aa52f11d701e5aefa2a095219e3a98cfd1 --- guix/packages.scm | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-) diff --git a/guix/packages.scm b/guix/packages.scm index 930b1a3b0e..09dc88e2af 100644 --- a/guix/packages.scm +++ b/guix/packages.scm @@ -1889,6 +1889,21 @@ (define (input=? input1 input2) (derivation=? obj1 obj2)) (equal? obj1 obj2)))))))) +(define (inputderivation bag #:optional context) "Return the derivation to build BAG for SYSTEM. Optionally, CONTEXT can be a package object describing the context in which the call occurs, for improved @@ -1911,7 +1926,7 @@ (define* (bag->derivation bag #:optional context) ;; that lead to the same derivation. Delete those duplicates to avoid ;; issues down the road, such as duplicate entries in '%build-inputs'. (apply (bag-build bag) (bag-name bag) - (delete-duplicates input-drvs input=?) + (deduplicate-inputs input-drvs) #:search-paths paths #:outputs (bag-outputs bag) #:system system (bag-arguments bag))))) @@ -1951,9 +1966,9 @@ (define* (bag->cross-derivation bag #:optional context) all)))) (apply (bag-build bag) (bag-name bag) - #:build-inputs (delete-duplicates build-drvs input=?) - #:host-inputs (delete-duplicates host-drvs input=?) - #:target-inputs (delete-duplicates target-drvs input=?) + #:build-inputs (deduplicate-inputs build-drvs) + #:host-inputs (deduplicate-inputs host-drvs) + #:target-inputs (deduplicate-inputs target-drvs) #:search-paths paths #:native-search-paths npaths #:outputs (bag-outputs bag) -- 2.41.0 From debbugs-submit-bounces@debbugs.gnu.org Fri Jan 12 08:54:01 2024 Received: (at 68271) by debbugs.gnu.org; 12 Jan 2024 13:54:01 +0000 Received: from localhost ([127.0.0.1]:35216 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rOHyz-0008Fq-A6 for submit@debbugs.gnu.org; Fri, 12 Jan 2024 08:54:01 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:36810) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rOHyx-0008Fc-2x for 68271@debbugs.gnu.org; Fri, 12 Jan 2024 08:54:00 -0500 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rOHyq-0001LQ-HZ; Fri, 12 Jan 2024 08:53:52 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-Version:Date:References:In-Reply-To:Subject:To: From; bh=c4JbLNJ7In3P2B6B1lKm+fHIhkAAsb4pISt/ruXSRZw=; b=D37tEVyFiGqSXa3n1uT2 2Y4HLdcsCFd03dkVdxHLdDsQkDyWqxZVau0vZgHgLXBzbGj5fuavxbjNlcBxJVhFtF1k7oezHRhyd WKY+OYB+GnNM/JhCinzB5CdlkKXievM1GS/iC97jKbntjoiXJcsKuVlyUk8Ap9d/nlvg7jAz4jsX1 vN8Hx9gUC0k/7I2V/JDT+PYYyHLwIg0pjtfY7tXXNX4p/z0WKYBz/viBwGxNu0UH950C45zhgXWXR GtiNsjWoeBXxiuu4b4mAHFORrVznXNJ9xsTfGghrb7MAVU4I2p8KIjTuidJG9dnsTc59PP0quLpih eb/QBrvSF9DUyg==; From: =?utf-8?Q?Ludovic_Court=C3=A8s?= To: Christopher Baines Subject: Re: [bug#68271] [PATCH 1/3] guix: utils: Add delete-duplicates/sort. In-Reply-To: (Christopher Baines's message of "Fri, 5 Jan 2024 20:53:20 +0000") References: <87h6jrqzc7.fsf@cbaines.net> Date: Fri, 12 Jan 2024 14:53:43 +0100 Message-ID: <87h6jik68o.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 68271 Cc: Josselin Poiret , Simon Tournier , Mathieu Othacehe , Tobias Geerinckx-Rice , 68271@debbugs.gnu.org, Ricardo Wurmus , Christopher Baines 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 (---) Christopher Baines skribis: > Similar to delete-duplicates, but sorts the list first and then compares = the > pairs in the list. This is faster than delete-duplicates for larger lists. We=E2=80=99re dealing with small lists here though (derivation inputs). Di= d you try to time the benefit? There=E2=80=99s a complexity/benefit tradeoff and I wonder if it cuts it. > +(define* (delete-duplicates/sort unsorted-lst less #:optional (equal? eq= ?)) > + (if (null? unsorted-lst) > + unsorted-lst This =E2=80=98if=E2=80=99 is unnecessary. > + (let ((sorted-lst (sort unsorted-lst > + ;; Sort in the reverse order > + (lambda (a b) (eq? #f (less a b)))))) Just: (negate less). > + (let loop ((lst (cdr sorted-lst)) > + (last-element (car sorted-lst)) > + (result (list (car sorted-lst)))) > + (if (null? lst) > + result > + (let ((current-element (car lst))) Please follow the convention of using =E2=80=98match=E2=80=99 rather than c= ar caddr caddddar (info "(guix) Data Types and Pattern Matching"): (match lst (() result) ((head . tail) =E2=80=A6)) Ludo=E2=80=99.