[plt-scheme] Re: scribblings on PLT Scheme 4.0

Matthew Flatt <mflatt at ...> writes:

> 
> Well, I think it was an interesting comparison. The example shows how
> replacing `append!' with `append' can lead to touching more than twice
> as much memory (and therefore suffer more than a 2x hit) without
> affecting asymptotic complexity.
> 
> Still, at this point, I'm interested in hearing about the overall
> effect on realistic programs (instead of just microbenchmarks) if
> anyone has an example to measure it.
> 
> Matthew

These are results I got with a fairly common function in any Schemer's tool 
box, `fringe'.  I simpy made a ! version out of it to compare with; they are 
otherwise identical.  This is probably showing append being used in a more
practical setting, and indeed, the differences in times, over varying tree 
sizes was stable and only a factor of less than two.

Hope this helps.

---------------CODE-----------------------------------

(define (fringe x:xs)
  (cond
    [(null? x:xs) ()]
    [else
     (let ([x (car x:xs)][xs (cdr x:xs)])
       (cond
         [(null? x) (fringe xs)]
         [(atom? x) (append (list x) (fringe xs))]
         [else
          ((lambda (t)
             (cond
               [(not (null? t)) (append t (fringe xs))]
               [else (fringe xs)]))
           (fringe x))]))]))

(define (fringe! x:xs)
  (cond
    [(null? x:xs) ()]
    [else
     (let ([x (car x:xs)][xs (cdr x:xs)])
       (cond
         [(null? x) (fringe! xs)]
         [(atom? x) (append! (list x) (fringe! xs))]
         [else
          ((lambda (t)
             (cond
               [(not (null? t)) (append! t (fringe! xs))]
               [else (fringe! xs)]))
           (fringe! x))]))]))

-------------Results for increasing tree sizes----------

Loops = 50000
fringe length= 3 
cpu time: 720 real time: 726 gc time: 170
fringe! length= 3 
cpu time: 426 real time: 429 gc time: 0
fringe length= 8 
cpu time: 4719 real time: 4794 gc time: 1282
fringe! length= 8 
cpu time: 2681 real time: 2718 gc time: 123
fringe length= 13 
cpu time: 8766 real time: 8858 gc time: 2408
fringe! length= 13 
cpu time: 4936 real time: 4969 gc time: 243
fringe length= 18 
cpu time: 12762 real time: 12883 gc time: 3539
fringe! length= 18 
cpu time: 7196 real time: 7244 gc time: 364
fringe length= 23 
cpu time: 17091 real time: 17262 gc time: 4941
fringe! length= 23 
cpu time: 9498 real time: 9570 gc time: 527

------------All times are for a loop of 5000 iterations----

Thanks,

--kyle
airfoil at bellsouth dot net
schemekeys.blogspot.com