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

[Nicolas Pouillard]

Excerpts from Ben Lippmeier's message of Sat Nov 21 12:56:09 +0100 2009:
> 
> 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...

Your algorithm is O(1) but the current run-time system can take a time closer to O(n). This could be the case with a two spaces GC or with swapping.

-- 
Nicolas Pouillard
http://nicolaspouillard.fr