[PATCH] weather: Don't look for exported package replacements twice.

  • Done
  • quality assurance status badge
Details
2 participants
  • Ludovic Courtès
  • Christopher Baines
Owner
unassigned
Submitted by
Christopher Baines
Severity
normal

Debbugs page

Christopher Baines wrote 4 years ago
(address . guix-patches@gnu.org)
20210711115638.30207-1-mail@cbaines.net
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.
---
guix/scripts/weather.scm | 35 ++++++++++++++++++++++++-----------
1 file changed, 24 insertions(+), 11 deletions(-)

Toggle diff (48 lines)
diff --git a/guix/scripts/weather.scm b/guix/scripts/weather.scm
index 06312d65a2..0f70dc8460 100644
--- a/guix/scripts/weather.scm
+++ b/guix/scripts/weather.scm
@@ -53,17 +53,30 @@
#:export (guix-weather))
(define (all-packages)
- "Return the list of public packages we are going to query."
- (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)))
+ "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)))
(define (call-with-progress-reporter reporter proc)
"This is a variant of 'call-with-progress-reporter' that works with monadic
--
2.32.0
Ludovic Courtès wrote 4 years ago
(name . Christopher Baines)(address . mail@cbaines.net)(address . 49522@debbugs.gnu.org)
875yx6mdpc.fsf@gnu.org
Hi!

Christopher Baines <mail@cbaines.net> skribis:

Toggle quote (6 lines)
> 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.

[...]

Toggle quote (25 lines)
> + "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?

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.)

Thanks,
Ludo’.
Christopher Baines wrote 4 years ago
(name . Ludovic Courtès)(address . ludo@gnu.org)(address . 49522@debbugs.gnu.org)
8735rtb454.fsf@cbaines.net
Ludovic Courtès <ludo@gnu.org> writes:

Toggle quote (39 lines)
> Hi!
>
> Christopher Baines <mail@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.

Toggle quote (8 lines)
> 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.
-----BEGIN PGP SIGNATURE-----

iQKlBAEBCgCPFiEEPonu50WOcg2XVOCyXiijOwuE9XcFAmEGt0dfFIAAAAAALgAo
aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDNF
ODlFRUU3NDU4RTcyMEQ5NzU0RTBCMjVFMjhBMzNCMEI4NEY1NzcRHG1haWxAY2Jh
aW5lcy5uZXQACgkQXiijOwuE9XfqpA/+MsrcuvhMddOGbTZc3YFs95esZrdtLz7K
j0rnL0FVYxbkZQnaCLROwMIMSo6QY5S62ZnVmMaCkwMkQmiGa36Py9cBdCbWVn9i
S+FwnGEfBEOsxUcn0BLKbi36Uv3S3MAJPeW5XFztFGCpSoh6npEo74P+053Q86KS
Q8iQ1lZhZKyux7pX/vANDuVwJl2UWR2ZH1nBTpW7ZcIc+Q5aBN40ntuMs6oMQJyG
eq9ozowNc3myo2xc8uQMC48cXr8Zto0jRqd8xC5HWouYhEbn4S95dIl6kadIkzKf
eVxIQCpI7yJBVyZTlOQTDWtZJ3rViLQ+38sSYYV0qBhqY8wzefSHENkLpBe9G9KA
R53YRwJDk194hNFLcBs3uGkkya4Dm81q4vAUpbWhmczV3AvV87SorWxuPInnszuR
Fq7JsINMG4A7cO5/ggQBBG8FTGuQaxCAEVCL3TwPvR+/JC6TumW+lVNDlDkndm79
Q7Mzt9ku3gQK6YA6dzdkoWLK7gLoI4UgzaGlus8B4jnNrjnIdkcnkqNn98qny/08
jfVnUUDi/NrObLT2Qv+3S+WMGR208oFyNBIu3NeeSX06T1TaDMbrGnxBHPL/+Xsk
tEA3foBTjknXzWC/Cp5kwoSnK+06jSn+4yzd4SF+3OL0cYEK0Yx3MXhhWlzgSBXe
B1CpezBeYLQ=
=aBX7
-----END PGP SIGNATURE-----

Christopher Baines wrote 4 years ago
[PATCH] weather: Don't look for exported package replacements twice.
(address . 49522@debbugs.gnu.org)
20210801154534.22051-1-mail@cbaines.net
* guix/scripts/weather.scm (all-packages): Delete duplicates, so that exported
replacements aren't included twice.
---
guix/scripts/weather.scm | 22 ++++++++++++----------
1 file changed, 12 insertions(+), 10 deletions(-)

Toggle diff (35 lines)
diff --git a/guix/scripts/weather.scm b/guix/scripts/weather.scm
index 06312d65a2..60a697d1ac 100644
--- a/guix/scripts/weather.scm
+++ b/guix/scripts/weather.scm
@@ -54,16 +54,18 @@
(define (all-packages)
"Return the list of public packages we are going to query."
- (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)))
+ (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?))
(define (call-with-progress-reporter reporter proc)
"This is a variant of 'call-with-progress-reporter' that works with monadic
--
2.32.0
Ludovic Courtès wrote 4 years ago
(name . Christopher Baines)(address . mail@cbaines.net)(address . 49522@debbugs.gnu.org)
87tuj456ho.fsf_-_@gnu.org
Hi,

Christopher Baines <mail@cbaines.net> skribis:

Toggle quote (3 lines)
> * guix/scripts/weather.scm (all-packages): Delete duplicates, so that exported
> replacements aren't included twice.

LGTM, and apologies for the delay!

Ludo’.
Christopher Baines wrote 4 years ago
(name . Ludovic Courtès)(address . ludo@gnu.org)(address . 49522-done@debbugs.gnu.org)
87a6kuqacm.fsf@cbaines.net
Ludovic Courtès <ludo@gnu.org> writes:

Toggle quote (9 lines)
> Hi,
>
> Christopher Baines <mail@cbaines.net> skribis:
>
>> * guix/scripts/weather.scm (all-packages): Delete duplicates, so that exported
>> replacements aren't included twice.
>
> LGTM, and apologies for the delay!

Great, I've pushed this now as 9540323458de87b0b8aa421e449a4fe27af7c393.
-----BEGIN PGP SIGNATURE-----

iQKlBAEBCgCPFiEEPonu50WOcg2XVOCyXiijOwuE9XcFAmEx6hlfFIAAAAAALgAo
aXNzdWVyLWZwckBub3RhdGlvbnMub3BlbnBncC5maWZ0aGhvcnNlbWFuLm5ldDNF
ODlFRUU3NDU4RTcyMEQ5NzU0RTBCMjVFMjhBMzNCMEI4NEY1NzcRHG1haWxAY2Jh
aW5lcy5uZXQACgkQXiijOwuE9XeVCQ/+KEjg7vpOtpTWUobZEUe3mzByunLMYJeA
RDdT3UyEUOJ6z+GRUZXYVt31tGE4HHMl/shzpW0+pMNYiC5y5/9deIlWipbikoCS
lZrsvYhDuKJPFDKzkcYs4OGFafOXCjbA9AjjQ6wYQSkj6YaHfIbRV1e+l0TYYYyR
KOi79YVbePxnWEpwZLVtO+3W93+GX3B8/D0fciIbV6l2O+vbLP4F6j0KlPEhuArK
nWvNuZtqCEpukq8q+/evaqWkyab5ZzQ5Y3UzBd//S0d3K25aKBENraoXYtU1f9tu
SEcpyltI+y2Pn513JkskffL4pvUomGWUvaVYiXA1o3XBGHx6F1YnMtn1CKsDH69w
s448eE0/exa0cCBErYQfxGh9Q+kRhHLfODoGj7O2Mo+fD2jEC5YYxExu7ETLxkcu
Lkn51CUOEHMC05qtTAqkGFJ5tmVW9N2/qMtfzgJuptMMX0so3F6hQ5VDIaYWKAaY
MDj+PFFQp13NUQr77Hrv7aExgAHxO3Su0n37ho3ouo/l+5Vfmg7xvr+8bNe42h6H
mPkBqPL93cTPHF0pA3Dy+/Z2v5B/VG3AvDlyaIMxjl8Oqq0Sl89bN1aYxK41wEjy
qdys5YtH8q5WQHMRwSOcACqCsaB1UfaLgXxBVnMH3icPD6h9kBXoWhOlOMkqHqUP
qaJ/pz44MNU=
=Yzwt
-----END PGP SIGNATURE-----

Closed
?
Your comment

This issue is archived.

To comment on this conversation send an email to 49522@debbugs.gnu.org

To respond to this issue using the mumi CLI, first switch to it
mumi current 49522
Then, you may apply the latest patchset in this issue (with sign off)
mumi am -- -s
Or, compose a reply to this issue
mumi compose
Or, send patches to this issue
mumi send-email *.patch
You may also tag this issue. See list of standard tags. For example, to set the confirmed and easy tags
mumi command -t +confirmed -t +easy
Or, remove the moreinfo tag and set the help tag
mumi command -t -moreinfo -t +help