[bug#74654] [PATCH 2/5] packages: Optimize ‘all-packages’.

["Ludovic Courtès" <ludo@gnu.org>]

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 | 30 +++++++++++++++++++-----------
 1 file changed, 19 insertions(+), 11 deletions(-)

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 @@ (define all-packages
   (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))))
-                    '()
+    ;; 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))
 
-                    ;; Dismiss deprecated packages but keep hidden packages.
-                    #:select? (negate package-superseded))
-     eq?)))
+    (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.
-- 
2.46.0