<br><br><div class="gmail_quote">On Tue, Oct 25, 2011 at 1:46 PM, Ben Franksen <span dir="ltr"><<a href="mailto:ben.franksen@online.de">ben.franksen@online.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
> IME, there are (at least) two possible problems<br><div class="im">
> here, 1) transactions scale (quadratically, I think) with the number of<br>
> TVars touched,<br>
<br>
</div>Ouch! What would be the reason for that? I thought it would be linear... I<br>
mean what happens is that the transaction log gets built when the<br>
transaction runs, which should take a constant time per TVar, and then on<br>
commit we have to traverse the log, which is again linear in the number of<br>
TVars...<br></blockquote><div><br>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).<br>
<br>Consider this code:<br><br>f :: TVar Int -> STM ()<br>f v = do<br> x <- readTVar v<br> writeTVar v $! (x+1)<br><br>g :: Int -> TVar Int -> STM ()<br>g n v = mapM_ (\_ -> f v) [1..n]<br><br>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.<br>
<br>As to your second assumption, it's been a while since I read the STM source, so I can't comment there.<br><br> -- ryan<br></div></div><br>