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