[GHC] #8680: In STM: Variables only in left branch of orElse can invalidate the right branch transaction

[GHC]

#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
      Resolution:                           |         Keywords:
Operating System:  Unknown/Multiple         |     Architecture:
 Type of failure:  Runtime performance bug  |  Unknown/Multiple
       Test Case:                           |       Difficulty:  Unknown
        Blocking:                           |       Blocked By:
                                            |  Related Tickets:
--------------------------------------------+------------------------------
Changes (by fryguybob):

 * cc: fryguybob@… (added)


Comment:

 As [comment:2 ezyang] said, this is the expected behavior.  We only visit
 the right branch if the left branch reaches retry.  While the effects of
 the left branch are discarded, the outcome is not.  When the whole
 transaction commits, it will check that the outcome of the left branch is
 still the same by checking that the reads from the left branch have not
 changed.

 This becomes important if the right branch reaches `retry` (and this is a
 top-level `orElse`).  When the transaction blocks, it needs to be added to
 the watch list for all the `TVar`s read, including the branches that we
 discarded as it may be the case that an earlier branch will allow the
 transaction to make progress.  Before we can block we must validate that
 we are not blocking due to reading inconsistent data.  Otherwise we could
 block and miss the chance to wake up.

 While I think a nondeterministic `orElse` should be possible, it would be
 tricky to get it right and with the fairness that we would clearly want.
 I'm not sure what are the right interactions with nesting and blocking.  A
 particular branch could reach `retry` due to inconsistent reads.  Do we
 still propagate the retry up, potentially taking another branch at a
 higher level?  Do we block on this faulty data, or validate the discarded
 reads first?  If found invalid do we start all over, or do we try
 inconsistent branches again?  If so in what order?  Perhaps there is some
 wisdom to be gleaned from this work: http://www.cs.rit.edu/~mtf/research
 /tx-events/IFL11/techrpt.pdf

 If you only care about a top-level chain of `orElse`s as in the example,
 you can sort of accomplish what you want now with something like this:

 {{{
 #!haskell
 atomicallyOneOf :: [STM a] -> IO a
 atomicallyOneOf ts = go (cycle (map run ts))
   where
     go (t:ts) = do
         v <- t
         case v of
            Nothing -> go ts
            Just a  -> return a
     run t = atomically ((Just <$> t) `orElse` return Nothing)
 }}}

 But this will still get "stuck" when it runs across a `t` that is
 contending with a repeated faster transaction.  If we had a
 `tryAtomically` that didn't bother to start again you could do a little
 better, but I'm not sure this is a good API to give users in general as
 they might reach for it at the wrong time.  The problem might be better
 addressed in the other direction by avoiding the repeated fast committing
 transaction.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8680#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler