Re: [Haskell-cafe] Efficient mutable arrays in STM

David Barbour wrote:

On Tue, Oct 25, 2011 at 10:47 AM, Ben Franksen 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 chunk.

Your idea is quite similar to what I had in mind, and it encourages me that you think it should be possible to do it like that. My idea was to use variable-size chunks, based on which slices are currently in use and how they overlap, i.e. calculate the maximal non-overlapping index intervals. Such a solution would automatically adapt to the usage pattern, but is harder to implement efficiently.

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.

This is also an interesting idea, probably much easier to implement, too. Thanks for the feedback Cheers Ben