quasiquote is slow

[larceny-trac-import]

_Reported by: pnkfelix on Thu May 11 15:26:35 2006 _ Consider the following definitions:

;; Nat (Num -> X) -> [Listof X]
(define (build-list n f) 
  (reverse 
   (let rec ((n n)) 
     (if (zero? n) 
         '() 
         (cons (f (- n 1)) (rec (- n 1)))))))

;; (() -> Any) -> Time
(define (time-thunk thunk) 
  (let* ((s1 (memstats)) 
         (r (thunk)) 
         (s2 (memstats)) 
         (map- (lambda (f x y) (- (f x) (f y))))) 
    (car (map (lambda (f) (map- f s2 s1)) 
              (list memstats-elapsed-time 
                    memstats-system-time 
                    memstats-user-time)))))

;; Nat -> [Listof (list Time Time Time)] 
(define (time-quasiquote-expansion max-len/100)
  (map (lambda (sz)
       (map (lambda (qq uq) 
              (let ((stx (list qq (build-list 
                                   sz 
                                   (lambda (x)
                                     (list uq (+ x 1)))))))
                (collect) 
                (time-thunk 
                  (lambda ()   
                    (length (twobit-expand 
                             stx 
                             (the-usual-syntactic-environment))))))) 
            (list 'quote 'quasiquote 'quasiquote)
            (list 'quote 'quote      'unquote   )
            ))
     (build-list max-len/100 (lambda (x) (* 100 (+ x 1))))
     ))

What this does is times expansion for three kinds of expressions: standard quotations of size Theta(N), quasiquotes of size Theta(N) with no unquotes inside them, and quasiquotes with Theta(N) unquotes inside of them.

Lets see what happens as we grow N (the argument to time-quasiquote-expansion).

% ./twobit
Larceny v0.91 "Children's Ice Cream" 
(May 11 2006 11:23:47, precise:SunOS5:split)

> (load "stuff-above")

> (time-quasiquote-expansion 15)
((0 50 194)
 (1 162 1007)
 (0 336 3671)
 (1 582 7189)
 (1 1026 11565)
 (0 1216 17878)
 (0 1402 24076)
 (1 2291 30180)
 (1 2597 38125)
 (1 2945 47111)
 (0 3735 58052)
 (1 4211 68678)
 (0 5157 81849)
 (1 5837 92064)
 (1 6271 105694))

Notice how the three kinds of expansions are growing: quasiquote is always slower than quote, but it gets '''really''' slow when you throw the unquotes in. (This is unsurprising.)

Sassy's source has a quasiquote with ~1000 entries, so this test case is realistic and relevant for our own purposes. We should consider fixing it.

Also note that these times were measured using ./twobit to start up Larceny. The code as is won't work in native Larceny, because twobit-expand isn't exposed in that heap, but we should be able to get interesting data by just passing the same constructed expressions to compile.

[larceny-trac-import]

Author: pnkfelix I'm going to take notes on a Wiki page rather than put it in comments here (since I'll be posted source code and its going to go under revisions...)

Also, this whole thing might be relevant to Ticket #71.

[larceny-trac-import]

Author: pnkfelix Oops, forgot to actually make a link to the Wiki page in my last comment.

Here it is: QuasiquoteIsSlow

[larceny-trac-import]

Author: pnkfelix i just ran the code under 0.93. An interesting aspect of the problem is that I'm seeing somewhat different performance profiles when I compare SparcNativeLarceny against IasnLarceny

SparcNativeLarceny:

> (time-quasiquote-expansion 15)
((1 53 188)
 (0 113 619)
 (1 198 1765)
 (0 393 3556)
 (1 441 6290)
 (1 589 8320)
 (0 757 11586)
 (0 950 14989)
 (1 1150 20049)
 (1 1549 24259)
 (1 1647 34086)
 (1 1895 33631)
 (0 2260 41750)
 (1 2487 47226)
 (1 2904 54685))

IasnLarceny:

> (time-quasiquote-expansion 15)
((1 24 90)
 (0 42 240)
 (1 69 492)
 (1 100 788)
 (1 134 1120)
 (1 173 1595)
 (0 216 2153)
 (1 264 2728)
 (1 373 3470)
 (1 379 4298)
 (0 448 5069)
 (1 503 12323)
 (0 639 7414)
 (1 784 8544)
 (1 860 9920))

(Maybe I need to use larger inputs to see the growth under IasnLarceny... that is, it could be an artifact of the differing speeds between the host machines...)

[larceny-trac-import]

Author: pnkfelix See also Ticket #472 for information related to timing the compiler. (Maybe all these tickets should be replaced by a single ticket along with a Wiki page on the subject...)

[larceny-trac-import]

Author: will I just ran the code under v0.96. The time required to macro-expand quasiquote forms appears to have been greatly reduced, most probably by changeset:5209, which addresses ticket:346.

I think we should consolidate what we have learned from ticket:65, ticket:71, ticket:346, ticket:472, and the QuasiquoteIsSlow wiki page, and move all of that information to a new TwobitIsSlow page dedicated to monitoring and improving the speed of Twobit. We should keep this ticket open, however, because the time required to expand a quasiquote form should be linear in the size of the form, and it still isn't.

SparcNativeLarceny:

> (time-quasiquote-expansion 15)
((1 101 36)
 (1 117 99)
 (0 214 203)
 (0 337 348)
 (0 586 528)
 (0 645 733)
 (1 833 948)
 (0 1058 1262)
 (0 1295 1559)
 (1 1547 1879)
 (0 1849 2269)
 (1 2418 5060)
 (0 2495 3116)
 (1 2841 3587)
 (1 3253 4158))

IasnLarceny:

> (time-quasiquote-expansion 15)
((0 27 20)
 (0 58 47)
 (0 94 83)
 (0 137 146)
 (0 279 196)
 (1 258 245)
 (0 357 419)
 (1 480 488)
 (0 642 737)
 (0 770 811)
 (1 938 1235)
 (0 1098 1523)
 (1 2070 1661)
 (0 1556 2049)
 (0 1760 2559))