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:                    |
-------------------------------------+-------------------------------------
Description changed by pacak:

@@ -49,1 +49,1 @@
- This will either finish successfully with `"solving\n0.0"`, or will die
+ This will either finish successfully producing no output, or will die

New description:

 The example below uses in-place copies (mostly to fix dependencies
 and to make it more self-contained) of `parallel` (modified),
 `unordered-containers` (modified), and `hashable`. Its behavior is
 nondeterministic, despite using only supposedly pure operations.

 Aforementioned aside, it only depends on `base` and `deepseq`, and there's
 no `unsafePtrEq` involved at all. The affected `fromListWith` uses
 `foldl'`
 to effect in-place `HashMap` updates using `unsafe{Thaw,Freeze}`.

 I don't see how references to intermediate versions of `HashMap` could
 possibly leak
 out, so in-place updates seem valid to me.

 Strictifying (or even `rnf`ing) the arguments to `unsafeInsertWith`
 doesn't
 help. The issue is reproducible with `-O0` on `HEAD` but not with `-O2`;
 On
 8.0.2 and 7.10.1, it can also be reproduced with `-O2`.

 {{{
 sum . map snd = sum . map snd . toList . fromListWith (+)
 }}}

 The above identity fails when the input contains values constructed using
 ''both'' memo combinators and parallel evaluation strategies.

 I have identified the in-place-update that needs to be replaced with
 copy-and-update to make things work―patch `unsafeInsertWith.go` in
 `unordered-containers-0.2.8.0/Data/HashMap/Strict.hs`, under the
 `BitmapIndexed` pattern as follows:

 {{{
 -            A.unsafeUpdateM ary i st'
 -            return t
 +            let ary' = A.update ary i st'
 +            return $ BitmapIndexed b ary'
 }}}

 Steps to reproduce:

 {{{
 git clone https://github.com/pacak/cuddly-bassoon && cd cuddly-bassoon
 cabal new-build
 dist-newstyle/build/gamebooksolver-0.1.0.0/build/gamebooksolver-
 solvebook02/gamebooksolver-solvebook02
 }}}

 This will either finish successfully producing no output, or will die
 with an `error` from the `regroup` function in `src/Solver.hs`.

 Your machine must have at least 2 CPU cores to reproduce the problem; also
 it will not show up with `+RTS -N1`.

 This issue was first reported here:
 https://github.com/tibbe/unordered-containers/issues/147

--

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