[GHC] #13861: Take more advantage of STG representation invariance (follows up #9291)
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Consider following `case` alternatives at the STG stage (i.e. untyped) : {{{#!hs case scrut of False -> [] Just x -> Right x [] -> Nothing }}} The common theme of all these is that the scrutinee's memory layout and the result's memory layout coincide. So operationally no allocation needs to take place, and the whole `case` expression is simply a (strict) identity at the STG stage. I propose to add a small STG analysis to: * for each `case` alternative check whether the assigned tag between scrutinee and result matches, and if so * check whether both have the underlying memory layout and contents. If these conditions are met, the case alternative can be replaced with the identity. When all alternatives simplify to the identity (also considering the DEFAULT alternative), then the entire `case` expression reduces to a single identity DEFAULT alternative (i.e. all other alternatives in the `case` can be dropped). Many of the code examples in the join points paper (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/join- points-pldi17.pdf) exhibit these optimisation opportunities. The already implemented suggestion in #9291 comes with the restriction that it only operates in the scope of the same type (see last comment there), but STG is untyped, so why not take advantage of this fact? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Things to think about * It's not just memory layout. To substitute one data constructor for another, they must have the same ''tag''; and may even need to belong to a data type with the same number of data constructors. Eg {{{ case x of Nothing -> True }}} `Nothing` has tag zero, and `True` has tag 1. * Runtime debugging or heap analysis may display the data constructor. Substituting a data constructor from another type would break this utterly. I'd need a bit of convincing that the benefit (in performance) justified the cost; and that the opportunities to exploit this happen often enough to use worth doing. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:1 simonpj]:
Things to think about
* It's not just memory layout. To substitute one data constructor for another, they must have the same ''tag''; and may even need to belong to a data type with the same number of data constructors. Eg
{{{ case x of Nothing -> True }}} `Nothing` has tag zero, and `True` has tag 1.
* Runtime debugging or heap analysis may display the data constructor. Substituting a data constructor from another type would break this utterly.
I'd need a bit of convincing that the benefit (in performance) justified
Oh, yes I consider tags in my proposal. See my first bullet point. I doubt that the number of constructors must match, though. Maybe with nomeata's help I can come up with a proof-of-concept at some hackathon, so that we can get a feeling whether this optimisation kicks in often enough to become interesting. the cost; and that the opportunities to exploit this happen often enough to use worth doing. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by maoe): * cc: maoe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * cc: nomeata (added) Comment: This could presumably easily be added to the STG CSE pass (#9291). Or at least that is roughly the right spot. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): When implemented, one could test: `\case Right a → Just a` should be `seq b (unsafeCoerce b)`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Brain dump of conversation with SPJ at Haskell eXchange, London. Currently pointer tagging only effective for "small constructor families". If not small, the tag is 1 on pointers to evaluated constructors. See `isSmallFamily` in `compiler/codeGen/StgCmmClosure.hs`. Of course this penalizes big families. I suggest to set tags 1..6 for non-small families' lower constructors, 7 for all other (overflowing) constructors. This would allow more precise branching for big families too (in a significant number of cases), as the ''former'' constructors are usually the more common ones (keeping fingers crossed). Also the coercion between small and big families would be straightforward, with following ranges directly castable: || || |||| from || || || ||= small =||= big =|| ||= to =||= small =|| 1..7 || 1..6 || || ||= big =|| 1..7 || 1..7 || Conservatively in the beginning one could only allow 1..6. Note: `(-1 :: Int) .&. 7 == 7` so that would lead to all-ones too. It is not immediately clear how to find out whether the constructor is n a big family. We could add the family size as an additional piece of information. A (future) wiki page should explain the new conventions. Many references to pinter tagging in the code should be updated. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): It would be nice to know what the motivation for *not* using the available tag space for big families is. Surely there was a reason, even if it was just keeping implementation complexity at bay. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): If the paper doesn't say and there are no comments to explain, the last port of call would be Simon Marlow. Otherwise I'd assume it was just becuase it seemed like the easiest thing, and most data types are smaller. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:7 bgamari]:
It would be nice to know what the motivation for *not* using the available tag space for big families is. Surely there was a reason, even if it was just keeping implementation complexity at bay.
Probably the motivation was "we'll think about this later". Implementation complexity seems to be fairly low, see my branch (caveat: ''very WIP'') https://github.com/ggreif/ghc/tree/wip/tag-big-families -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:9 heisenbug]:
Probably the motivation was "we'll think about this later".
Implementation complexity seems to be fairly low, see my branch (caveat: ''very WIP'') https://github.com/ggreif/ghc/tree/wip/tag-big-families The last checkin does bootstrap GHC and seems to do well not he test side. Code still is not as pretty as I want it, but I shall clean it up in the next days. Can somebody do a perf evaluation with it? Thanks! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by heisenbug): * owner: (none) => heisenbug -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Now that #14373 is up for review, it is time to revisit this one. It turns out that coercion between small and big families is not an issue any more (provided that wip/T14373 gets merged). From big family with ptr-tag 7 we anyway only can go to small family ptr-tag 7 if the tags in the info table match, so everything is okay. My conservative 1..6 assessment above is not needed. We can safely have 1..7. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): https://github.com/ggreif/ghc/tree/wip/T13861 is the branch that builds on https://github.com/ggreif/ghc/tree/wip/T14373. I wonder what https://perf.haskell.org will say... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CodeGen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13861: Take more advantage of STG representation invariance (follows up #9291) -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: heisenbug Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.2 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by osa1): * cc: osa1 (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13861#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC