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

But in this case you're using a quadratic-time algorithm for a
linear-time problem!

In less friendly words it isn't comparing a pure program to an
imperative one; it is a comparing a bad program (that you should never
write!) to an imperative program. :) Instead, try writing a function
that uses `cons' in the loop, and then does one append at the end.
More like Eli's comparison (upthread).

As far as crashing drscheme goes, have you tried setting a memory
limit? I guess you're running out of memory (its a new feature -- see
the "Scheme" menu).

Robby

On 5/28/07, Kyle Smith <airfoil at bellsouth.net> wrote:
> Matthew Flatt <mflatt at ...> writes:
>
> > How much time does `append!' save you in an actual application? My
> > guess is that the savings will be minor, but I'm interested in
> > measurements you might be able to take.
> >
> > Matthew
>
> Hi,
>
> This is what I get for append vs append! when I use it in a routine that
> builds a list within the loop, returning the result; which for me is more
> typical of when I would use append.  In this code append! looks to be
> faster by an order of magnitude for all but the smallest lists.  I stop at
> (> loops 15000) because shortly after that, the append version crashes
> my DrScheme system.
>
> --kyle
> airfoil at bellsouth dot com
> schemekeys.blogspot.com
> ---------------------CODE---------------------------------
> (module time-it mzscheme
>
>   (provide time-it)
>
>   (define (time-it title loops append)
>     (collect-garbage)
>     (printf "; ~a loops=~a " title loops)
>     (time
>      (let loop ([result ()][n loops])
>        (cond
>          ((= n 0) result)
>          (else
>           (loop (append result (list #f)) (sub1 n)))))))
>   )
> (require time-it)
> (let loop ([foo #f][bar #f][loops 1000])
>   (cond
>     ((> loops 15000) 'finished)
>     (else
>      (set! foo (time-it 'append loops append))
>      (set! bar (time-it 'append! loops append!))
>      (loop #f #f (floor (* loops (log 3)))))))
> --------------------RESULTS--------------------------------
> Welcome to DrScheme, version 369.100-svn13may2007 [3m].
> Language: SchemeKeys custom.
> ; append loops=1000 cpu time: 8 real time: 8 gc time: 0
> ; append! loops=1000 cpu time: 2 real time: 1 gc time: 0
> ; append loops=1098.0 cpu time: 8 real time: 8 gc time: 0
> ; append! loops=1098.0 cpu time: 2 real time: 2 gc time: 0
> ; append loops=1206.0 cpu time: 11 real time: 11 gc time: 0
> ; append! loops=1206.0 cpu time: 2 real time: 3 gc time: 0
> ; append loops=1324.0 cpu time: 13 real time: 13 gc time: 0
> ; append! loops=1324.0 cpu time: 3 real time: 3 gc time: 0
> ; append loops=1454.0 cpu time: 15 real time: 16 gc time: 0
> ; append! loops=1454.0 cpu time: 4 real time: 4 gc time: 0
> ; append loops=1597.0 cpu time: 19 real time: 18 gc time: 0
> ; append! loops=1597.0 cpu time: 5 real time: 5 gc time: 0
> ; append loops=1754.0 cpu time: 23 real time: 23 gc time: 0
> ; append! loops=1754.0 cpu time: 6 real time: 5 gc time: 0
> ; append loops=1926.0 cpu time: 26 real time: 27 gc time: 0
> ; append! loops=1926.0 cpu time: 7 real time: 7 gc time: 0
> ; append loops=2115.0 cpu time: 66 real time: 67 gc time: 32
> ; append! loops=2115.0 cpu time: 8 real time: 8 gc time: 0
> ; append loops=2323.0 cpu time: 73 real time: 73 gc time: 33
> ; append! loops=2323.0 cpu time: 9 real time: 10 gc time: 0
> ; append loops=2552.0 cpu time: 81 real time: 82 gc time: 33
> ; append! loops=2552.0 cpu time: 11 real time: 12 gc time: 0
> ; append loops=2803.0 cpu time: 90 real time: 92 gc time: 33
> ; append! loops=2803.0 cpu time: 15 real time: 15 gc time: 0
> ; append loops=3079.0 cpu time: 138 real time: 138 gc time: 67
> ; append! loops=3079.0 cpu time: 17 real time: 17 gc time: 0
> ; append loops=3382.0 cpu time: 152 real time: 154 gc time: 67
> ; append! loops=3382.0 cpu time: 21 real time: 21 gc time: 0
> ; append loops=3715.0 cpu time: 209 real time: 230 gc time: 103
> ; append! loops=3715.0 cpu time: 25 real time: 25 gc time: 0
> ; append loops=4081.0 cpu time: 269 real time: 275 gc time: 134
> ; append! loops=4081.0 cpu time: 30 real time: 30 gc time: 0
> ; append loops=4483.0 cpu time: 287 real time: 296 gc time: 135
> ; append! loops=4483.0 cpu time: 37 real time: 38 gc time: 0
> ; append loops=4925.0 cpu time: 360 real time: 362 gc time: 172
> ; append! loops=4925.0 cpu time: 46 real time: 46 gc time: 0
> ; append loops=5410.0 cpu time: 472 real time: 493 gc time: 241
> ; append! loops=5410.0 cpu time: 53 real time: 53 gc time: 0
> ; append loops=5943.0 cpu time: 552 real time: 570 gc time: 273
> ; append! loops=5943.0 cpu time: 66 real time: 67 gc time: 0
> ; append loops=6529.0 cpu time: 675 real time: 692 gc time: 344
> ; append! loops=6529.0 cpu time: 76 real time: 77 gc time: 0
> ; append loops=7172.0 cpu time: 813 real time: 834 gc time: 421
> ; append! loops=7172.0 cpu time: 92 real time: 92 gc time: 0
> ; append loops=7879.0 cpu time: 977 real time: 1020 gc time: 495
> ; append! loops=7879.0 cpu time: 111 real time: 112 gc time: 0
> ; append loops=8655.0 cpu time: 1195 real time: 1232 gc time: 618
> ; append! loops=8655.0 cpu time: 135 real time: 136 gc time: 0
> ; append loops=9508.0 cpu time: 1461 real time: 1479 gc time: 767
> ; append! loops=9508.0 cpu time: 169 real time: 170 gc time: 0
> ; append loops=10445.0 cpu time: 1813 real time: 1877 gc time: 978
> ; append! loops=10445.0 cpu time: 194 real time: 195 gc time: 0
> ; append loops=11475.0 cpu time: 2199 real time: 2252 gc time: 1191
> ; append! loops=11475.0 cpu time: 243 real time: 245 gc time: 0
> ; append loops=12606.0 cpu time: 2692 real time: 2754 gc time: 1468
> ; append! loops=12606.0 cpu time: 291 real time: 307 gc time: 0
> ; append loops=13849.0 cpu time: 3315 real time: 3378 gc time: 1851
> ; append! loops=13849.0 cpu time: 365 real time: 367 gc time: 0
> finished
>
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>