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

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