[Haskell-cafe] IORef vs TVar performance: 6 seconds versus 4 minutes

[Jim Snow]

I decided to try to implement a graph algorithm using STM.  Each node in 
the graph has a set of TVar-protected lists of the nodes it links to and 
the nodes that link to it.  Also, there is a global TVar-protected 
Data.Map that contains all the nodes in the graph, indexed by name 
(which is polymorphic):

data Node k r = Node {
 fwdPos :: TVar [Node k r],  -- forward links (nodes we like)
 fwdNeg :: TVar [Node k r],  -- we allow "negative" links, too (nodes we 
don't like)
 revPos :: TVar [Node k r],  -- backlinks (nodes that like us)
 revNeg :: TVar [Node k r], -- negative back links (nodes that don't 
like us)
 currRep :: r,    -- extra user-defined data
 name   :: k     -- node's unique identifier
} deriving Show

data Network k r = Network {
 node    :: TVar (M.Map k (Node k r)),  -- map of nodes by name
 trusted :: TVar [Node k r]        -- a list of nodes we need to iterate 
over occasionally
} deriving Show


I tried loading a datafile of about 20,000 nodes into the graph in one 
big transaction, and found that it takes about 4 minutes.  This seemed 
rather slow, so I replaced all the TVars with IORefs (and substituted 
STM with IO in the type signatures), and the same operation with the new 
version took about 6 seconds!

This is all with one thread, so there should be no contention for the 
TVars.  Is there something about STM that makes it scale worse than 
linearly wrt the number of mutations in a transaction?

Above performance numbers are for ghc-6.10.1.  With ghc-6.8.3, the STM 
version takes more than 9 minutes.

According to profiling, one of my trouble spots is this function, which 
just adds an entry onto a TVar [a]:

stmcons :: k -> TVar [k] -> STM ()
stmcons x tv =
 do xs <- readTVar tv
      writeTVar tv (x:xs)

This seems like it ought to be pretty innocuous, unless the whole list 
is getting evaluated each time I cons a new entry, or if readTVar or 
writeTVar are much more expensive than they appear.

-jim