[Haskell-cafe] Boxed Mutable Arrays

[Don Stewart]

brad.larsen:
> On Tue, Dec 15, 2009 at 11:33 AM, Serguey Zefirov <sergueyz at gmail.com> wrote:
> >>> If the number of buckets was fixed, one could use an array of STRefs
> >>> to lists.  I believe this would avoid the bug from Ticket #650?
> >> now i see what you mean. no, i mean trivial transformation. #650 says
> >> about slow GC. why it's slow? because once you made any update to the
> >> array, the entire array is marked as updated and scanned on next minor GC
> >> (which occurs after every 512 kbytes allocated, afaik). let's replace
> >> big array (say, of 10,000 elements) with array of 100 arrays of 100
> >> elements each. now, between minor GCs only some of arrays will be
> >> changed and entire amount of memory to be scanned will become less
> >
> > Data.IntMap?
> >
> 
> I want to implement a more-or-less traditional, mutable, imperative
> hash table in the ST monad.  Hence, I'm not considering Data.IntMap
> and other persistent tree structures for its implementation, although
> I have thought about it.
> 
> The bug described in Ticket #650, AFAICS, prevents implementation of a
> reasonable, generic hash table in Haskell.  :-(

You can certainly implement it, it just requires that you increase the
heap size to a bit bigger than your hash to reduce the pressure on the
GC.

But note, Simon's making progress,
    http://hackage.haskell.org/trac/ghc/ticket/650#comment:17

-- Don