Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators

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 rnfing) the arguments to unsafeInsertWith doesn't help. The issue is reproducible with -O0 on HEAD but not with -O2; On

1. 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