Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,333
    • Issues 4,333
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 370
    • Merge Requests 370
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #13615

Closed
Open
Opened Apr 25, 2017 by pacak@trac-pacak

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
Assignee
Assign to
8.2.1
Milestone
8.2.1 (Past due)
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#13615