unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
From: "Linus Björnstam" <linus.bjornstam@veryfast.biz>
To: "Ludovic Courtès" <ludo@gnu.org>
Cc: guile-user <guile-user@gnu.org>, guile-devel <guile-devel@gnu.org>
Subject: Re: Guile's time execution issues
Date: Fri, 08 May 2020 13:31:44 +0200	[thread overview]
Message-ID: <29b88b88-00c4-478e-8587-7a6e2d7a8e39@www.fastmail.com> (raw)
In-Reply-To: <d7951a62-a1df-44e2-bbc0-2fb9e0bc4079@www.fastmail.com>

Another option would be to just overload equal? in match.scm to transform into eqv? when there are char literals or numbers, eq? on symbols, booleans,  the empty list and keywords and (@@ (guile) equal?) for everything else.

Considering that it in this case contributed a 25% overhead to code that was performance critical I think it would be a pretty valid thing to do. If you, ludo, an Andy thinks that would be a good idea I can make such a patch for match.scm. That would have the benefit of not changing the upstream code (which is (include ...)d in match.scm), nor fiddling around with guile optimisations.

-- 
  Linus Björnstam

On Mon, 4 May 2020, at 22:50, Linus Björnstam wrote:
> You didn't see my other reply. The matching code isn't suboptimal. The 
> equality predicate is  The problem is that match compares using equal? 
> even for literal chars (where eqv? is a lot faster). It would be a 
> rather trivial optimization to do, either to match.scm (meaning: 
> breaking with upstream and use syntax-case) or to the guile compiler in 
> general (changing equal? to eqv, when there are character literals), 
> which seems ok-ish for this use-case but at very little benefit in 
> general.
> 
> A long-term goal of mine is to write a pattern matcher with the 
> optimisations that the racket matcher does (among other things: some 
> serious list matching reordering!). That is a daunting task though.
> 
> -- 
>   Linus Björnstam
> 
> On Mon, 4 May 2020, at 22:09, Ludovic Courtès wrote:
> > Hi,
> > 
> > Linus Björnstam <linus.bjornstam@veryfast.biz> skribis:
> > 
> > > On Mon, 4 May 2020, at 11:36, Ludovic Courtès wrote:
> > >  
> > >> > One thing I found is that `match` is slow. The code looked nicer but had to change it back to lets and conds as the performance
> > >> > increase was ~2 seconds.
> > >> 
> > >> Oh, in which case exactly?  And are you sure your hand-written code is
> > >> equivalent to the ‘match’ code (it’s common for hand-written code to be
> > >> more lax than ‘match’)?
> > >> 
> > >> One thing to pay attention to is the use of ‘list?’, which is O(N), and
> > >> is implied by ellipses in ‘match’.  If you want to use ‘match’ in a way
> > >> that avoids ‘list?’, write patterns such as (a . b) instead of (a b ...).
> > >> It doesn’t have the same meaning, but often the end result is the same,
> > >> for instance because you’ll later match on ‘b’ anyway.
> > >> 
> > >> (I wish we can one day have a proper list type disjoint from pairs…)
> > >
> > > The change is here: he is only matching against chars and predicates: https://github.com/aconchillo/guile-json/commit/ad4b06d86e4822466983d00f55474c8f664b538d
> > 
> > It would be nice if you could pinpoint which one of these changes causes
> > a difference, because:
> > 
> > --8<---------------cut here---------------start------------->8---
> > scheme@(guile-user)> ,optimize (match (peek-char port) ((? eof-object?) 
> > x) ((? whitespace?) w) (_ e))
> > $84 = (let ((v (peek-char port)))
> >   (cond ((eof-object? v) x)
> >         ((whitespace? v) w)
> >         (else e)))
> > --8<---------------cut here---------------end--------------->8---
> > 
> > What might make a difference is the code bloat when using ‘or’:
> > 
> > --8<---------------cut here---------------start------------->8---
> > scheme@(guile-user)> ,optimize (match (peek-char port) ((or #\a #\b #\c #\d) x))
> > $86 = (let ((v (peek-char port)))
> >   (cond ((equal? v #\a) x)
> >         ((equal? v #\b) x)
> >         ((equal? v #\c) x)
> >         ((equal? v #\d) x)
> >         (else
> >          ((@@ (ice-9 match) error)
> >           'match
> >           "no matching pattern"
> >           v)
> >          #f)))
> > --8<---------------cut here---------------end--------------->8---
> > 
> > but even that sounds unlikely.
> > 
> > You’re compiling with -O2, right?
> > 
> > Thanks,
> > Ludo’.
> >
> 
>



  reply	other threads:[~2020-05-08 11:31 UTC|newest]

Thread overview: 12+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-04-21 22:03 Guile's time execution issues Aleix Conchillo Flaqué
2020-04-22 13:47 ` Linus Björnstam
2020-04-26 17:16 ` Ludovic Courtès
2020-04-26 23:14   ` Aleix Conchillo Flaqué
2020-05-02 14:11     ` Ludovic Courtès
2020-05-04  0:32       ` Aleix Conchillo Flaqué
2020-05-04  9:36         ` Ludovic Courtès
2020-05-04 11:19           ` Linus Björnstam
2020-05-04 20:09             ` Ludovic Courtès
2020-05-04 20:50               ` Linus Björnstam
2020-05-08 11:31                 ` Linus Björnstam [this message]
2020-05-04 18:47           ` Linus Björnstam

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/guile/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=29b88b88-00c4-478e-8587-7a6e2d7a8e39@www.fastmail.com \
    --to=linus.bjornstam@veryfast.biz \
    --cc=guile-devel@gnu.org \
    --cc=guile-user@gnu.org \
    --cc=ludo@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).