[GHC] #14461: Reuse free variable lists through nested closures
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: 7258 Differential Rev(s): | Wiki Page: NestedClosures -------------------------------------+------------------------------------- Consider [wiki:NestedClosures] and [ticket:7258]; essentially, deeply nested closures exhibit quadratic compiler performance due to the fact that when allocating registers, each nesting level will have the compiler unpack the entire parent closure and then re-pack the variables into the child closure. To solve this, check if the parent closure can be carried along wholesale, and pull variables from there so that the repackaging can be bypassed. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by tdammers): Work on this is already being done: https://github.com/alexbiehl/ghc/commit/a5e845eeaac932a9e43a3c2587df1abbd10b... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by tdammers): * owner: (none) => alexbiehl -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): Transforming the free variables in the codegen (as done in the mentioned patch) remains hairy. I have another plan: I will introduce a new `data GenStgFreeVar occ = StgFreeVar occ [occ]` type and calculate the sharing in CoreToStg as we have all the relevant data available and in good shape anyway. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by simonpj):
I have another plan: I will introduce a new data GenStgFreeVar occ = StgFreeVar occ [occ] type and calculate the sharing in CoreToStg as we have all the relevant data available and in good shape anyway.
I think that's a great plan: see [wiki:NestedClosures] under "Implementation". If you could describe the moving parts of your plan in the wiki page, it'd help us to offer you support and feedback. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): Replying to [comment:4 simonpj]:
I think that's a great plan: see [wiki:NestedClosures] under "Implementation".
Ups, I didn't see that! I have another thing, somewhat related: If we find something like {{{ case e of x { T a b c -> let [a b c] f = \[] -> } }}} Why not make it {{{ case e of x { -- evaluate e to not change strictness T _ _ _ -> let [x] f = \[] -> case x of T a b c -> ... } }}} This could even be done at Core level I suppose. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by simonpj): Yes you could do that in Core, but the simplifier would immediately undo it by eliminating the inner case. However, in our proposed STG-level transformation, I think we could indeed transform {{{ case e of x { T a b c -> let [a b c] f = \[] -> ... } }}} to {{{ case e of x { T _ _ _ -> let [x{a,b,c}] f = \[] -> ... } }}} using the notation on the wiki page. I'm beginning to think that it might be easier to do this free-var-finding stuff as a STG-to-STG pass with a single purpose, rather than as part of Core-to-STG. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
I'm beginning to think that it might be easier to do this free-var- finding stuff as a STG-to-STG pass with a single purpose, rather than as
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): Replying to [comment:6 simonpj]: part of Core-to-STG. Seems reasonable. I will take that in consideration. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): I have hit a problem. Using ticket #7258 as a base line I figured that most of the closures we generate during `Read`/`Show` deriving are updatable thunks: {{{ let [fv1 fv2 ... fvn] outer = \u [] -- 'u' for updatable let [fv1 fv2 ... fvn] inner = \u [] ... }}} Applying the NestedClosure idea gets us: {{{ let [fv1 fv2 ... fvn] outer = \u [] let [outer{fv1 fv2 ... fvn}] inner = \u [] ... }}} Now, when forcing `outer` we push an update frame which overwrites `outer`s closure to be an indirection to the resulting value hereby turning the free variables effectively into garbage. We now have no safe way to access `outer`s free variables from `inner`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): Ok, compiling with optimizations somewhat reduces the amount of updatable thunks. Possibly because of demand analysis. We must be careful to not share updatable thunks. I have to measure the impact but I suspect this will greatly reduce the effect of this transformation and we should think about a different scheme. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by simonpj):
Now, when forcing `outer` we push an update frame which overwrites `outer`s closure to be an indirection to the resulting value hereby turning the free variables effectively into garbage.
Ah! That's an excellent point, one that I had totally neglected. Possibilities: * Step 1. Don't do this for thunks. We have no data about what the troublesome cases are, but the one case we do know about has functions. * Step 2. Still don't do the this for thunks, but {{{ let k1 = [fv1, ..., fvn] \ [] let k2 = [fv1, ..., fvn] \ [] -> ... in ... in ... ===> let t = (fv1, ..., fvn) in let k1 = [t{fv1, ..., fvn}] \ [] -> let k2 = [t{fv1, ..., fvn}]] \ [] -> ... in ... in ... }}} NB: here I am allowing the `t{fv1,..,fvn}` as a way to access the free vars of a data constructor, as well as a function closure. I don't think this should be hard to arrange. And it might be useful anyway. Now the shared bit is a separate tuple, which won't get updated. One thing that would help would be some '''data''' on how common this kind of thing is. Even deciding what to measure is non-obvious. For example: * For each STG let-binding {{{ let x = [fv1..fvn] \ argsx -> ex }}} How often is it the case that there is an enclosing binding {{{ let y = [gv1,...gvm] \ argsy -> ey }}} where the `[gv1,..gvm]` is a subset of `[fv1,..fvn]`? And what is the distribution of savings? By "enclosing" here, in the RHS of a let, I include the let-binding itself, ''even if it is non-recursive''. All the examples above have this form. Some data along these lines would be extremely helpful in guiding what we do. Another variant: currently we insist that `[gv1,..gvm]` is a '''subset''' of `[fv1,..fvn]`, to avoid space leaks. But with some RTS support we could do better: the closure for `x` could point to the closure for `y`, but ''also'' have a bitmap (in `x`'s info table) to say which of `y`'s free vars are actually used by `x`. That would open up the possibility for much more flexible sharing, at the cost of more bitmaps etc. E.g. {{{ x = [fv1,...fv100] \ [a] -> let y = [fv1,...fv99, a] \ [] -> ... in ... }}} Here `y` needs all but one of `x`'s free vars. Data on how often this happens would be would be jolly useful. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by alexbiehl): I hacked up a POC of this transformation (it excludes updatable thunks from consideration). I had a quick (non-scientific) glance over the amount of CMM code generated for W2.hs (example from #7258): {{{ vanilla ghc ~380000 LOC hacked ghc ~270000 LOC }}} I noticed a lots of small, nested closures which only needed a fraction of the free variables of their outer closures and hence didn't benefit from the transformation.
Some data along these lines would be extremely helpful in guiding what we do. I will instrument my GHC to collect some data to guide us from here.
Another variant: currently we insist that `[gv1,..gvm]` is a '''subset''' of `[fv1,..fvn]`, to avoid space leaks. But with some RTS support we could do better: the closure for `x` could point to the closure for `y`, but ''also'' have a bitmap (in `x`'s info table) to say which of `y`'s free vars are actually used by `x`. That would open up the possibility for much more flexible sharing, at the cost of more bitmaps etc. E.g. {{{ x = [fv1,...fv100] \ [a] -> let y = [fv1,...fv99, a] \ [] -> ... in ... }}}
Sound reasonable. Let's see what the data shows.. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by dfeuer): As discussed today, the plan in comment:10 seems to offer the ability to deal also with the case where several, but not all, of the free variables are reused. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by simonmar): * cc: simonmar (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by bgamari): * failure: None/Unknown => Runtime performance bug -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Comment (by simonpj): @alexbiehl your POC in comment:11 looks so promising that it seems a shame to let this lie. Do you (or anyone else) have time to carry it through? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by simonpj): * cc: dfeuer (removed) * cc: dfeuer., andreask (added) Comment: AndreasK: maybe you'd be interested. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by potato44): * cc: dfeuer. (removed) * cc: dfeuer (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CodeGen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14461: Reuse free variable lists through nested closures -------------------------------------+------------------------------------- Reporter: tdammers | Owner: alexbiehl Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 7258 | Differential Rev(s): Wiki Page: NestedClosures | -------------------------------------+------------------------------------- Changes (by sgraf): * cc: sgraf (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14461#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC