[Haskell-cafe] Boxed Mutable Arrays

Bulat Ziganshin bulat.ziganshin at gmail.com
Tue Dec 15 11:23:50 EST 2009


Hello Brad,

Tuesday, December 15, 2009, 7:16:18 PM, you wrote:

> You said to use an array of arrays instead of a large array, in the
> context of a fast hash table in ST.  Do you mean I should use an array
> for hash buckets, rather than a list?

> Is that what you meant?  And why would it be faster?

> 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


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com



More information about the Haskell-Cafe mailing list