[GHC] #13615: Wrong results from what supposed to be pure function with presense of parallel evaluation

GHC

25 Apr 25 Apr

8:26 p.m.

#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

Reply

Sign in to reply online Use email software

GHC

8:50 p.m.

#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

Reply

Sign in to reply online Use email software

GHC

10:40 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

26 Apr 26 Apr

12:04 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

9:24 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

12:44 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

3:31 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

8:15 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

9:15 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

9:38 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

10:20 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

10:51 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

8:56 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

28 Apr 28 Apr

2:18 p.m.

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

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

Reply

Sign in to reply online Use email software

GHC

2 May 2 May

10:15 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

16 May 16 May

10:58 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

7 Jun 7 Jun

11:30 a.m.

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

#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 (symbol and line for ./Data/HashMap/Strict.hs, line 93) + field 0: Ptr 0x434298 + field 1: Word 283476377554 +1: RET_SMALL return = 0x439338 (symbol and line for ./Data/HashMap/Strict.hs, line 166) field 0: Ptr 0x439338 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 (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 (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 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 (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 (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 (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 (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 (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 (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 (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 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 (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 (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 (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 (symbol and line for libraries/base/GHC/Base.hs, line 859) field 0: Ptr 0x471d38 - 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 (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 (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 (symbol and line for ./Data/HashMap/Base.hs, line 122) field 0: Ptr 0x44c790 - 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 (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 (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 (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 (symbol and line for libraries/base/GHC/Base.hs, line 859) field 0: Ptr 0x471d38 - 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 (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 (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

Reply

Sign in to reply online Use email software

GHC

12:33 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

9 Jun 9 Jun

3:59 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

14 Jun 14 Jun

2:11 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

15 Jun 15 Jun

7:37 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

16 Jun 16 Jun

9:37 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

24 Jun 24 Jun

8:45 p.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

27 Jun 27 Jun

1:34 p.m.

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

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

Reply

Sign in to reply online Use email software

GHC

2:24 a.m.

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

#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

Reply

Sign in to reply online Use email software

GHC

7:42 p.m.

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

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

Reply

Sign in to reply online Use email software

GHC

19 Jul 19 Jul

7:29 p.m.

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

#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 ): 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 on its first argument. However, due to #13977 the demand analyser would assign a demand of 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

Reply

Sign in to reply online Use email software

GHC

20 Jul 20 Jul

12:04 p.m.

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

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

Reply

Sign in to reply online Use email software

GHC

9 Aug 9 Aug

5:26 a.m.

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

#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

Reply

Sign in to reply online Use email software

tags

participants (1)