[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