GNU bug report logs - #12032
quasiquote is too slow

Previous Next

Full log

View this message in rfc822 format

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

Previous Next

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