ice-9 match penalty depending on pattern?

ice-9 match penalty depending on pattern?

[Simon Tournier]

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

Re: ice-9 match penalty depending on pattern?

[Carlo Zancanaro]

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

Re: ice-9 match penalty depending on pattern?

[Simon Tournier]

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

Re: ice-9 match penalty depending on pattern?

[Ludovic Courtès]

Hey,

Simon Tournier <zimon.toutoune@gmail.com> 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’.