From ed3592a9809fad73e9caee2d321d06446d78c8d2 Mon Sep 17 00:00:00 2001 From: Ludovic Courtès Date: Sun, 11 Jan 2015 23:04:07 +0100 Subject: derivations: Use sets for 'derivations-prerequisites'. This yields a 46% improvement in 'derivation-prerequisites' invocations on the Emacs derivation. * guix/derivations.scm (derivation-prerequisites): Add 'input-set' variable, and use it in iterations. --- guix/derivations.scm | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/guix/derivations.scm b/guix/derivations.scm index ec438e833c..2f015089a3 100644 --- a/guix/derivations.scm +++ b/guix/derivations.scm @@ -31,6 +31,7 @@ (define-module (guix derivations) #:use-module (guix hash) #:use-module (guix base32) #:use-module (guix records) + #:use-module (guix sets) #:export ( derivation? derivation-outputs @@ -162,16 +163,18 @@ (define (derivation-input-output-paths input) (define (derivation-prerequisites drv) "Return the list of derivation-inputs required to build DRV, recursively." - (let loop ((drv drv) - (result '())) - (let ((inputs (remove (cut member <> result) ; XXX: quadratic + (let loop ((drv drv) + (result '()) + (input-set (set))) + (let ((inputs (remove (cut set-contains? input-set <>) (derivation-inputs drv)))) - (fold loop - (append inputs result) - (map (lambda (i) - (call-with-input-file (derivation-input-path i) - read-derivation)) - inputs))))) + (fold2 loop + (append inputs result) + (fold set-insert input-set inputs) + (map (lambda (i) + (call-with-input-file (derivation-input-path i) + read-derivation)) + inputs))))) (define (offloadable-derivation? drv) "Return true if DRV can be offloaded, false otherwise." -- cgit v1.2.3