Re: [GHC] #13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators (was: Wrong results from what supposed to be pure function with presense of parallel evaluation)

Wed Apr 26 02:40:23 UTC 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:                    |
-------------------------------------+-------------------------------------
Changes (by liyang):

 * cc: liyang (added)


@@ -1,4 +1,4 @@
- The program linked below uses modified (mostly to trim down on
- dependencies) copies of parallel and unordered-containers. Its behavior is
- nondeterministic, even though all the operations it uses are supposed to
- be pure
+ 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.
@@ -6,0 +6,4 @@
+ Aforementioned aside, it only depends on `base` and `deepseq`, and there's
+ no `unsafePtrEq` involved at all. The affected `fromListWith` uses
+ `foldl'`
+ to perform in-place `HashMap` updates using `unsafe{Thaw,Freeze}`.
@@ -7,4 +11,3 @@
- Mostly self contained sample - only depends on base, deepseq and locally
- provided hashable and unordered-containers. No unsafePtrEq involved, but
- unsafeThaw/Freese  is - affected function uses `foldl'` to insert stuff
- into hashmap.
+ I don't see how references to intermediate versions of `HashMap` could
+ leak
+ out, so using in-place updates seem valid to me.
@@ -12,10 +15,5 @@
-
- unsafeThaw/Freeze are used to perform implace updates on a HashMap inside
- fromListWith function. Updates are sequential and performed with `foldl'`,
- I don't see obvious ways of obtaining references to intermediate versions
- of HashMap so inplace updates seems to be valid.
-
- Making arguments to unsafeInsertWith strict or rnf'ing them doesn't help.
-
- Issue is reproduceable with HEAD with -O0 but not with O2. in ghc 8.0.2
- and 7.10.1 it's reproduceable with -O2 as well.
+ 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`.
@@ -24,1 +22,1 @@
- sum (map snd xs) = sum (map snd (toList $ fromListWith (+) xs))
+ sum . map snd = sum . map snd . toList . fromListWith (+)
@@ -27,2 +25,2 @@
- ^ this statement fails to hold when xs contains stuff with memocombinators
- and parallel evaluation from evaluation strategies
+ The above identity fails when the input contains values constructed using
+ ''both'' memo combinators and parallel evaluation strategies.
@@ -30,4 +28,3 @@
-
- I found which inplace update needs to be replaced with copy and update to
- make  things work - bug is fixed after changing unsafeInsertWith,
- BitmapIndexed branch:
+ I have identified the in-place-update that needs to be replaced with
+ copy-and-update to make things work―patch `unsafeInsertWith` on the
+ `BitmapIndexed` branch as follows:
@@ -38,1 +35,1 @@
- +            let  ary' = A.update ary i st'
+ +            let ary' = A.update ary i st'
@@ -42,5 +39,1 @@
-
-
- Steps:
-
- clone this:
+ Steps to reproduce:
@@ -49,1 +42,4 @@
- https://github.com/pacak/cuddly-bassoon
+ 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
@@ -52,3 +48,2 @@
- {{{
- stack build
- }}}
+ This will either finish successfully with `"solving\n0.0"`, or will die
+ with an `error` from the `regroup` function in `src/Solver.hs`.
@@ -56,4 +51,2 @@
- {{{
-  ./.stack-work/install/x86_64-linux/ghc-8.0.2/8.0.2/bin/gamebooksolver-
- solvebook02
- }}}
+ Your machine must have at least 2 CPU cores to reproduce the problem; also
+ it will not show up with `+RTS -N1`.
@@ -61,2 +54,2 @@
- Last command will either finish successfully printing `"solving\n0.0"` or
- will die with `error` in `src/Solver.hs` `regroup` function.
+ This issue was first reported here:
+ https://github.com/tibbe/unordered-containers/issues/147
@@ -64,3 +57,3 @@
-
- To reproduce the problem computer must have at least 3 CPUs, running with
- +RTS -N1 or -N2 "fixes" the problem.
+ 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

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 perform in-place `HashMap` updates using `unsafe{Thaw,Freeze}`.

 I don't see how references to intermediate versions of `HashMap` could
 leak
 out, so using 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` on the
 `BitmapIndexed` branch 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:

 I've editorised the text of the original bug report. Pray I do not
 editorise it further.

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