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

To be slightly more precise in my algorithmic analysis: to a first
approximation, atomic operations that aren't allocation are free. In
the append version of your program you are allocating O(n^2) cells
when you only need to allocation O(n). The append! version allocates
O(n). The difference is that append doesn't copy its first argument,
but append does.

Hope that is slightly more clear!

Robby

On 5/28/07, Robby Findler <robby at cs.uchicago.edu> wrote:
> 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
> >
>