[Haskell-cafe] Efficient mutable arrays in STM

[Ben Franksen]

Ketil Malde wrote:

> Ben Franksen <ben.franksen at online.de> writes:
> 
>> An array of TVars is certainly *much* too inefficient for what I have in
>> mind w.r.t. both memory and cpu time.
> 
> You must be a lot more confident than I if you say this without
> benchmarking first. :-) 

Ok, not science, but an informed guess based on what I read about how STM is 
implemented in ghc. Cache locality is one of the main reasons why unboxed 
arrays perform so much better in practice than boxed ones, and TVars are 
most certainly boxed...

> IME, there are (at least) two possible problems
> here, 1) transactions scale (quadratically, I think) with the number of
> TVars touched, 

Ouch! What would be the reason for that? I thought it would be linear... I 
mean what happens is that the transaction log gets built when the 
transaction runs, which should take a constant time per TVar, and then on 
commit we have to traverse the log, which is again linear in the number of 
TVars...

> so if any transaction touch a large part of the array,
> it's going to cost you, and 2) every element of your array will have a
> pointer to it, making GC potentially expensive.  Perhaps you can get
> around the latter by tuning GC, e.g. +RTS -A100M might help.
> 
>> Or should I use a high-level approach, something like a Data.Sequence.Seq
>> of medium sized chunks (TVar (IOVector e))?
> 
> I'm not sure exactly what you mean here, but if you're going to touch
> contigous segments of the array, why not TArray (Vector e) or similar?

Yes, that was what David suggested, too. Have to think about it.

Cheers
Ben