[Haskell-cafe] Efficient mutable arrays in STM

[Ben Franksen]

David Barbour wrote:
> 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 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