[Haskell-cafe] Questions about slow GC with STArray

Dan Doel dan.doel at gmail.com
Mon Apr 6 04:35:14 EDT 2009

On Monday 06 April 2009 4:10:43 am Bulat Ziganshin wrote:
> one way to solve this problem is to make one `modified` bit per each 256
> elements rather than entire array so GC will have to scan only
> modified chunks

For reference, I constructed a benchmark that takes advantage of GHC's tagging 
of whole arrays to approximate this:


Since each array has a dirty bit, making a type that stores an array of arrays 
that add up to the desired size is similar to having a dirty bit for chunks 
the size of the sub-array. The test then fills a 10 million element array.

However, something about the benchmark makes it perform poorly for both small 
chunks and large chunks. -sstderr reports that lots of copying occurs for 
small chunk sizes, and I haven't bothered to figure out why this is the case. 
You can, however, see that marking dirty chunks in this fashion would be 
profitable. The un-chunked array takes around a minute here, while with chunks 
of 10,000 (which seems to be about the optimal value with the above copying 
tradeoff), it takes about 6 seconds, and that's still with 60+% GC time.

-- Dan

More information about the Haskell-Cafe mailing list