GNU bug report logs - #12032
quasiquote is too slow

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 12032 in the body.
You can then email your comments to 12032 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: nalaginrut <nalaginrut <at> gmail.com>
To: bug-guile <at> gnu.org
Subject: quasiquote is too slow
Date: Mon, 23 Jul 2012 14:10:47 +0800

I think our quasiquote is too slow, here's an algorithm to test it.
1. quasiquote version:
https://gist.github.com/3148984
2. use list append to instead
https://gist.github.com/3148977

The input value is 6000.
v1 cost ~50s for me.
v2 ~16s.

But quasiquote is more elegant I think.

Regards.

Message #8 received at 12032 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: nalaginrut <nalaginrut <at> gmail.com>
Cc: 12032 <at> debbugs.gnu.org
Subject: Re: bug#12032: quasiquote is too slow
Date: Sun, 19 Aug 2012 00:49:51 +0200

Hi,

nalaginrut <nalaginrut <at> gmail.com> skribis:

> I think our quasiquote is too slow, here's an algorithm to test it.
> 1. quasiquote version:
> https://gist.github.com/3148984
> 2. use list append to instead
> https://gist.github.com/3148977
>
> The input value is 6000.
> v1 cost ~50s for me.
> v2 ~16s.

I’m not sure what you’re measuring here.

I commented out the I/O, and tried this variant with len = 20000:

--8<---------------cut here---------------start------------->8---
(use-modules (ice-9 time))

(define (one len)
  (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2))))
    (display len)(newline)
    (time
     (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1))
       (and (< n len)
            (lp (append (list 1 (car b)) (cdr a)) (append (cdr b) (list (list-ref a m))) (1+ n)))))))

(define (two len)
  (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2))))
    (display len)(newline)
    (time
     (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1))
       (and (< n len)
            (lp `(1 ,(car b) ,@(cdr a)) `(,@(cdr b) ,(list-ref a m)) (1+ n)))))))
--8<---------------cut here---------------end--------------->8---

Both take ~7.12 seconds on my laptop.

In terms of code, the only difference is that, in ‘two’, the first
argument of the recursive call is optimized as:

  (cons 1 (cons (car b) (cdr a)))

whereas ‘one’ uses ‘append’.  In this case, there’s no real difference
between the two in terms of performance.

Can you please be more precise as to what felt “slow” for you, and
exactly how you measured execution times?

Thanks,
Ludo’.

Message #11 received at 12032 <at> debbugs.gnu.org (full text, mbox):

From: nalaginrut <nalaginrut <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 12032 <at> debbugs.gnu.org
Subject: Re: bug#12032: quasiquote is too slow
Date: Mon, 20 Aug 2012 13:59:48 +0800

On Sun, 2012-08-19 at 00:49 +0200, Ludovic Courtès wrote: 
> Hi,
> 
> nalaginrut <nalaginrut <at> gmail.com> skribis:
> 
> > I think our quasiquote is too slow, here's an algorithm to test it.
> > 1. quasiquote version:
> > https://gist.github.com/3148984
> > 2. use list append to instead
> > https://gist.github.com/3148977
> >
> > The input value is 6000.
> > v1 cost ~50s for me.
> > v2 ~16s.
> 
> I’m not sure what you’re measuring here.
> 
> I commented out the I/O, and tried this variant with len = 20000:
> 
> --8<---------------cut here---------------start------------->8---
> (use-modules (ice-9 time))
> 
> (define (one len)
>   (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2))))
>     (display len)(newline)
>     (time
>      (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1))
>        (and (< n len)
>             (lp (append (list 1 (car b)) (cdr a)) (append (cdr b) (list (list-ref a m))) (1+ n)))))))
> 
> (define (two len)
>   (let* ((ll ((@ (srfi srfi-1) iota) len 1)) (m (1- (/ len 2))))
>     (display len)(newline)
>     (time
>      (let lp((a (list-head ll (1+ m))) (b (list-tail ll (1+ m))) (n 1))
>        (and (< n len)
>             (lp `(1 ,(car b) ,@(cdr a)) `(,@(cdr b) ,(list-ref a m)) (1+ n)))))))
> --8<---------------cut here---------------end--------------->8---
> 
> Both take ~7.12 seconds on my laptop.
> 


Yes, Ludo, I realized that my measurement was little different:
-----------code---------
echo 6000 | ./v1.scm 1>/dev/null
-----------end----------
So I believe the delayed time caused by I/O.

But I can't reproduce the measure data I provided now(both
stable-2.0/wip-rtl), since it's been a while, I guess the later Guile
got some promotion? And I can't remember the commit version I've tried
(hmm...I should provide it). 
> In terms of code, the only difference is that, in ‘two’, the first
> argument of the recursive call is optimized as:
> 
>   (cons 1 (cons (car b) (cdr a)))
> 
> whereas ‘one’ uses ‘append’.  In this case, there’s no real difference
> between the two in terms of performance.
> 

Thanks for explain! 
I was always suspect that the difference in code level between append
and quasiquote, now I learned something.

> Can you please be more precise as to what felt “slow” for you, and
> exactly how you measured execution times?
> 
> Thanks,
> Ludo’.

Message #16 received at 12032-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: nalaginrut <nalaginrut <at> gmail.com>
Cc: 12032-done <at> debbugs.gnu.org
Subject: Re: bug#12032: quasiquote is too slow
Date: Mon, 20 Aug 2012 10:57:18 +0200

Hi, Nala,

nalaginrut <nalaginrut <at> gmail.com> skribis:

> Yes, Ludo, I realized that my measurement was little different:
> -----------code---------
> echo 6000 | ./v1.scm 1>/dev/null
> -----------end----------
> So I believe the delayed time caused by I/O.
>
> But I can't reproduce the measure data I provided now(both
> stable-2.0/wip-rtl), since it's been a while, I guess the later Guile
> got some promotion? And I can't remember the commit version I've tried
> (hmm...I should provide it). 

So I’m closing this bug for now.  However, feel free to reopen it, or
open another one, if you find the problem is still there.  But please,
make sure to reduce your benchmark as much as possible.

Thanks!

Ludo’.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.