From 97e7e47d6f1e036e1ed6bd3f428e40d9794a3353 Mon Sep 17 00:00:00 2001
From: Ludovic Courtès <ludo@gnu.org>
Date: Mon, 2 Dec 2024 17:06:52 +0100
Subject: packages: Optimize ‘all-packages’.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

On my laptop, wall-clock time for (all-packages) goes from 27s to 1s.

* gnu/packages.scm (all-packages): Use a hash table to remember visited
packages instead of calling ‘delete-duplicates’ on the final list.

Change-Id: I4aae804656b56ef2095993e91f0572a5891f419f
---
 gnu/packages.scm | 32 ++++++++++++++++++++------------
 1 file changed, 20 insertions(+), 12 deletions(-)

(limited to 'gnu')

diff --git a/gnu/packages.scm b/gnu/packages.scm
index 1af3b8d440..bdd5d21940 100644
--- a/gnu/packages.scm
+++ b/gnu/packages.scm
@@ -258,18 +258,26 @@ is guaranteed to never traverse the same package twice."
   (mlambda ()
     "Return the list of all public packages, including replacements and hidden
 packages, excluding superseded packages."
-    (delete-duplicates
-     (fold-packages (lambda (package result)
-                      (match (package-replacement package)
-                        ((? package? replacement)
-                         (cons* replacement package result))
-                        (#f
-                         (cons package result))))
-                    '()
-
-                    ;; Dismiss deprecated packages but keep hidden packages.
-                    #:select? (negate package-superseded))
-     eq?)))
+    ;; Note: 'fold-packages' never traverses the same package twice but
+    ;; replacements break that (they may or may not be visible to
+    ;; 'fold-packages'), hence this hash table to track visited packages.
+    (define visited (make-hash-table))
+
+    (fold-packages (lambda (package result)
+                     (if (hashq-ref visited package)
+                         result
+                         (begin
+                           (hashq-set! visited package #t)
+                           (match (package-replacement package)
+                             ((? package? replacement)
+                              (hashq-set! visited replacement #t)
+                              (cons* replacement package result))
+                             (#f
+                              (cons package result))))))
+                   '()
+
+                   ;; Dismiss deprecated packages but keep hidden packages.
+                   #:select? (negate package-superseded))))
 
 (define %package-cache-file
   ;; Location of the package cache.
-- 
cgit v1.2.3