Re: Optimizing union.scm

[ludo@gnu.org (Ludovic Courtès)]

Mark H Weaver <mhw@netris.org> skribis:

> Here's a first draft of a new union.scm.

Thanks for being so fast!

> On my YeeLoong 8101B, when building my 155-package profile, it uses
> about 1/14 as much CPU time (25 seconds vs 6 minutes), and about 2/7 as
> much real time (2 minutes vs about 7.17 minutes).  It also handles
> libffi in core-updates properly.  A few notes:

That’s good news, and definitely an incentive to switch to this
implementation.

> * For now, I'm using a hash table, because it turned out to be rather
>   awkward to use a vhash for this.  I can make it purely functional
>   later if it's deemed important.

I would prefer it, but it must not be blocking.

> * I've not yet updated tests/union.scm, which tests internal procedures
>   in union.scm that no longer exist.

Right, the ‘tree-union’ and ‘delete-duplicate-leaves’ tests will have to
be removed.

However, could you add similar tests?  They will have to use the real
‘union-build’, though.  Maybe the ‘with-file-tree’ can be useful to
write the tests.

> * Although I can now run union-build in 2 minutes, another full minute
>   is spent in 'display-search-paths', plus another 30-40 seconds in
>   'guix package' before the profile build begins.

Ouch, you know where to look afterwards.  :-)

> In the end, the total time for "guix package -i" goes from around 8.5
> minutes to around 3.5 minutes: a significant improvement, but there's
> still more code for me to look at trying to optimize.

Excellent!

Some stylistic comments:

> (define (names-in-directory dirname)
>   (let ((dir (opendir dirname)))
>     (let loop ((filenames '()))
>       (match (readdir dir)
>         ((or "." "..")
>          (loop filenames))
>         ((? eof-object?)
>          (closedir dir)
>          filenames)
>         (name
>          (loop (cons name filenames)))))))

Rather use something like:

  (scandir directory (lambda (file)
                       (not (member file '("." "..")))))

‘scandir’ also has the advantage of being deterministic (it sorts
entries.)

> (define (directory? name)
>   (eq? 'directory (stat:type (stat name))))

Rather ‘file-is-directory?’.

> (define* (union-build output inputs
>                       #:key (log-port (current-error-port)))

Docstring.

>   (define (make-link input output)

Maybe ‘symlink*’?  (‘make-link’ sounds like it returns a newly-allocated
object.)

>     (format log-port "`~a' ~~> `~a'~%" input output)
>     (symlink input output))
>
>   (define (union output inputs)
>     (match inputs
>       ((input)
>        ;; There's only one input, so just make a link.
>        (make-link input output))
>       (_
>        (receive (dirs files) (partition directory? inputs)

Rather SRFI-11 let-values.

>          (cond
>           ((null? files)
>
>            ;; All inputs are directories.  Create a new directory
>            ;; where we will merge the input directories.
>            (mkdir output)
>
>            ;; Build a hash table mapping each name to a list of input
>            ;; directories containing that name.
>            (let ((table (make-hash-table)))
>
>              (define (add-to-table! name dir)
>                (let ((handle (hash-create-handle! table name '())))
>                  (set-cdr! handle (cons dir (cdr handle)))))

Rather ‘hash-set!’ (‘set-cdr!’ is doomed, you know ;-)).

>               (format (current-error-port)
>                       "warning: collision encountered: ~{~a ~}~%"
>                       files)
>
>               ;; TODO: Implement smarter strategies.
>               (format (current-error-port)
>                       "warning: arbitrarily choosing ~a~%"
>                       file)

Can we keep that as a separate, possibly inner ‘resolve-collisions’
procedure?  That makes it clear what to extend, when we want to
implement that (the original idea was that ‘union-build’ could be passed
a collision-resolution procedure.)

>               (make-link file output))))
>
>           (else
>            ;; The inputs are a mixture of files and directories
>            (error "union-build: collision between file and directories"
>                   `((files ,files) (dirs ,dirs)))))))))

Same for this one.

I like that it’s smaller that the current union.scm.  :-)

Could you please update it and tests/union.scm, and then I think we’ll
be all set?

Thank you!

Ludo’.