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)
GHC
ghc-devs at haskell.org
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
More information about the ghc-tickets
mailing list