unofficial mirror of guix-devel@gnu.org 
 help / color / mirror / code / Atom feed
* ice-9 match penalty depending on pattern?
@ 2024-02-06 21:33 Simon Tournier
  2024-02-06 23:41 ` Carlo Zancanaro
  0 siblings, 1 reply; 3+ messages in thread
From: Simon Tournier @ 2024-02-06 21:33 UTC (permalink / raw)
  To: Guix Devel; +Cc: Ludovic Courtès

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/@civodul@toot.aquilenet.fr/111885442823194970



^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: ice-9 match penalty depending on pattern?
  2024-02-06 21:33 ice-9 match penalty depending on pattern? Simon Tournier
@ 2024-02-06 23:41 ` Carlo Zancanaro
  2024-02-07  9:22   ` Simon Tournier
  0 siblings, 1 reply; 3+ messages in thread
From: Carlo Zancanaro @ 2024-02-06 23:41 UTC (permalink / raw)
  To: Simon Tournier; +Cc: Guix Devel, Ludovic Courtès

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


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: ice-9 match penalty depending on pattern?
  2024-02-06 23:41 ` Carlo Zancanaro
@ 2024-02-07  9:22   ` Simon Tournier
  0 siblings, 0 replies; 3+ messages in thread
From: Simon Tournier @ 2024-02-07  9:22 UTC (permalink / raw)
  To: Carlo Zancanaro; +Cc: Guix Devel, Ludovic Courtès

Hi,

On mer., 07 févr. 2024 at 10:41, Carlo Zancanaro <carlo@zancanaro.id.au> 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


^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2024-02-11 17:22 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-02-06 21:33 ice-9 match penalty depending on pattern? Simon Tournier
2024-02-06 23:41 ` Carlo Zancanaro
2024-02-07  9:22   ` Simon Tournier

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/guix.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).