Re: [GHC] #13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators
GHC
ghc-devs at haskell.org
Wed Jun 7 15:30:36 UTC 2017
#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 <rxSU_info+72> (symbol and line for
./Data/HashMap/Strict.hs, line 93)
+ field 0: Ptr 0x434298 <rxSU_info+72>
+ field 1: Word 283476377554
+1: RET_SMALL
return = 0x439338 <sy5n_info+272> (symbol and line for
./Data/HashMap/Strict.hs, line 166)
field 0: Ptr 0x439338 <sy5n_info+272>
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
<unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216>
(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 <snqC_info+88> (symbol and line for
./Data/HashMap/Base.hs, line 122)
field 0: Ptr 0x44c790 <snqC_info+88>
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 <base_GHCziBase_map_info+192> (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 <s4Vv_info+56> (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 <sr4u_info+232> (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 <s5BF_info+168> (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 <sy5n_info+160> (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
<unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216>
(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 <snqC_info+88> (symbol and line for
./Data/HashMap/Base.hs, line 122)
field 0: Ptr 0x44c790 <snqC_info+88>
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 <base_GHCziBase_map_info+192> (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 <s4Vv_info+56> (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 <sr4u_info+232> (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 <s5BF_info+208> (symbol and line for
libraries/base/GHC/Base.hs, line 859)
field 0: Ptr 0x471d38 <s5BF_info+208>
- 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 <sy5n_info+160> (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
<unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216>
(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 <snqC_info+88> (symbol and line for
./Data/HashMap/Base.hs, line 122)
field 0: Ptr 0x44c790 <snqC_info+88>
- 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 <base_GHCziBase_map_info+192> (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 <s4Vv_info+56> (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 <sr4u_info+232> (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 <s5BF_info+208> (symbol and line for
libraries/base/GHC/Base.hs, line 859)
field 0: Ptr 0x471d38 <s5BF_info+208>
- 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 <sy5n_info+160> (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
<unorderedzmcontainerszm0zi2zi8zi0zminplace_DataziHashMapziStrict_zdwfromListWith_info+216>
(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
More information about the ghc-tickets
mailing list