[GHC] #13615: Wrong results from what supposed to be pure function with presense of parallel evaluation
#13615: Wrong results from what supposed to be pure function with presense of parallel evaluation -------------------------------------+------------------------------------- Reporter: pacak | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1-rc2 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: -------------------------------------+------------------------------------- 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 think there's a way to obtain multiple references to the same map. Making arguments 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. {{{ sum (map snd xs) = map snd (toList $ fromListWith (+) xs) }}} ^ this statement fails to hold when xs contains stuff with memocombinators and parallel evaluation from evaluation strategies 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: {{{ - A.unsafeUpdateM ary i st' - return t + let ary' = A.update ary i st' + return $ BitmapIndexed b ary' }}} Steps: clone this: {{{ https://github.com/pacak/cuddly-bassoon }}} {{{ stack build }}} {{{ ./.stack-work/install/x86_64-linux/ghc-8.0.2/8.0.2/bin/gamebooksolver- solvebook02 }}} Last command will either finish successfully printing `"solving\n0.0"` or will die with `error` in `src/Solver.hs` `regroup` function. To reproduce the problem computer must have at least 3 CPUs, running with +RTS -N1 or -N2 "fixes" the problem. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Wrong results from what supposed to be pure function with presense of parallel evaluation -------------------------------------+------------------------------------- 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 bgamari): * priority: normal => highest * milestone: => 8.2.1 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Wrong results from what supposed to be pure function with presense of parallel evaluation -------------------------------------+------------------------------------- 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: | -------------------------------------+------------------------------------- Comment (by mpickering): Can also build easily with "cabal new-build". -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Wrong results from what supposed to be pure function with presense of parallel evaluation -------------------------------------+------------------------------------- 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: @@ -0,0 +1,6 @@ + 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 + + @@ -4,2 +10,9 @@ - into hashmap - I don't think there's a way to obtain multiple references - to the same map. Making arguments strict or rnf'ing them doesn't help. + into hashmap. + + + 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. @@ -11,1 +24,1 @@ - sum (map snd xs) = map snd (toList $ fromListWith (+) xs) + sum (map snd xs) = sum (map snd (toList $ fromListWith (+) xs)) New description: 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 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. 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. {{{ sum (map snd xs) = sum (map snd (toList $ fromListWith (+) xs)) }}} ^ this statement fails to hold when xs contains stuff with memocombinators and parallel evaluation from evaluation strategies 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: {{{ - A.unsafeUpdateM ary i st' - return t + let ary' = A.update ary i st' + return $ BitmapIndexed b ary' }}} Steps: clone this: {{{ https://github.com/pacak/cuddly-bassoon }}} {{{ stack build }}} {{{ ./.stack-work/install/x86_64-linux/ghc-8.0.2/8.0.2/bin/gamebooksolver- solvebook02 }}} Last command will either finish successfully printing `"solving\n0.0"` or will die with `error` in `src/Solver.hs` `regroup` function. To reproduce the problem computer must have at least 3 CPUs, running with +RTS -N1 or -N2 "fixes" the problem. -- -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Wrong results from what supposed to be pure function with presense of parallel evaluation -------------------------------------+------------------------------------- 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Interesting, forcing `st'` before passing it to `unsafeUpdateM` in the the `BitmapIndexed` branch of `Data.HashMap.Strict.unsafeInsertWith` also seems to fix the issue. I haven't thought much about why. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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
#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
#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 liyang: @@ -57,4 +57,0 @@ - - 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 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 -- -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by pacak): I pushed a bunch of simplification commits to the repo, failure chance went down a bit but still within 10-20% on my machine. If you can't reproduce the problem - try first commit. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): While playing around with the repro, I noticed that the issue is reproducible if the `unsafeUpdateM` is performed, even if the resulting `HashMap` doesn't refer to the old array. e.g., {{{#!hs go h k x s t@(BitmapIndexed b ary) | b .&. m == 0 = do let ary' = A.insert ary i $! leaf h k x return $! bitmapIndexedOrFull (b .|. m) ary' | otherwise = do st <- A.indexM ary i st' <- rnf x `seq` go h k x (s+bitsPerSubkey) st let !ary' = A.update ary i $! st' A.unsafeUpdateM ary i st' return $ BitmapIndexed b ary' where m = mask h s i = sparseIndex b m }}} I'm not yet sure whether this is a meaninfgul observation, but it is an observation nonetheless. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): I have confirmed that eliminating the use of `parMap` in `solve` eliminates the issue as does replacing `rdeepseq` with `rseq`. I don't know whether the use of the `memo` combinator contributes as runtime blows up when it is removed Both uses of `A.unsafeUpdateM` in `unsafeInsertWith` (one in the `BitmapIndexed` branch and one in the `Full` branch) are problematic. Replacing either one with `A.update` decreases the failure rate, but the rate is still non-zero. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): So it appears that the intermediate mutable arrays from `unsafeInsertWith` are somehow "leaking" out of the fold. Consider this variant of `unsafeInsertWith`'s `BitIndexed` codepath, {{{#!hs go h k x s (BitmapIndexed b ary) | b .&. m == 0 = do let ary' = A.insert ary i $! leaf h k x return $! bitmapIndexedOrFull (b .|. m) ary' | otherwise = do st <- A.indexM ary i st' <- ({-# SCC "hi3" #-}rnf x) `seq` go h k x (s+bitsPerSubkey) st let !ary' = A.update ary i $! st' A.unsafeUpdateM ary i (error "fiddlesticks") return $ BitmapIndexed b ary' where m = mask h s i = sparseIndex b m }}} Now, as far as I can tell, if no one has kept any references to the `HashMap` that `unsafeInsertWith` is inserting into there should be no way that we enter `error "fiddlesticks"`. Afterall, the array `ary` is dead after we finish evaluating `go`. However, in actuality this doesn't appear to be true: `fiddlesticks` is indeed entered! Namely, it is forced by the `rnf` at the beginning of `unsafeInsertWith`. {{{#!hs unsafeInsertWith f k0 v0 m0 = ({-# SCC "top" #-}rnf m0) `seq` runST (go h0 k0 v0 0 m0) }}} Now this is quite strange as it means that either, a. a reference to the old `ary` is somehow leaking out of `go` b. there are multiple references to `ary` scattered throughout the `HashMap` It's not immediately obvious how either of these could be true, but the facts don't lie. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): Hypothesis: `thawArray#` is to blame. Falsified by falling back to `__GLASGOW_HAKSELL__ < 702` codepath in `Data.HashMap.Array.thaw`. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): For the record, I've also tested with `-fno-full-laziness`; the issue persists. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by pacak): {{{ <bgamari> gamebooksolver-solvebook02: Those are expected to be equal(6030,6030) <bgamari> GHC has an interesting sense of equality }}} Code that generates this error looks like this and both `s'` and `s` are `Int`s. {{{ if s' /= s then error $ "Those are expected to be equal" ++ show (s', s) else xs' }}} I don't see how that's possible unless `Eq` instance for `Int` gets corrupted somehow. If that's the case - it also might mean `Num` instance is bogus as well and that results in wrong sum. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by pacak): I've confirmed that ghc has an interesting sense of equality: {{{ regroup :: (NFData a, Show a, Hashable a, Eq a, Ord a) => [(a, Int)] -> [(a, Int)] regroup xs = let xs' = HM.toList $ HM.fromListWith (+) xs s' = sum (map snd xs') s = sum (map snd xs) in if s' /= s then if show s' == show s then error "WAT????" else error $ "Those are expected to be equal" ++ show (s', s) else xs' }}} {{{ gamebooksolver-solvebook02: Those are expected to be equal(141,121) CallStack (from HasCallStack): error, called at src/Main.hs:50:26 in main:Main gamebooksolver-solvebook02: Those are expected to be equal(384,300) CallStack (from HasCallStack): error, called at src/Main.hs:50:26 in main:Main gamebooksolver-solvebook02: Those are expected to be equal(1045,1045) CallStack (from HasCallStack): error, called at src/Main.hs:50:26 in main:Main gamebooksolver-solvebook02: WAT???? CallStack (from HasCallStack): error, called at src/Main.hs:49:26 in main:Main gamebooksolver-solvebook02: WAT???? CallStack (from HasCallStack): error, called at src/Main.hs:49:26 in main:Main gamebooksolver-solvebook02: WAT???? CallStack (from HasCallStack): error, called at src/Main.hs:49:26 in main:Main }}} Actually it's even worse, note third error. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:16> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): Indeed I have also observed similar insanity to comment:16. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:17> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): Note that the probability of seeing the issue increases markedly if `regroup` is defined as, {{{#!hs regroup :: (NFData a, Show a, Hashable a, Eq a, Ord a) => [(a, Int)] -> [(a, Int)] regroup xs0 = let xs = map (\(x,y) -> (x, y+1)) xs0 xs' = HM.toList $ HM.fromListWith (+) xs s' = sum (map snd xs') s = sum (map snd xs) in if s' /= s then if show s' == show s then error "WAT????" else error $ "Those are expected to be equal" ++ show (s', s) else xs' }}} It appears that elements are getting dropped from the list inspected by `fromListWith` (which is why the `(+1)` makes the issue easier to see: you won't notice if you drop a zero from a sum) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:18> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): `-feager-blackholing` also makes no difference. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:19> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): So perhaps we are entering a closure twice and consequently get a race condition where one thread in-place increments a hashtable entry by `x`, then the other does the same, but uses the now already incremented hashtable, resulting in an overall contribution of `2*x`. This explains why the hashtable sum is always larger than the expected result. While it's not clear precisely what closure we are entering multiple times, the fix is clear: ensure that `unordered-containers` is compiled with `-feager-blackholing`. However, we should also (at very least) document this caveat better. The users-guide current advertises `-feager- blackholing` as a optimization to avoid redundant computation in parallel programs. However, in this case that it's absolutely critical for correctness. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:20> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): For future reference, the `-feager-blackholing` flag was introduced in GHC 6.12. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:21> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by akio): `-feager-blackholing` does not eliminate the race completely, right? I thought you needed a call to `noDuplicate#` in order to guarantee single entry. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:22> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): Indeed you may be right; I'll need to try to work out precisely where the multiple entry is occurring tomorrow. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:23> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by simonpj): Why does it matter if we evaluate the same thunk twice? I'm lost. Simon -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:24> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari):
Why does it matter if we evaluate the same thunk twice? I'm lost.
Well, I'm still not entirely certain what the problematic thunk looks like, but the program in question *does* rely on in-place modification of an array which would break if performed more than once. I believe the problem revolves around `Data.HashMap.Strict.unsafeInsertWith`, which, to paraphrase, does the following, {{{#!hs unsafeInsertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v unsafeInsertWith f k v (HashMap arr) = runST $ do marr <- unsafeThawArray# arr let some_index = {- some function of k -} old_v <- readArray# marr some_index writeArray# marr some_index (f old_v v) _ <- unsafeFreezeArray# marr return (HashMap arr) }}} That is, despite being a "pure" function, `unsafeInsertWith` take the array out of the `HashMap` which it was given, thaws it, modifies it, freezes it again, and then returns the same array as a "new" result. This means that if we have a thunk `unsafeInsertWith some_key some_value hm` which we enter twice, the multiple entry will be observable through the fact that the array element at `some_index` will be `f v (f v old_v)`, instead of `f v old_v` as was intended. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:25> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by bgamari): I've put this aside for now. The current state of things is, * My current theory is that a closure is being entered multiple times, resulting in repeated observable mutation. It's still not entirely clear precisely which closure is being entered multiple times, but the evidence before us is consistent with the multiple mutation hypothesis. * compiling `unordered-containers` with `-feager-blackholing` appears to resolve the issue, however I'm pretty certain that this is merely shrinking the race window, not eliminating it altogether. * adding a `noDuplicate#` (e.g. see https://github.com/bgamari/unordered- containers/commit/bf799b2a00da8c78ac78d818de8f1963c7ff87ad) at the beginning of `unsafeInsertWith` also resolves the issue, even with lazy blackholing enabled. However, this seems like a very large hammer to place in an inner loop like this. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:26> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"228d4670e98e4fd998c847aac38c11ad85aa35a7/ghc" 228d4670/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="228d4670e98e4fd998c847aac38c11ad85aa35a7" Use memcpy in cloneArray While looking at #13615 I noticed that there was this strange open-coded memcpy in the definition of the cloneArray macro. I don't see why this should be preferable to memcpy. Test Plan: Validate, particularly focusing on array operations Reviewers: simonmar, tibbe, austin, alexbiehl Reviewed By: tibbe, alexbiehl Subscribers: alexbiehl, rwbarton, thomie Differential Revision: https://phabricator.haskell.org/D3504 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:27> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: | -------------------------------------+------------------------------------- Comment (by glguy): I believe I was experiencing this same bug in code that used Foreign.Marshal.Unsafe.unsafeLocalState and par together https://github.com/glguy/kami-solver/blob/master/src/Kami.hs#L172-L181 unsafeLocalState is defined as unsafeDupablePerformIO. Switching to unsafePerformIO (which adds the noDuplicate) resolved the random segmentation faults. I'm just adding this comment here in case it becomes useful at some point. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:28> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: (none) Type: bug | Status: new Priority: highest | Milestone: 7.10.4 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 bgamari): * milestone: 8.2.1 => 7.10.4 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:29> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#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: 7.10.3 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 bgamari): * version: 8.2.1-rc2 => 7.10.3 * milestone: 7.10.4 => 8.2.1 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:30> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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 bgamari): * owner: (none) => bgamari -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:31> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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 asr): * cc: asr (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:32> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): So with `-A8k` the incorrect behavior seems to disappear entirely, but with the expected degradation in performance. However, it's hard to rule out that this is merely due a change in timings. However, I've also confirmed that we are indeed entering `unsafeInsertWith` multiple times on the same `HashMap`. I've instrumented `unsafeInsertWith` to record when it is entered (within the context of a particular `fromListWith` call) and found that indeed we do see multiple threads entering concurrently. Looking at the stacks of the threads involved in the multiple entry, I see some highly suspicious behavior. Namely, the top twenty or so frames are nearly identical. For instance, we have {{{#!diff --- <unnamed> +++ <unnamed> @@ -1,7 +1,11 @@ -thread 17 (entered first) +thread 16 (entered second) ----------------------------------- 0: RET_SMALL + return = 0x434298 <rxSU_info+72> (symbol and line for ./Data/HashMap/Strict.hs, line 93) + field 0: Ptr 0x434298 <rxSU_info+72> + field 1: Word 283476377554 +1: RET_SMALL return = 0x439338 <sy5n_info+272> (symbol and line for ./Data/HashMap/Strict.hs, line 166) field 0: Ptr 0x439338 <sy5n_info+272> field 1: Ptr 0x420072cea0 @@ -11,36 +15,36 @@ field 5: Ptr 0x42008230b0 field 6: Ptr 0x420082312d field 7: Word 283476377554 -1: RET_SMALL +2: RET_SMALL return = 0x439498 <unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216> (symbol and line for ./Data/HashMap/Strict.hs, line 160) -2: UPDATE_FRAME(0x4200810610: BLACKHOLE(0x420046661a: constr)) -3: RET_SMALL +3: UPDATE_FRAME(0x4200810610: BLACKHOLE(0x420046661a: constr)) +4: RET_SMALL return = 0x44c790 <snqC_info+88> (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 <snqC_info+88> field 1: Word 283476373666 -4: UPDATE_FRAME(0x4200810678: BLACKHOLE(0x42004694fa: constr)) -5: RET_SMALL +5: UPDATE_FRAME(0x4200810678: BLACKHOLE(0x42004694fa: constr)) +6: RET_SMALL return = 0x471b98 <base_GHCziBase_map_info+192> (symbol and line for libraries/base/GHC/Base.hs, line 946) field 0: Word 4660120 -6: UPDATE_FRAME(0x42008106b0: BLACKHOLE(0x4200469552: constr)) -7: RET_SMALL +7: UPDATE_FRAME(0x42008106b0: BLACKHOLE(0x4200469552: constr)) +8: RET_SMALL return = 0x4af310 <s4Vv_info+56> (symbol and line for libraries/base/GHC/List.hs, line 187) field 0: Word 4911888 field 1: Word 283476373528 field 2: Ptr 0x420082305a -8: RET_SMALL +9: RET_SMALL return = 0x40abb8 <sr4u_info+232> (symbol and line for src/Solver.hs, line 41) field 0: Word 4238264 field 1: Ptr 0x4200822f78 field 2: Word 283476373392 field 3: Ptr 0x4200822ee0 field 4: Ptr 0x4200822f00 -9: UPDATE_FRAME(0x42008106e0: BLACKHOLE(0x42004414b0: THUNK)) -10: RET_SMALL +10: UPDATE_FRAME(0x42008106e0: BLACKHOLE(0x42004414b0: THUNK)) +11: RET_SMALL return = 0x471d10 <s5BF_info+168> (symbol and line for libraries/base/GHC/Base.hs, line 860) field 0: Word 4660496 -11: UPDATE_FRAME(0x4200724cf8: THUNK) -12: RET_SMALL +12: UPDATE_FRAME(0x4200724cf8: THUNK) +13: RET_SMALL return = 0x4392c8 <sy5n_info+160> (symbol and line for ./Data/HashMap/Strict.hs, line 164) field 0: Word 4428488 field 1: Word 283469122208 @@ -48,86 +52,85 @@ field 3: Ptr 0x7ec538 field 4: Ptr 0x4200138a90 field 5: Ptr 0x4200138b0d - field 6: Ptr 0x420007ae22 -13: RET_SMALL + field 6: Ptr 0x4200724e9a +14: RET_SMALL return = 0x439498 <unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216> (symbol and line for ./Data/HashMap/Strict.hs, line 160) -14: UPDATE_FRAME(0x420010bb98: AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8)) -15: RET_SMALL +15: UPDATE_FRAME(0x420010bb98: AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8)) +16: RET_SMALL return = 0x44c790 <snqC_info+88> (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 <snqC_info+88> field 1: Word 283469122178 -16: UPDATE_FRAME(0x420010bc00: AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20)) -17: RET_SMALL +17: UPDATE_FRAME(0x420010bc00: AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20)) +18: RET_SMALL return = 0x471b98 <base_GHCziBase_map_info+192> (symbol and line for libraries/base/GHC/Base.hs, line 946) field 0: Word 4660120 -18: UPDATE_FRAME(0x420010bc38: AP_STACK(size=2, fun=AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20), payload=0x420010bc58)) -19: RET_SMALL +19: UPDATE_FRAME(0x420010bc38: AP_STACK(size=2, fun=AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20), payload=0x420010bc58)) +20: RET_SMALL return = 0x4af310 <s4Vv_info+56> (symbol and line for libraries/base/GHC/List.hs, line 187) field 0: Word 4911888 field 1: Word 283469122040 field 2: Ptr 0x4200138a3a -20: RET_SMALL +21: RET_SMALL return = 0x40abb8 <sr4u_info+232> (symbol and line for src/Solver.hs, line 41) field 0: Word 4238264 field 1: Ptr 0x4200138968 field 2: Word 283469121920 field 3: Ptr 0x42001388d0 field 4: Ptr 0x42001388f0 -21: UPDATE_FRAME(0x420010bc68: AP_STACK(size=10, fun=AP_STACK(size=2, fun=AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20), payload=0x420010bc58), payload=0x420010bc88)) -22: UPDATE_FRAME(0x4200056810: BLACKHOLE(0x420000bc50: TSO)) -23: RET_SMALL +22: UPDATE_FRAME(0x420010bc68: AP_STACK(size=10, fun=AP_STACK(size=2, fun=AP_STACK(size=3, fun=AP_STACK(size=9, fun=BLACKHOLE(0x4200724062: constr), payload=0x420010bbb8), payload=0x420010bc20), payload=0x420010bc58), payload=0x420010bc88)) +23: UPDATE_FRAME(0x420086c660: BLACKHOLE(0x420086f000: TSO)) +24: RET_SMALL return = 0x471d38 <s5BF_info+208> (symbol and line for libraries/base/GHC/Base.hs, line 859) field 0: Ptr 0x471d38 <s5BF_info+208> - field 1: Word 283468195841 -24: UPDATE_FRAME(0x4200056560: BLACKHOLE(0x420000bc50: TSO)) -25: RET_SMALL + field 1: Word 283476674129 +25: UPDATE_FRAME(0x420086c3b0: BLACKHOLE(0x420086f000: TSO)) +26: RET_SMALL return = 0x4392c8 <sy5n_info+160> (symbol and line for ./Data/HashMap/Strict.hs, line 164) field 0: Word 4428488 - field 1: Word 283468195696 - field 2: Word 283468195296 + field 1: Word 283476673984 + field 2: Word 283476673584 field 3: Ptr 0x7e60c8 - field 4: Ptr 0x4200056760 - field 5: Ptr 0x42000567dd + field 4: Ptr 0x420086c5b0 + field 5: Ptr 0x420086c62d field 6: Ptr 0x7ee011 -26: RET_SMALL +27: RET_SMALL return = 0x439498 <unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216> (symbol and line for ./Data/HashMap/Strict.hs, line 160) -27: UPDATE_FRAME(0x4200056718: BLACKHOLE(0x420000bc50: TSO)) -28: RET_SMALL +28: UPDATE_FRAME(0x420086c568: BLACKHOLE(0x420086f000: TSO)) +29: RET_SMALL return = 0x44c790 <snqC_info+88> (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 <snqC_info+88> - field 1: Word 283468195666 -29: UPDATE_FRAME(0x4200056650: BLACKHOLE(0x420000bc50: TSO)) -30: RET_SMALL + field 1: Word 283476673954 +30: UPDATE_FRAME(0x420086c4a0: BLACKHOLE(0x420086f000: TSO)) +31: RET_SMALL return = 0x471b98 <base_GHCziBase_map_info+192> (symbol and line for libraries/base/GHC/Base.hs, line 946) field 0: Word 4660120 -31: UPDATE_FRAME(0x4200056688: BLACKHOLE(0x420000bc50: TSO)) -32: RET_SMALL +32: UPDATE_FRAME(0x420086c4d8: BLACKHOLE(0x420086f000: TSO)) +33: RET_SMALL return = 0x4af310 <s4Vv_info+56> (symbol and line for libraries/base/GHC/List.hs, line 187) field 0: Word 4911888 - field 1: Word 283468195528 - field 2: Ptr 0x420005670a -33: RET_SMALL + field 1: Word 283476673816 + field 2: Ptr 0x420086c55a +34: RET_SMALL return = 0x40abb8 <sr4u_info+232> (symbol and line for src/Solver.hs, line 41) field 0: Word 4238264 - field 1: Ptr 0x4200056638 - field 2: Word 283468195408 - field 3: Ptr 0x42000565a0 - field 4: Ptr 0x42000565c0 -34: UPDATE_FRAME(0x4200056528: BLACKHOLE(0x420000bc50: TSO)) -35: RET_SMALL + field 1: Ptr 0x420086c488 + field 2: Word 283476673696 + field 3: Ptr 0x420086c3f0 + field 4: Ptr 0x420086c410 +35: UPDATE_FRAME(0x420086c378: BLACKHOLE(0x420086f000: TSO)) +36: RET_SMALL return = 0x471d38 <s5BF_info+208> (symbol and line for libraries/base/GHC/Base.hs, line 859) field 0: Ptr 0x471d38 <s5BF_info+208> - field 1: Word 283468195081 -36: UPDATE_FRAME(0x4200056258: BLACKHOLE(0x420000bc50: TSO)) -37: RET_SMALL + field 1: Word 283476673369 +37: UPDATE_FRAME(0x420086c0a8: BLACKHOLE(0x420086f000: TSO)) +38: RET_SMALL return = 0x4392c8 <sy5n_info+160> (symbol and line for ./Data/HashMap/Strict.hs, line 164) field 0: Word 4428488 - field 1: Word 283468194936 - field 2: Word 283468194536 + field 1: Word 283476673224 + field 2: Word 283476672824 field 3: Ptr 0x7ebb39 - field 4: Ptr 0x4200056468 - field 5: Ptr 0x42000564e5 + field 4: Ptr 0x420086c2b8 + field 5: Ptr 0x420086c335 field 6: Ptr 0x7ee011 -38: RET_SMALL +39: RET_SMALL return = 0x439498 <unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216> (symbol and line for ./Data/HashMap/Strict.hs, line 160) -39: UPDATE_FRAME(0x4200056420: BLACKHOLE(0x420000bc50: TSO)) }}} Here we see that the threads' stacks differ by only a single word (save frame 0, which is merely an artifact of my instrumentation) in the first 21 frames. Intriguingly, they begin to differ after frame 21/22, which is an update frame updating an `AP_STACK`. Strangely, the only way that we can end up with such a closure is via the `raiseAsync` machinery or via the bytecode interpreter. There's clearly still more digging to do. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:33> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Ahh, of course; the `AP_STACK` is presumably being produced by `raiseAsync` while suspending a thread in preparation for GC. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:34> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): One interesting observation is that the issue persists even if the list passed to `fromListWith` is fully forced; that is, {{{#!hs let xs' = deepseq xs `seq` HM.toList (HM.fromListWith (+) xs) }}} instead of {{{#!hs let xs' = HM.toList (HM.fromListWith (+) xs) }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:35> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Alright, I think I have a theory for how we end up getting multiple entries despite having no thunk allocation inside `fromListWith`: 1. Thread A enters a `fromListWith` closure and begins folding over the insertions 2. At some point during this fold we need to garbage collect; the garbage collector constructs an `AP_STACK` closure capturing the state of Thread A, including the partially-finished `fromListWith` computation 3. Garbage collection commences and finishes, evaluation resumes 4. At some point Thread A is resumed, picking up the previously suspended `fromListWith` computation; we are blackholing lazily so no update to the closure is made 5. At some later Thread B tries to force the same `fromListWith` computation; finding that it's not blackholed it enters 6. We now have two mutator threads performing evaluation on the same, effectful computation with shared, mutable state. Does this sound plausible? The only bit that I'm a bit hazy on is point (5). That is, how is it that Thread B is able to enter the suspended computation given that (if I understand correctly) Thread A won't update the original `fromListWith` until finishes its evaluation and pops its associated update frame. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:36> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by dfeuer): I've written a [https://github.com/treeowl/unordered-containers/tree /super-safe seriously legitimate modification] of `Data.HashMap.Strict.fromListWith` that Ben indicates still demonstrates the problem. This version uses a separate type of mutable hashmap that holds `MArray`s. When it's done, it traverses the tree and (unsafely) freezes all the arrays. Unless I've goofed up, there should be no doubt that this version should work correctly. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:37> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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 dfeuer): * cc: dfeuer (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:38> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): simonmar, does comment:36 sound at all plausible? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:39> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): I should also mention that the variant prepared by dfeuer in comment:37 also exhibits this bug. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:40> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by andrewthad): I have simplified the example failure here: https://github.com/andrewthad /cuddly-bassoon/tree/9e87acbc43b10d38758e6263b8d17231cb1f3ed7 In this commit, I entirely removed the use of hashmap and hashable. I'm just adding up the numbers in an STRef, and the problem still shows up. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:41> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by pacak): {{{ runST = unsafeDupablePerformIO -- more or less }}}
`unsafeDupablePerformIO`: This version of `unsafePerformIO` is more efficient because it omits the check that the IO is only being performed by a single thread.
Basically "not to be used in multiple threads, we really mean it, look at the name"
`par`: Indicates that it may be beneficial to evaluate the first argument in parallel with the second.
Basically "do things in multiple threads". The problem is `unsafeDupablePerformIO` is hidden in a bunch of different places. HashMaps, ByteStrings, etc... `par` is less frequent but not used directly either but it's also out there. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:42> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by andrewthad): pacak, it should in general be safe to duplicate an ST computation on multiple threads. For IO, it's a problem because mutable variables can come from outside of the IO computation. Something like `unsafeDupablePerformIO (modifyIORef ...)` is bad because for this reason. But, with ST, variables cannot escape the scope of the computation, so it should be safe. There is no way to write the ST equivalent of the expression I just gave. You would instead have to write: `runST (do {r <- newSTRef 5; modifySTRef r ...;})`, but this should be safe to duplicate, since each thread ends up with its own STRef (no sharing of the reference across threads). Also worth mentioning is that GHC cannot float out the call to `newSTRef` because of how the state token is threaded through the computation in `ST`s `Monad` instance. In #11760, it was discovered that lazy ST was unsound because it allows you to create pure expressions that capture mutable variables. When one of these expression is evaluated on two capabilities simultaneously, we get nondeterministic results. According to people on that thread, strict ST should not have the same problem. I don't totally understand why. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:43> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari):
According to people on that thread, strict ST should not have the same problem. I don't totally understand why.
In the case of strict ST all effects should be executed before we produce the result. This means that there should be no chance of entering any thunk arising from the `ST` block producing effects, meaning that multiple entry should pose no thread to correctness. However, if my hypothesis from comment:36 holds then it is indeed possible for the garbage collector to suspend a computation before all effects have taken place. This places us in a position where multiple-entry will indeed cause effects to be performed multiple times. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:44> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): I have confirmed that we indeed hit the codepath in `raiseAsync` responsible for updating the thunk under evaluation. I believe this fills the final question in comment:36. To recap, what is happening is the following, 1. Thread A enters a `fromListWith` closure and begins folding over the insertions 2. At some point during this fold we need to garbage collect (usually due to a stack overflow, judging from the eventlog); the garbage collector construct an `AP_STACK` closure capturing the state of Thread A, including the partially-finished `fromListWith` computation. The `fromListWith` thunk is updated to point to this `AP_STACK`. 3. Garbage collection commences and finishes, evaluation resumes 4. At some point Thread A is resumed, entering the previously saved `AP_STACK` computation which we prepared in step (2); we are blackholing lazily so no update to the `AP_STACK` closure is made 5. At some later point Thread B tries to force the same `AP_STACK` computation; finding that it's not blackholed, it enters We now have two mutator threads performing evaluation on the same, effectful computation with shared, mutable state. My first intuition says that the easiest way to avoid this would be to unconditionally eagerly blackhole `AP_STACK`s. I believe this can be done straightforwardly, {{{#!diff diff --git a/rts/Apply.cmm b/rts/Apply.cmm index f14bb8f331..a35b41e5b0 100644 --- a/rts/Apply.cmm +++ b/rts/Apply.cmm @@ -464,6 +464,16 @@ INFO_TABLE(stg_AP_STACK,/*special layout*/0,0,AP_STACK,"AP_STACK","AP_STACK") Words = StgAP_STACK_size(ap); + W_ old_info; + (old_info) = prim %cmpxchgW(ap, stg_AP_STACK_info, stg_WHITEHOLE_info); + if (old_info != stg_AP_STACK_info) { + /* someone else beat us to it */ + jump ENTRY_LBL(stg_WHITEHOLE) (ap); + } + StgInd_indirectee(ap) = CurrentTSO; + W_[ap] = stg_EAGER_BLACKHOLE_info; + /* * Check for stack overflow. IMPORTANT: use a _ENTER check here, * because if the check fails, we might end up blackholing this very }}} However, in doing this I'm seeing `<<loops>>` in the testcase. I haven't yet worked out why. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:45> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Indeed disabling the duplicate-work-suspension logic in `threadPaused` prevents the issue from manifesting. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:46> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"1e471265c1ea9b2c4e9709adc182c36d0635f071/ghc" 1e47126/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="1e471265c1ea9b2c4e9709adc182c36d0635f071" rts: Clarify whitehole logic in threadPaused Previously we would look at the indirectee field of a WHITEHOLE object. However, WHITEHOLE isn't a sort of indirection and therefore has no indirectee field. I encountered this while investigating #13615, although it doesn't fix that bug. Test Plan: Validate Reviewers: simonmar, austin, erikd Subscribers: rwbarton, thomie GHC Trac Issues: #13615 Differential Revision: https://phabricator.haskell.org/D3674 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:47> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: new Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Me: 1, Bug: 0. Details and patch coming. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:48> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: patch Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * differential: => Phab:D3695 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:49> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: patch Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"0836bfbd480b00a690937060fc98df5e26453078/ghc" 0836bfb/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="0836bfbd480b00a690937060fc98df5e26453078" testsuite: Add testcase for #13615 Reviewers: austin Subscribers: dfeuer, rwbarton, thomie GHC Trac Issues: #13615 Differential Revision: https://phabricator.haskell.org/D3696 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:50> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: patch Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"fd7a7a6363d8dde1813bc23cb4ef00ebb70a49c0/ghc" fd7a7a6/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="fd7a7a6363d8dde1813bc23cb4ef00ebb70a49c0" Eagerly blackhole AP_STACKs This fixes #13615. See the rather lengthy Note [AP_STACKs must be eagerly blackholed] for details. Reviewers: simonmar, austin, erikd, dfeuer Subscribers: duog, dfeuer, hsyl20, rwbarton, thomie GHC Trac Issues: #13615 Differential Revision: https://phabricator.haskell.org/D3695 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:51> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => closed * resolution: => fixed Comment: Merged to `ghc-8.2` with d94aebd369a78ae55ab2c078da79e4dc11fa9657 and c1c0985416a6f9766c03d361449f556905bf8e1d. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:52> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"c940e3b92f4527ca59fcae93f36c869de3e7ccb9/ghc" c940e3b/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="c940e3b92f4527ca59fcae93f36c869de3e7ccb9" dmdAnal: Ensure that ExnStr flag isn't dropped inappropriately This fixes #13977 and consequently #13615. Here an optimization in the demand analyser was too liberal, causing us to drop the ExnStr flag and consequently resulting in incorrect demand signatures. This manifested as a segmentation fault in #13615 as we incorrectly concluded that an application of catchRetry# would bottom. Specifically, we had orElse' :: STM a -> STM a -> STM a orElse' x = catchRetry# x y where y = {- some action -} Where the catchRetry# primop places a demand of <xC(S),1*C1(U)> on its first argument. However, due to #13977 the demand analyser would assign a demand of <C(S),1*C1(U)> on the first argument of orElse'. Note the missing `x`. case orElse' bottomingAction anotherAction of { x -> Just x } being transformed to, case orElse' bottomingAction anotherAction of {} by the simplifier. This would naturally blow up when orElse' returned at runtime, causing the segmentation fault described in #13615. Test Plan: Validate, perhaps add a testcase Reviewers: austin, simonpj Reviewed By: simonpj Subscribers: rwbarton, thomie GHC Trac Issues: #13977, #13615 Differential Revision: https://phabricator.haskell.org/D3756 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:53> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Comment:53 was actualling intended to refer to #13916. Too many bugs with too similar numbers. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:54> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"bade356f79d44c9f6e8918a89d9ffac7f5608dbf/ghc" bade356/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="bade356f79d44c9f6e8918a89d9ffac7f5608dbf" rts: Claim AP_STACK before adjusting Sp In the fix to #13615 we introduced some logic to atomically blackhole AP_STACKs closures upon entry. However, this logic was placed *after* a stack pointer adjustment. This meant that if someone else beat us to blackholing the AP_STACK we would suspend the thread with uninitialized content on the stack. This would then later blow up when threadPaused attempted to walk the stack, hence #13970. Silly bug but still cost lots of head-scratching to find. Thanks to albertov for the great repro. Fixes #13970. Bug originally introduced by the fix to #13615. Reviewers: austin, erikd, simonmar Reviewed By: erikd, simonmar Subscribers: rwbarton, thomie GHC Trac Issues: #13970, #13615 Differential Revision: https://phabricator.haskell.org/D3760 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:55> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): bgamari, how hard do you think it would be to merge this to 8.0? 7.10? 7.8? Apparently there are still a few people using 7.6, but they should really give it up. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:56> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators -------------------------------------+------------------------------------- Reporter: pacak | Owner: bgamari Type: bug | Status: closed Priority: highest | Milestone: 8.2.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | 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): Phab:D3695 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Merging likely wouldn't be terribly difficult. Building and releasing bindists, on the other hand, would require several days of effort. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13615#comment:57> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC