GNU bug report logs - #49522
[PATCH] weather: Don't look for exported package replacements twice.

Previous Next

Full log

View this message in rfc822 format

From: Christopher Baines <mail <at> cbaines.net>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 49522 <at> debbugs.gnu.org
Subject: [bug#49522] [PATCH] weather: Don't look for exported package replacements twice.
Date: Sun, 01 Aug 2021 16:01:27 +0100

[Message part 1 (text/plain, inline)]

Ludovic Courtès <ludo <at> gnu.org> writes:

> Hi!
>
> Christopher Baines <mail <at> cbaines.net> skribis:
>
>> There could be performance issues with member here, but only if there are lots
>> of replacements.
>>
>> * guix/scripts/weather.scm (all-packages): Return all exported packages, plus
>> non exported replacements, rather than including exported replacements twice.
>
> [...]
>
>> +  "Return the list of packages we are going to query."
>> +  (let* ((packages
>> +          (fold-packages (lambda (package result)
>> +                           (cons package result))
>> +                         '()
>> +
>> +                         ;; Dismiss deprecated packages but keep hidden packages.
>> +                         #:select? (negate package-superseded)))
>> +         (non-exported-replacement-packages
>> +          (fold-packages (lambda (package result)
>> +                           (let ((replacement (package-replacement package)))
>> +                             (if (and replacement
>> +                                      ;; Avoid double couting replacements
>> +                                      ;; that are themselves exported
>> +                                      (not (member replacement packages)))
>> +                                 (cons replacement result)
>> +                                 result)))
>> +                         '()
>> +
>> +                         ;; Dismiss deprecated packages but keep hidden packages.
>> +                         #:select? (negate package-superseded))))
>> +    (append
>> +     packages
>> +     non-exported-replacement-packages)))
>
> Is the goal to delete duplicates?

Not really, the goal is to have a list with no duplicates.

> In that case, how about wrapping the existing expression in
> (delete-duplicates … eq?) ?
>
> (Note that (member x lst) is O(N) is the number of packages, so the code
> above is quadratic in the number of packages, which should be avoided.
> Also, packages cannot be meaningfully compared with ‘equal?’ (which is
> expensive in case of different packages), so ‘eq?’ should be preferred.)

Replacing member with memq seems sensible.

My understanding of delete duplicates is that it's O(N^2), because it
constructs a new list, and keeps searching it in linear time. While that
sounds better, doing a linear search of packages for each replacement
should be quicker, assuming there's only a few replacements compared to
the number of packages.

I'm fine with either though, I don't actually know which is faster, and
it probably doesn't matter anyway. I'll send a patch with a
delete-duplicates approach.

[signature.asc (application/pgp-signature, inline)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.