[Haskell-beginners] Re: Is Haskell for me?

[Ben Lippmeier]

On 21/11/2009, at 21:13 , Nicolas Pouillard wrote:

> Excerpts from Ben Lippmeier's message of Sat Nov 21 07:38:09 +0100 2009:
>> 
>> On 21/11/2009, at 15:36 , Jon Harrop wrote:
>> 
>>> The long-standing bug in GHC's garbage collector that makes writing a single 
>>> boxed value into an array O(n) instead of O(1), because the GC dirties and 
>>> retraverses the entire array, makes it impossible to write efficient Haskell 
>>> code to solve many basic problems.
>> 
>> Are you talking about http://hackage.haskell.org/trac/ghc/ticket/650 ?
>> 
>> The way I read that ticket is that writing a boxed value to a mutable array is still O(1), but the garbage collector traverses the whole array during
>> scanning. That could certainly slow down GC cycles, but how does it make array update O(n)?
> 
> He means in worst case. Writing once, will cause O(n) during the next GC. Of
> course if you do a lot of updates between two GCs their is no extra penalty.
> So if you make 'k' updates between 2 GCs it costs you k*O(1)+O(n) which is
> still O(n) but practically nicer than k*O(n).
> 

Hmm. I'd be careful about conflating algorithmic complexity with memory management issues. By the above reasoning, if I were to run any program using arrays on a system with a two space garbage collector (which copies all live objects during each GC) I could say the worst case algorithmic complexity was O(n). That doesn't sound right.

I could take this further and say that in a virtual memory system, there is a chance that the whole heap gets copied to the disk and back between each array update. I might again say this has O(n) complexity, but it wouldn't be very helpful...

Ben.