Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Register
  • Sign in
  • GHC GHC
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
    • Locked files
  • Issues 5.5k
    • Issues 5.5k
    • List
    • Boards
    • Service Desk
    • Milestones
    • Iterations
  • Merge requests 631
    • Merge requests 631
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Artifacts
    • Schedules
    • Test cases
  • Deployments
    • Deployments
    • Releases
  • Packages and registries
    • Packages and registries
    • Model experiments
  • Analytics
    • Analytics
    • CI/CD
    • Code review
    • Insights
    • Issue
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell CompilerGlasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #13615

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

Edited Mar 10, 2019 by pacak
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking