[GHC] #8680: In STM: Variables only in left branch of orElse can invalidate the right branch transaction
GHC
ghc-devs at haskell.org
Sat Jan 18 21:33:34 UTC 2014
#8680: In STM: Variables only in left branch of orElse can invalidate the right
branch transaction
------------------------------+--------------------------------------------
Reporter: jberryman | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 7.6.3
Keywords: | Operating System: Unknown/Multiple
Architecture: | Type of failure: Runtime performance bug
Unknown/Multiple | Test Case:
Difficulty: Unknown | Blocking:
Blocked By: |
Related Tickets: |
------------------------------+--------------------------------------------
I'm sorry if this is expected behavior; I'm still trying to wrap my head
around this. I was surprised to learn that the right branch of an `orElse`
can be invalidated by changes to the world only visible by the left
branch. This might lead to starvation or performance issues for the use-
case I was envisioning it for (e.g. several threads trying to take from
one of a large set of TMVars in a randomized round-robin fashion).
Here is a really bad example demonstrating current behavior:
{{{
import Control.Concurrent
import Control.Concurrent.STM
import Control.Concurrent.STM.TSem
import Control.Monad
import System.IO
import Debug.Trace
main = do
hSetBuffering stdout NoBuffering
noMansLand <- replicateM 998 $ newTVarIO 0
t0 <- newTVarIO (1::Int)
t999 <- newTVarIO (-1)
let ts = t0:noMansLand++[t999]
done <- atomically $ newTSem 0
forkIO $ atomically $ nestedOrElseMap done ts
-- need enough time here for nestedOrElseMap thread above to move past
t0
-- in this version, the modifications to t0 force nestedOrElseMap to
be restarted
forkIO (trace "starting vexing!" $ forever $ atomically $ (modifyTVar'
t0 (+1) >> trace "vex" (return ())))
-- in this version nestedOrElseMap causes this transaction to be
restarted and never makes progress:
--forkIO (atomically (trace "starting vexing!" $ forever $
(modifyTVar' t0 (+1) >> trace "vex" (return ()))))
atomically $ waitTSem done
putStrLn "No livelock! Did the t0 counter get incremented?: "
atomically (readTVar t0) >>= print
-- another thread begins modifying head ts after we've moved to the right
branch
nestedOrElseMap :: TSem -> [TVar Int] -> STM ()
nestedOrElseMap done ts = trace "nestedOrElseMap starting" $ foldl1 orElse
$ map transaction $ zip [(1::Int)..] ts
where transaction (cnt,v) = do
n <- traceShow cnt $ readTVar v
if n < 0
then trace "@" (modifyTVar' v (subtract 1)) >> signalTSem
done
else retry
}}}
I can see it possibly being useful that both branches of an `orElse` see
the same view of the variables they ''share'', but current behavior seems
overzealous in restarting the whole transaction.
Maybe this is an artifact of changes related to #7493? Or maybe it's
obvious why this behavior has to be the way it is and its just not
clicking for me.
--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8680>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
More information about the ghc-tickets
mailing list