bug#12032: quasiquote is too slow

[Ludovic Courtès]

Hi,

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