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

25 Apr 2017


      #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:                    |
-------------------------------------+-------------------------------------

@@ -9,1 +9,1 @@
- to perform in-place `HashMap` updates using `unsafe{Thaw,Freeze}`.
+ to effect in-place `HashMap` updates using `unsafe{Thaw,Freeze}`.
@@ -12,2 +12,2 @@
- leak
- out, so using in-place updates seem valid to me.
+ possibly leak
+ out, so in-place updates seem valid to me.
@@ -29,2 +29,3 @@
- copy-and-update to make things work―patch `unsafeInsertWith` on the
- `BitmapIndexed` branch as follows:
+ 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:

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 with `"solving\n0.0"`, 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

 And the original text of ''this'' report can be found here, in case my
 editor fucked up or left anything out:
 http://lpaste.net/diff/6339195854280196096/6983816376066506752

--

Comment (by liyang):

 I have editorised the text further. Sorry.

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

    