Re: [GHC] #13615: Nondeterminism in ‘pure’ function w/ parallel evaluation & memo combinators

7 Jun 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