unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* [PATCH] Add tree-il optimizations for equal? on char and number literals
@ 2020-05-13 11:20 Linus Björnstam
  2020-05-13 13:55 ` Andy Wingo
  0 siblings, 1 reply; 6+ messages in thread
From: Linus Björnstam @ 2020-05-13 11:20 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 1049 bytes --]

Hi there!

Aleix and I noticed that equal? has a lot higher overhead than eqv? on chars, which means using (ice-9 match) for chars was suboptimal. This patch fixes that.

With this patch, guile now turns (equal? #\b var) into (eqv? #\b var) and (equal? any-non-fixnum-number-literal var) into (eqv? any-non-fixnum-number-literal var). This fixes the (ice-9 match) problem, and means you can dispatch to equal? in macros and guile will just do the right thing is there are any literals.

There is one regression: it is not o(n). Currently the primitve expander is run once per call, which means a (equal? #\a b c d e) becomes (and (eqv? #\a b) (eqv? b c d e)) and that second call gets run through the primitive expander once again, which checks all the arguments again. The solution I see is to manually build the conditional code, or to just extend the old code, where only the comparisons directly involving the literal is optimized: (equal? a b #\c) -> (and (equal? a b) (eqv? b #\c)).

Any feedback is welcome.

-- 
  Linus Björnstam

[-- Attachment #2: 0001-Make-equal-to-eqv-or-eq-if-any-suitable-literals-are.patch --]
[-- Type: application/octet-stream, Size: 5637 bytes --]

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

* Re: [PATCH] Add tree-il optimizations for equal? on char and number literals
  2020-05-13 11:20 [PATCH] Add tree-il optimizations for equal? on char and number literals Linus Björnstam
@ 2020-05-13 13:55 ` Andy Wingo
  2020-05-13 16:33   ` Arne Babenhauserheide
  2020-05-13 21:16   ` Linus Björnstam
  0 siblings, 2 replies; 6+ messages in thread
From: Andy Wingo @ 2020-05-13 13:55 UTC (permalink / raw)
  To: Linus Björnstam; +Cc: guile-devel

Hi :)

On Wed 13 May 2020 13:20, Linus Björnstam <linus.bjornstam@veryfast.biz> writes:

> Hi there!
>
> Aleix and I noticed that equal? has a lot higher overhead than eqv? on
> chars, which means using (ice-9 match) for chars was suboptimal. This
> patch fixes that.

I think we can be a little more simple here.  Scheme doesn't specify
what (eqv? #\a x) is, but in Guile it is equivalent to (eq? #\a x), and
our compiler should be free to turn the portable eqv? invocation into
eq?.  But as the comment on line 416 says, we should really do this in
peval and not in the expander.  So.... you nerd-sniped me ;)  I just
pushed a patch that did this.

While looking, I found this:

> +         (make-conditional src (make-primcall src prim (list a b))
> +                           (make-primcall src prim (cons b rest))
> +                           (make-const src #f))))))

This was in the original code but is wrong: if "b" has a side-effect, it
will happen twice.  I have fixed it in git.

Thanks for the debugging and patch!

Andy



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

* Re: [PATCH] Add tree-il optimizations for equal? on char and number literals
  2020-05-13 13:55 ` Andy Wingo
@ 2020-05-13 16:33   ` Arne Babenhauserheide
  2020-05-13 21:16   ` Linus Björnstam
  1 sibling, 0 replies; 6+ messages in thread
From: Arne Babenhauserheide @ 2020-05-13 16:33 UTC (permalink / raw)
  To: Andy Wingo; +Cc: guile-devel, Linus Björnstam


Andy Wingo <wingo@pobox.com> writes:

> This was in the original code but is wrong: if "b" has a side-effect, it
> will happen twice.  I have fixed it in git.

Cool — thank you!

Do you see the difference in your benchmarks?

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken



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

* Re: [PATCH] Add tree-il optimizations for equal? on char and number literals
  2020-05-13 13:55 ` Andy Wingo
  2020-05-13 16:33   ` Arne Babenhauserheide
@ 2020-05-13 21:16   ` Linus Björnstam
  2020-05-14  8:38     ` Andy Wingo
  1 sibling, 1 reply; 6+ messages in thread
From: Linus Björnstam @ 2020-05-13 21:16 UTC (permalink / raw)
  To: Andy Wingo; +Cc: guile-devel

That is indeed a lot prettier!  I didn't know guile compared chars using eq? (The manual states that you should use eqv? For chars and numbers). 

On the latest master equal? was not reduced to eq? on chars in the repl for things like ,opt (define (a b) (equal? b #\b)). Was I using the new baseline compiler or should it always be triggered? I didn't have time to really check it out, and I have about a gazillion little computers that run guile. I do think I was sshing into the right one, though :)

Good to hear know that I can (match...) without fear in the future! Between this and the record unification I feel I have very little motivation to write my own extensible pattern matcher :) 
-- 
  Linus Björnstam

On Wed, 13 May 2020, at 15:55, Andy Wingo wrote:
> Hi :)
> 
> On Wed 13 May 2020 13:20, Linus Björnstam <linus.bjornstam@veryfast.biz> writes:
> 
> > Hi there!
> >
> > Aleix and I noticed that equal? has a lot higher overhead than eqv? on
> > chars, which means using (ice-9 match) for chars was suboptimal. This
> > patch fixes that.
> 
> I think we can be a little more simple here.  Scheme doesn't specify
> what (eqv? #\a x) is, but in Guile it is equivalent to (eq? #\a x), and
> our compiler should be free to turn the portable eqv? invocation into
> eq?.  But as the comment on line 416 says, we should really do this in
> peval and not in the expander.  So.... you nerd-sniped me ;)  I just
> pushed a patch that did this.
> 
> While looking, I found this:
> 
> > +         (make-conditional src (make-primcall src prim (list a b))
> > +                           (make-primcall src prim (cons b rest))
> > +                           (make-const src #f))))))
> 
> This was in the original code but is wrong: if "b" has a side-effect, it
> will happen twice.  I have fixed it in git.
> 
> Thanks for the debugging and patch!
> 
> Andy
>



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

* Re: [PATCH] Add tree-il optimizations for equal? on char and number literals
  2020-05-13 21:16   ` Linus Björnstam
@ 2020-05-14  8:38     ` Andy Wingo
  2020-05-14 18:14       ` Linus Björnstam
  0 siblings, 1 reply; 6+ messages in thread
From: Andy Wingo @ 2020-05-14  8:38 UTC (permalink / raw)
  To: Linus Björnstam; +Cc: guile-devel

On Wed 13 May 2020 23:16, Linus Björnstam <linus.bjornstam@veryfast.biz> writes:

> On the latest master equal? was not reduced to eq? on chars in the repl
> for things like ,opt (define (a b) (equal? b #\b)).

This turned out to be that I had broken the REPL command.  The optimizer
was working fine though.  Fixed now :)

Cheers,

Andy



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

* Re: [PATCH] Add tree-il optimizations for equal? on char and number literals
  2020-05-14  8:38     ` Andy Wingo
@ 2020-05-14 18:14       ` Linus Björnstam
  0 siblings, 0 replies; 6+ messages in thread
From: Linus Björnstam @ 2020-05-14 18:14 UTC (permalink / raw)
  To: Andy Wingo; +Cc: guile-devel

Works like a charm!

-- 
  Linus Björnstam

On Thu, 14 May 2020, at 10:38, Andy Wingo wrote:
> On Wed 13 May 2020 23:16, Linus Björnstam <linus.bjornstam@veryfast.biz> writes:
> 
> > On the latest master equal? was not reduced to eq? on chars in the repl
> > for things like ,opt (define (a b) (equal? b #\b)).
> 
> This turned out to be that I had broken the REPL command.  The optimizer
> was working fine though.  Fixed now :)
> 
> Cheers,
> 
> Andy
>



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

end of thread, other threads:[~2020-05-14 18:14 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-13 11:20 [PATCH] Add tree-il optimizations for equal? on char and number literals Linus Björnstam
2020-05-13 13:55 ` Andy Wingo
2020-05-13 16:33   ` Arne Babenhauserheide
2020-05-13 21:16   ` Linus Björnstam
2020-05-14  8:38     ` Andy Wingo
2020-05-14 18:14       ` Linus Björnstam

unofficial mirror of guile-devel@gnu.org 

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://yhetil.org/guile-devel/0 guile-devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 guile-devel guile-devel/ https://yhetil.org/guile-devel \
		guile-devel@gnu.org
	public-inbox-index guile-devel

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.yhetil.org/yhetil.lisp.guile.devel
	nntp://news.gmane.io/gmane.lisp.guile.devel


AGPL code for this site: git clone http://ou63pmih66umazou.onion/public-inbox.git