[Haskell-cafe] Efficient mutable arrays in STM

David Barbour dmbarbour at gmail.com
Tue Oct 25 21:55:17 CEST 2011

On Tue, Oct 25, 2011 at 10:47 AM, Ben Franksen <ben.franksen at online.de>wrote:

> The main question is: does the STM transaction actually "see" that I
> changed

part of the underlying array, so that the transaction gets re-tried? Or do I
> have to implement this manually, and if yes: how?

Create an extra TVar Int for every `chunk` in the array (e.g every 256
elements, tuned to your update patterns). Read-write it (increment it, be
sure to force evaluation) just before every time you write an element or
slice it or slice the array element. The IO mutable array is then adjusted
unsafely, but there is enough transactional context to restart transactions
that see an inconsistent state. You will have extra read/write and
write/write conflicts relative to a pure STM solution, but only within each

A cleaner alternative is to create a `chunked` TArray, i.e. that works with
fixed-width immutable chunks in a spine. This should have good performance
characteristics, and would be a lot safer for general purpose use.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111025/07dd522e/attachment.htm>

More information about the Haskell-Cafe mailing list