bug#12032: quasiquote is too slow

bug#12032: quasiquote is too slow

[nalaginrut]

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.

bug#12032: quasiquote is too slow

[Ludovic Courtès]

Hi,

nalaginrut <nalaginrut@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’.

bug#12032: quasiquote is too slow

[nalaginrut]

On Sun, 2012-08-19 at 00:49 +0200, Ludovic Courtès wrote: 
> Hi,
> 
> nalaginrut <nalaginrut@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’.

bug#12032: quasiquote is too slow

[Ludovic Courtès]

Hi, Nala,

nalaginrut <nalaginrut@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’.