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

[Nicolas Pouillard]

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).

-- 
Nicolas Pouillard
http://nicolaspouillard.fr