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

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

At Mon, 28 May 2007 16:40:03 -0500, "Robby Findler" wrote:
> Kyle: my point is that your comparison isn't fair, for technical
> reasons. If you want to test just raw append vs append!, Matthew's
> first timing post is probably the right one. If you want to test
> "real" uses, then it isn't wise to pick a function that can
> implemented in linear time and write an quadratic-time algorithm for
> it.
> 
> yours,
> Robby
> 
> On 5/28/07, Kyle Smith <airfoil at bellsouth.net> wrote:
> > Robby Findler <robby at ...> writes:
> >
> > >
> > > 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
> >
> > Hi Robby,
> >
> > I could of course write:
> > (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) (reverse result))
> >          (else
> >           (loop (cons result (list #f)) (sub1 n)))))))
> >   )
> >
> > to achieve the same thing without using append at all, in this
> > contrived example, which, as you point out runs rather quickly.
> > But it doesn't time append.  The code I benchmarked, as you say,
> > "should never be written", but I think that it does isolate the
> > differences between append vs append!, by having append do all
> > the work.
> >
> > I actually don't use append! at all, or any of the other ! versions,
> > except for set-car! and set-cdr! in my queue ADT.  Not becauseI had
> > bad experiences with the ! versions, but rather because it was strongly
> > advised against in TSPL, which is the book that I read first in learning
> > Scheme.
> >
> > So, I don't have a stake in the outcome, and am not advocating a
> > position.  The fact is, I noticed that Mathew's code was using vector->list
> > on every iteration of the loop, which got me wondering how accurately that
> > code was measuring append, in isolation. I was simply trying to isolate the
> > differences between the functions, by having append be the predominate
> > function in the loop.  I had to give it some thought as how best to isolate
> > append, and the code I presented was simply the result of that thought
> > process.
> >
> > A good unit benchmark doesn't necessarily reflect good coding practice;
> > it's purpose is to time the unit, in this case append.  I think it did a good
> > job of showing the difference between the timing of using append vs
> > append! on varying sizes of lists, and that the size of the list had an 
> impact
> > on the timing.  If I had started the loops at one, you would see that their 
> is
> > insignifcant differences between the times of the two functions.  So, if you
> > are only going to be using append a only a few times, as in Eli's code, it
> > makes no sense to take the risk involved in using append!.  On the other
> > hand, if you had code that employed append in a loop, for what ever
> > purpose, you're going to run into trouble, because the timing differences,
> > due to allocation, are quite significant.
> >
> > I think there is some history behind this thread, that I havn't been 
> following,
> > and I seem to have stumbled into it.  I quite like functional programming,
> > and am trying to learn ml and Haskell, when I can pull myself away from
> > DrScheme, because they are both much more rigid than Scheme in their
> > allowance of mutable objects.  So, if DrScheme becomes more strict in that
> > area, it would suit me just fine.
> >
> > I hope this missive clears up any inaccurate impressions of my view on the
> > forth coming changes to DrScheme my benchmark may have spawned.
> >
> > Cheers,
> >
> > --kyle
> > airfoil at bellsouth dot net
> > schemekeys.blogspot.net
> >
> >
> > _________________________________________________
> >   For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme