GNU bug report logs - #12032
quasiquote is too slow

Previous Next

Full log

View this message in rfc822 format

From: nalaginrut <nalaginrut <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 12032 <at> debbugs.gnu.org
Subject: 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’.

Previous Next

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