#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): Reid, indeed it is known: #5916. (If you find any other tickets about this, please add them.) I think the best approach would be as in comment:16 of ticket:5916#comment:16 * '''Inline `runS` very late, in `CorePrep`''' Some thoughts about this. * We'd want a single, magical function which has this behaviour. Things like `unsafeDupablePerformIO` should call `runS`. * Now I think about it, I wonder if the magical function should instead be this: {{{ runRW# :: (State# s -> (# State s, a)) -> (# State s, a #) {-# NOINLINE runRW# #-} runRW# f = f realWorld# }}} That is, all `runRW#` does is to apply its argument to a fresh state token. Now we can define your `runS` thus: {{{ runS f = case ruNRW# f of (# _, r #) -> r }}} I think we can inline `runS` freely, which is good because it means that more code is exposed to the optimiser (in particular that `case`). * Moreover, if we do this, I think we now don't need `lazy`. Because `runRW#`'s strictness signature won't be strict in the `r` part; see `Note [unsafeDupablePerformIO has a lazy RHS]` in `GHC.IO`. * If `CorePrep` saw `runRW# (f a b)` it can generate `f a b realWorld#`. But if it sees `runRW# (\s.e)`, it should generate `e[realWorld#/s]`. That is, it should do the beta-reduction on the fly. That's slightly annoying because `CorePrep` doesn't currently carry around a substitution. But I suppose that you could literally call `substExpr`; this doesn't happen much. * Alternatively maybe this could be done in the code generator, effectively treating `runRW` as a primop. That would be a good plan, except that by the time we get to STG the program is in ANF, so instead of `runRW# (f a b)` we'd have {{{ let g = f a b in ruNRW# g }}} and before we see the `runRW#` we'll have generated code to allocate a closure for `g`. So we'd need to allow STG syntax (for specified primops) to have expressions, not just atoms, as the arguments to the primop. This might actually be a Jolly Good Thing. At the moment `catch# (\s -> e1) (\x s -> e2)` allocates two closures before it gets to the `catch#`, which is pretty stupid since the first thing we do after pushing the exception-catch frame is to execute `e1`. I think changes like this would make modest but significant improvements to many programs. If you'd like to dig into it, I'd gladly help. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): Great! Thank you. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by rwbarton): * Attachment "runRW-nofib.txt" added. nofib results -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): Good! Can you give a small example of your last para? I bet it's something like {{{ case (runRW (\s -> I# x)) of (# _ , I# y) -> blah }}} I bet that you can make something similar happen with `catch#`. A new ticket, perhaps. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by rwbarton): Replying to [comment:7 simonpj]:

Good! Can you give a small example of your last para? I bet it's something like {{{ case (runRW (\s -> I# x)) of (# _ , I# y) -> blah }}}

Right, so in integer-gmp, where I previously had {{{ runS :: S RealWorld a -> a -- type S s a = State# s -> (# State# s, a #) runS m = case runRW# m of (# _, a #) -> a }}} when `a = BigNat` (`data BigNat = BN# ByteArray#`), I can instead use {{{ runS_BigNat :: S RealWorld BigNat -> BigNat runS_BigNat m = case runRW# (\s -> case m s of (# s', BN# ba #) -> (# s', ba #)) of (# _, ba #) -> BN# ba }}} The idea is * `m` usually simplifies to something like {{{ \s0 -> case newByteArray# n s0 of (# s1, arr #) -> case someGmpFunction arr s1 of s2 -> case unsafeFreezeByteArray# arr s2 of (# s3, farr #) -> (# s3, BN# farr #) }}} so in the "inner case" in `runS_BigNat`, the constructor `BN#` will cancel * Now the caller of `runS_BigNat` (say, `plusBigNat`) has the CPR property because the `BN#` constructor is visible outside the `runRW#` * Its caller in turn (say, `plusInteger`) looks like {{{ plusInteger (Jp# x) (Jp# y) = Jp# (plusBigNat x y) }}} but `Jp#`'s argument is unboxed for size reasons {{{ data Integer = ... | Jp# {-# UNPACK #-} !BigNat | ... }}} so `Jp# (plusBigNat x y)` would have meant extracting the field from a `BN#` and repacking it into a `Jp#`. But by calling the unboxed worker we can avoid ever allocating an intermediate `BN#` constructor. Note that the transformation `runS -> runS_BigNat` is always valid for any `m`, even though it looks like a nested CPR situation. The reason is that the context of the `runRW#` is strict in the second argument anyways. To determine when the transformation is a good idea for a particular argument `m`, we can use regular CPR analysis on the function `\s -> case m s of (# _, r #) -> r`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): Anyway let's land `runRW`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1103 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * differential: => Phab:D1103 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1103 Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonmar): * cc: simonmar (added) Old description:

integer-gmp uses an unsafePerformIO-like operation to work with mutable BigNats (unsafePerformIO and even the IO type are not yet available, since integer-gmp is a dependency of base): {{{#!hs type S s a = State# s -> (# State# s, a #)

-- NB: equivalent of GHC.IO.unsafeDupablePerformIO, see notes there runS :: S RealWorld a -> a runS m = lazy (case m realWorld# of (# _, r #) -> r) {-# NOINLINE runS #-} }}} It's tempting to think of such an operation as "free" like an unsafeCoerce, but it is actually somewhat expensive.

Consider `plusBigNat` for instance. (Most BigNat operations have a similar structure.) {{{#!hs plusBigNat :: BigNat -> BigNat -> BigNat plusBigNat x y | isTrue# (eqBigNatWord# x 0##) = y | isTrue# (eqBigNatWord# y 0##) = x | isTrue# (nx# >=# ny#) = go x nx# y ny# | True = go y ny# x nx# where go (BN# a#) na# (BN# b#) nb# = runS $ do mbn@(MBN# mba#) <- newBigNat# na# (W# c#) <- liftIO (c_mpn_add mba# a# na# b# nb#) case c# of 0## -> unsafeFreezeBigNat# mbn _ -> unsafeSnocFreezeBigNat# mbn c#

nx# = sizeofBigNat# x ny# = sizeofBigNat# y }}} The assembly for `go` begins {{{ 00000000000001d0 : 1d0: 49 83 c4 28 add $0x28,%r12 1d4: 4d 3b a5 58 03 00 00 cmp 0x358(%r13),%r12 1db: 77 26 ja 203 1dd: 49 c7 44 24 e0 00 00 movq $0x0,-0x20(%r12) 1e4: 00 00 1e2: R_X86_64_32S .text+0x38 1e6: 4d 89 74 24 e8 mov %r14,-0x18(%r12) 1eb: 49 89 7c 24 f0 mov %rdi,-0x10(%r12) 1f0: 49 89 74 24 f8 mov %rsi,-0x8(%r12) 1f5: 4d 89 04 24 mov %r8,(%r12) 1f9: 4d 8d 74 24 e1 lea -0x1f(%r12),%r14 1fe: e9 00 00 00 00 jmpq 203 1ff: R_X86_64_PC32 integerzmgmp_GHCziIntegerziType_runS_info-0x4 203: ... ; heap overflow }}} This allocates a 5-word closure (containing `a#`, `na#`, `b#`, `nb#`) whose code is at `.text+0x38` and passes it to `runS`, which does some `stg_ap`-y things to call back into the closure, which reads its free variables back from the heap and finally does all the real work. Altogether it's around two dozen instructions compared to if we could call directly from `go` to the argument of `runS`.

The old integer-gmp somehow avoided this particular overhead by instead using the implicit "unsafePerformIO" of a foreign import prim which performed both the allocation and the addition. Is this overhead a necessary consequence of doing the work in multiple steps in Haskell?

I understand that we cannot allow everything to be inlined and, for example, the `newBigNat#` to be shared between a `plusBigNat` and `minusBigNat` with the same arguments. But once `runS` has done its job of keeping the `newBigNat#/c_mpn_add/unsafeFreeze*` together, it would be nice to eliminate it completely in the backend when compiling `go`, or any inlined version of `go`.

I'm not sure whether this should be fixed in the code generator or in integer-gmp itself. I'm also aware that this is a tricky subject but haven't really done my homework on the related tickets, so I might be missing something important!

New description: integer-gmp uses an unsafePerformIO-like operation to work with mutable BigNats (unsafePerformIO and even the IO type are not yet available, since integer-gmp is a dependency of base): {{{#!hs type S s a = State# s -> (# State# s, a #) -- NB: equivalent of GHC.IO.unsafeDupablePerformIO, see notes there runS :: S RealWorld a -> a runS m = lazy (case m realWorld# of (# _, r #) -> r) {-# NOINLINE runS #-} }}} It's tempting to think of such an operation as "free" like an unsafeCoerce, but it is actually somewhat expensive. Consider `plusBigNat` for instance. (Most BigNat operations have a similar structure.) {{{#!hs plusBigNat :: BigNat -> BigNat -> BigNat plusBigNat x y | isTrue# (eqBigNatWord# x 0##) = y | isTrue# (eqBigNatWord# y 0##) = x | isTrue# (nx# >=# ny#) = go x nx# y ny# | True = go y ny# x nx# where go (BN# a#) na# (BN# b#) nb# = runS $ do mbn@(MBN# mba#) <- newBigNat# na# (W# c#) <- liftIO (c_mpn_add mba# a# na# b# nb#) case c# of 0## -> unsafeFreezeBigNat# mbn _ -> unsafeSnocFreezeBigNat# mbn c# nx# = sizeofBigNat# x ny# = sizeofBigNat# y }}} The assembly for `go` begins {{{ 00000000000001d0 : 1d0: 49 83 c4 28 add $0x28,%r12 1d4: 4d 3b a5 58 03 00 00 cmp 0x358(%r13),%r12 1db: 77 26 ja 203 1dd: 49 c7 44 24 e0 00 00 movq $0x0,-0x20(%r12) 1e4: 00 00 1e2: R_X86_64_32S .text+0x38 1e6: 4d 89 74 24 e8 mov %r14,-0x18(%r12) 1eb: 49 89 7c 24 f0 mov %rdi,-0x10(%r12) 1f0: 49 89 74 24 f8 mov %rsi,-0x8(%r12) 1f5: 4d 89 04 24 mov %r8,(%r12) 1f9: 4d 8d 74 24 e1 lea -0x1f(%r12),%r14 1fe: e9 00 00 00 00 jmpq 203 1ff: R_X86_64_PC32 integerzmgmp_GHCziIntegerziType_runS_info-0x4 203: ... ; heap overflow }}} This allocates a 5-word closure (containing `a#`, `na#`, `b#`, `nb#`) whose code is at `.text+0x38` and passes it to `runS`, which does some `stg_ap`-y things to call back into the closure, which reads its free variables back from the heap and finally does all the real work. Altogether it's around two dozen instructions compared to if we could call directly from `go` to the argument of `runS`. The old integer-gmp somehow avoided this particular overhead by instead using the implicit "unsafePerformIO" of a foreign import prim which performed both the allocation and the addition. Is this overhead a necessary consequence of doing the work in multiple steps in Haskell? I understand that we cannot allow everything to be inlined and, for example, the `newBigNat#` to be shared between a `plusBigNat` and `minusBigNat` with the same arguments. But once `runS` has done its job of keeping the `newBigNat#/c_mpn_add/unsafeFreeze*` together, it would be nice to eliminate it completely in the backend when compiling `go`, or any inlined version of `go`. I'm not sure whether this should be fixed in the code generator or in integer-gmp itself. I'm also aware that this is a tricky subject but haven't really done my homework on the related tickets, so I might be missing something important! -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1103 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"351de169e14ad9277aaca653df4a3753c151f7bb/ghc" 351de169/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="351de169e14ad9277aaca653df4a3753c151f7bb" New magic function for applying realWorld# Test Plan: validate Reviewers: goldfire, erikd, rwbarton, simonpj, austin, simonmar, hvr Reviewed By: simonpj Subscribers: simonmar, thomie Differential Revision: https://phabricator.haskell.org/D1103 GHC Trac Issues: #10678 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10678: integer-gmp's runS seems unnecessarily expensive -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.1 (CodeGen) | Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1103 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): https://perf.haskell.org/ghc/#revision/351de169e14ad9277aaca653df4a3753c151f... looks great, good job! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10678#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler