[Haskell-cafe] Boxed Mutable Arrays

Don Stewart dons at galois.com
Wed Dec 16 11:27:29 EST 2009

> 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

But note, Simon's making progress,

-- Don

More information about the Haskell-Cafe mailing list