On Tue, Oct 25, 2011 at 1:46 PM, Ben Franksen <[email protected]>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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
