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

[GHC]

#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