#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