On Tue, Oct 25, 2011 at 1:46 PM, Ben Franksen
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