Re: [GHC] #13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators

[GHC]

#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators
-------------------------------------+-------------------------------------
        Reporter:  pacak             |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.2.1
       Component:  Compiler          |              Version:  8.2.1-rc2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Incorrect result  |  Unknown/Multiple
  at runtime                         |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by bgamari):

 So it appears that the intermediate mutable arrays from `unsafeInsertWith`
 are somehow "leaking" out of the fold. Consider this variant of
 `unsafeInsertWith`'s `BitIndexed` codepath,
 {{{#!hs
     go h k x s (BitmapIndexed b ary)
         | b .&. m == 0 = do
             let ary' = A.insert ary i $! leaf h k x
             return $! bitmapIndexedOrFull (b .|. m) ary'
         | otherwise = do
             st <- A.indexM ary i
             st' <- ({-# SCC "hi3" #-}rnf x) `seq` go h k x
 (s+bitsPerSubkey) st
             let !ary' = A.update ary i $! st'
             A.unsafeUpdateM ary i (error "fiddlesticks")
             return $ BitmapIndexed b ary'
       where m = mask h s
             i = sparseIndex b m
 }}}

 Now, as far as I can tell, if no one has kept any references to the
 `HashMap` that `unsafeInsertWith` is inserting into there should be no way
 that we enter `error "fiddlesticks"`. Afterall, the array `ary` is dead
 after we finish evaluating `go`.

 However, in actuality this doesn't appear to be true: `fiddlesticks` is
 indeed entered! Namely, it is forced by the `rnf` at the beginning of
 `unsafeInsertWith`.
 {{{#!hs
 unsafeInsertWith f k0 v0 m0 = ({-# SCC "top" #-}rnf m0) `seq` runST (go h0
 k0 v0 0 m0)
 }}}
 Now this is quite strange as it means that either,

 a. a reference to the old `ary` is somehow leaking out of `go`
 b. there are multiple references to `ary` scattered throughout the
 `HashMap`

 It's not immediately obvious how either of these could be true, but the
 facts don't lie.

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