Re: Guile's time execution issues
Hey! Aleix Conchillo Flaqué skribis: > So weird I'm getting different numbers on 2.2.7. Not sure how I'm getting > those initial ~20s and you are getting consistent ~ 45s. It > shouldn't have nothing to do with it, but could it be I'm running it on macOS? Did you add this ‘->bool’ call to ensure the resulting alist is not kept in memory? > Now, it would be good to profile ‘json->scm’ to see if there’s anything > that could be improved on the Guile side, or if it’s just a normal > profile for GC-intensive code. > > Good news is that I have been working on performance improvements and > json->scm is going down from my ~19 seconds to ~3 > seconds on the same sample file. Linus Björnstam was the one to bring up > performance issues so we've been back and forth trying to > make it fast. Nice! > 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…) Thanks, Ludo’.
Re: Guile's time execution issues
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
Re: Guile's time execution issues
Sorry, sent a premature reply. The problem is that some of those match blocks expand to using equal? which is a lot slower than using eqv? If we are doing it on every char in a 24mb file we are getting some serious constant factors. match is a syntax-rules macro, so distinguishing literals are not possible. Concerning "the macro writer's bill of rights" I could maybe think this it would be a rather nice thing to turn equal? to eqv? when one argument is a char literal :D -- Linus Björnstam On Mon, 4 May 2020, at 11:36, Ludovic Courtès wrote: > Hey! > > Aleix Conchillo Flaqué skribis: > > > So weird I'm getting different numbers on 2.2.7. Not sure how I'm getting > > those initial ~20s and you are getting consistent ~ 45s. It > > shouldn't have nothing to do with it, but could it be I'm running it on > > macOS? > > Did you add this ‘->bool’ call to ensure the resulting alist is not kept > in memory? > > > Now, it would be good to profile ‘json->scm’ to see if there’s anything > > that could be improved on the Guile side, or if it’s just a normal > > profile for GC-intensive code. > > > > Good news is that I have been working on performance improvements and > > json->scm is going down from my ~19 seconds to ~3 > > seconds on the same sample file. Linus Björnstam was the one to bring up > > performance issues so we've been back and forth trying to > > make it fast. > > Nice! > > > 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…) > > Thanks, > Ludo’. > >
Re: Guile's time execution issues
Hi, Linus Björnstam 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’.
Re: Guile's time execution issues
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 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’. >
