Re: ice-9 match penalty depending on pattern?
Hey, Simon Tournier skribis: > Re ‘match’ penalty: when using ellipses in patterns, the generated > code checks for “proper lists”, which is O(n). The trick is to > instead match a pair: > > ✔ (match lst ((head . tail) …)) > ❎ (match lst ((head tail ...) …)) To clarify, my message should not be understood as “never use ellipses in ‘match’ patterns”. Whether using ellipses is a “penalty” depends on the context. In some cases I use ellipses anyway because it’s more accurate, more pleasant to the eye, because the input list is small, and/or because this is not performance-critical code. Having a disjoint type for proper lists would avoid this problem, as I mentioned on the Fediverse, but we’re not there yet… Ludo’.
Re: ice-9 match penalty depending on pattern?
Hi, On mer., 07 févr. 2024 at 10:41, Carlo Zancanaro wrote: >> Why not? Do I miss something in the implementation of ’match’? > > The only reason I can think of would be if these matches are sometimes > provided improper lists, which need to fail these match conditions. That > seems unlikely to me, but it should be clear from looking at the other > match clauses in each case. Well, I have not pruned the list returned by just grepping. :-) And I have just grepped with the term ’head’, ’tail’ and ’\.\.\.’ Somehow, my question is twofold: 1. Is the “expensive” check worth for such case: (match paths ((head tail ...) (if (visited? head) (loop tail visited result) (call-with-values (lambda () (loop (references store head) (visit head) result)) (lambda (visited result) (loop tail visited (cons head result)) (() (values visited result) seen in ’topologically-sorted’ procedure from (guix store) module. 2. Is the “expensive” check worth for such multi-cases: (match sexp ((? string? str) (let ((prefix "swh:1:dir:")) (if (string-prefix? prefix str) (cons (string-drop str (string-length prefix)) ids) ids))) ((head tail ...) (loop tail (loop head ids))) (_ ids)) seen in ’lookup-disarchive-spec’ from (guix lint). Well, I am not saying to rely on ’car’ and ’cdr’. Instead, I am asking what is the idiomatic Guile pattern matching for Guile? My main concern is about chasing the unnecessary checks for making Guix a bit faster. :-) Cheers, simon
Re: ice-9 match penalty depending on pattern?
> ./guix/docker.scm:261: (((head ...) (tail ...) id) This one is not like the others. However, looking at the context I think the pattern could just be (head tail id). > Why not? Do I miss something in the implementation of ’match’? The only reason I can think of would be if these matches are sometimes provided improper lists, which need to fail these match conditions. That seems unlikely to me, but it should be clear from looking at the other match clauses in each case. Carlo
ice-9 match penalty depending on pattern?
Hi, >From Ludo’s mastodon message [1]: Re ‘match’ penalty: when using ellipses in patterns, the generated code checks for “proper lists”, which is O(n). The trick is to instead match a pair: ✔ (match lst ((head . tail) …)) ❎ (match lst ((head tail ...) …)) Therefore I have confused by some patterns. --8<---cut here---start->8--- 28 candidates: ./gnu/services/monitoring.scm:249:((head tail ...) ./gnu/system/file-systems.scm:249: ((head1 tail1 ...) ./gnu/system/file-systems.scm:251: ((head2 tail2 ...) ./gnu/packages.scm:116: ((_ file head tail ...) ./gnu/build/activation.scm:85: ((head tail ...) ./gnu/build/linux-boot.scm:225: ((head tail ...) ./guix/http-client.scm:255: ((head tail ...) ./guix/records.scm:604: ((_ record field offset ((head normal) tail ...)) ./guix/records.scm:607: ((_ record field offset ((head delayed) tail ...)) ./guix/records.scm:610: ((_ record field offset ((head thunked) tail ...)) ./guix/read-print.scm:482: ((head tail ...) ./guix/read-print.scm:750: ((head tail ...) ./guix/lint.scm:1614:((head tail ...) ./guix/scripts/package.scm:809: ((head tail ...) head ./guix/self.scm:160: ((head tail ...) ./guix/store.scm:1556:((head tail ...) ./guix/store.scm:1764: ((head tail ...) ./guix/ui.scm:295: ((head tail ...) ./guix/ui.scm:2258: ((head tail ...) head))) ./guix/docker.scm:261: (((head ...) (tail ...) id) ./guix/build/store-copy.scm:72:((head tail ...) ./guix/build/gremlin.scm:336: ((head tail ...) ./guix/build/graft.scm:330: ((head tail ...) ./guix/build/utils.scm:236: ((head tail ...) ./guix/build/utils.scm:405: ((head tail ...) ./guix/utils.scm:910: ((head1 tail1 ...) ./guix/utils.scm:913: ((head2 tail2 ...) ./build-aux/compile-all.scm:71: ((head tail ...) --8<---cut here---end--->8--- Maybe for some of them, it changes nothing for the user-visible performances. Maybe it does. :-) Well, I do not know the length of each match. However, some are part of some loop. Therefore, if we could save some cycles by simply replacing the ellipsis, as ((head tail ...) stuff that use head or tail) by ((head . tail) stuff that use head or tail) Why not? Do I miss something in the implementation of ’match’? Cheers, simon 1: https://social.sciences.re/@civo...@toot.aquilenet.fr/111885442823194970
