[Haskell-cafe] Efficient mutable arrays in STM

[Ryan Ingram]

On Tue, Oct 25, 2011 at 1:46 PM, Ben Franksen <ben.franksen at online.de>wrote:

> > 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...
>

Your first assumption is incorrect.  Every time you access a TVar it needs
to check in the log if that TVar was already accessed in this transaction,
so that it can get/update the current value.  Right now the log is just a
list, so accessing a TVar takes O(number of TVars already accessed).

Consider this code:

f :: TVar Int -> STM ()
f v = do
    x <- readTVar v
    writeTVar v $! (x+1)

g :: Int -> TVar Int -> STM ()
g n v = mapM_ (\_ -> f v) [1..n]

In order for f to get the current value of the TVar, it has to check if the
variable is in the log already; otherwise later calls to f will just see the
original value in memory and not repeatedly increment it.

As to your second assumption, it's been a while since I read the STM source,
so I can't comment there.

  -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111027/50fffee9/attachment.htm>