[GHC] #11372: Loopification does not trigger for IO even if it could
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, | Operating System: Unknown/Multiple loopification, code generation | Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- The loopification optimization, as I understand it, allows a self- recursive function to jump to a local label instead of the beginning of the function, thus skipping a potential stack check. However, I only observe it triggering for pure functions while IO functions do not get that benefit, even when it would be possible. I discovered this in #8793 after looking into an unexpected speedup by removing the IO context from an otherwise pure loop and while such a loop can simply be changed to a pure version (the {{{IOLoop}}} examples), other functions can not, but the optimization could be applied to them (see {{{MapM.hs}}}). I tried to benchmark the differences between a naive loop in IO and some horrible {{{inlinePerformIO}}} hacks to get the loopification to fire and the "optimized" version performs 3-5% faster on my machine. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by jscholl): * Attachment "MapM.hs" added. mapM_ implementation as example of a loop which would benefit from the optimization, but currently doesn't. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by jscholl): * Attachment "IOLoop.hs" added. Loop which can be made pure by the user -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by simonpj: Old description:
The loopification optimization, as I understand it, allows a self- recursive function to jump to a local label instead of the beginning of the function, thus skipping a potential stack check. However, I only observe it triggering for pure functions while IO functions do not get that benefit, even when it would be possible.
I discovered this in #8793 after looking into an unexpected speedup by removing the IO context from an otherwise pure loop and while such a loop can simply be changed to a pure version (the {{{IOLoop}}} examples), other functions can not, but the optimization could be applied to them (see {{{MapM.hs}}}).
I tried to benchmark the differences between a naive loop in IO and some horrible {{{inlinePerformIO}}} hacks to get the loopification to fire and the "optimized" version performs 3-5% faster on my machine.
New description: The loopification optimization, as I understand it, allows a self- recursive function to jump to a local label instead of the beginning of the function, thus skipping a potential stack check. However, I only observe it triggering for pure functions while IO functions do not get that benefit, even when it would be possible. I discovered this in #8793 after looking into an unexpected speedup by removing the IO context from an otherwise pure loop and while such a loop can simply be changed to a pure version (the {{{IOLoop}}} examples), other functions can not, but the optimization could be applied to them (see {{{MapM.hs}}}). I tried to benchmark the differences between a naive loop in IO and some horrible {{{inlinePerformIO}}} hacks to get the loopification to fire and the "optimized" version performs 3-5% faster on my machine. See [wiki:Commentary/Compiler/Loopification] for details -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by jscholl): * status: new => patch * differential: => Phab:D1767 Comment: The problem with loopification for loops in {{{IO}}} / any monad of the form {{{State# s -> (# State s, a #)}}} is indeed caused by the extra {{{State#}}} tokens. While they have no runtime representation and thus are not passed to a self-recursive call, they are still counted as arguments when considering a self-recursive call for loopification. So I tried to fix this by adding an additional parameter to {{{getCallMethod}}}, namely the number of void arguments, and subtract that number before checking if the correct number of arguments is present (I could not just remove void arguments from the arguments as the number of arguments is used in other places as well and I think there these void arguments have to generate {{{stg_ap_v}}} calls or something similar). I also tried to add a note describing the situation with these void arguments and loopification. I also did a nofib-run. Most things changed only a little bit, but most of the code seems to run a little bit faster, though in praxis it is even less than in my benchmark, but this is not suprising as most code does not (only) consist of such loops in IO. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by jscholl): * Attachment "nofib-results" added. nofib run comparing current ghc-8.0 branch and my changes applied to it -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could
-------------------------------------+-------------------------------------
Reporter: jscholl | Owner:
Type: bug | Status: patch
Priority: normal | Milestone:
Component: Compiler | Version: 7.10.3
(CodeGen) | Keywords: cmm,
Resolution: | loopification, code generation
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s): Phab:D1767
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: merge Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => merge -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: => 8.0.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Merged to `ghc-8.0` as 4b4d4c34cb10ba34fa25e90bdd3b381440f9c43d. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: fixed | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: merge => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: fixed | loopification, code generation Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Comment (by thomie): [https://perf.haskell.org/ghc/#revision/4d51bfc8975f9c6c3ab6d293c48f98da85210... GHC Speed] results are in: {{{ nofib/time/fannkuch-redux 3.153 - 11.45% 2.792 seconds nofib/time/n-body 0.886 - 3.61% 0.854 seconds }}} Nice! Also interesting is the stabilization of the n-body performance in this [https://perf.haskell.org/ghc/#graph/nofib/time/n-body;hl=4d51bfc8975f9c6c3ab... graph]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11372: Loopification does not trigger for IO even if it could -------------------------------------+------------------------------------- Reporter: jscholl | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 (CodeGen) | Keywords: cmm, Resolution: fixed | loopification, code generation, | CodeGen Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1767 Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: cmm, loopification, code generation => cmm, loopification, code generation, CodeGen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11372#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC