[GHC] #9374: Investigate Static Argument Transformation
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Blocked By: | None/Unknown Related Tickets: | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- At the moment the Static Argument Transformation (SAT) optimisation is not run unless explicitly enabled with `-fstatic-argument-transformation`. The comment in DynFlags says: {{{ Max writes: I think it's probably best not to enable SAT with -O2 for the 6.10 release. The version of SAT in HEAD at the moment doesn't incorporate several improvements to the heuristics, and I'm concerned that without those changes SAT will interfere with some attempts to write "high performance Haskell", as we saw in some posts on Haskell-Cafe earlier this year. In particular, the version in HEAD lacks the tail call criterion, so many things that look like reasonable loops will be turned into functions with extra (unneccesary) thunk creation. }}} 6.10 was a long time ago. Has anything changed since then? Does it make sense to enable that optimisation now? What are the mentioned heuristics and were they finally implemented? Does anyone know what Haskell-cafe posts does Max refer to? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by simonpj): * cc: nicolas.frisby@… (added) Comment: That would be great. Quick thoughts * As I recall, in [http://research.microsoft.com/en- us/um/people/simonpj/papers/santos-thesis.ps.gz Andre Santos's thesis] he got ambiguous results from SAT: some programs improved, some got worse. * Also worth reading: Danvy et al's paper about "lambda-dropping" * The places it got worse might well be fixed by Nick Frisby's work on "late lambda lifting". Sadly, this has stalled a bit because Nick has got interested in other things. I'm copying him in the hope of an update. It would be great to re-instate SAT. But it would need someone to do some careful benchmarking to make sure that it yielded a net benefit. What usually happens is that you find a couple of cases where it makes things worse, investigate, find why, and modify the transformation to avoid them. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): I found an email summarising a conversation Max and I had about SAT, back in 2009. Here it is verbatim, FWIW: SAT can lose; eg * few static args (can spot) * few loop iterations (hard to spot) * SAT changes SpecConstr opportunity into CaseLib opportunity; and the latter is not good at the moment * SATing exposes new loop-invariant sub-expressions e.g. {{{ f x y = if y==0 then 0 else g x + f x (y-1) }}} That is potentially good. But float-out can be bad for cold branches, and this can be bad. Hence want to focus on SAT in situations where it’s most likely to benefit. SAT has benefits of two kinds: 1. More efficient loops, when there are a lot of static args. This is a pretty small effect. 2. Specialisation from (a) SAT makes recursive function non-rec; (b) then inlining can happen. This is the big gain. Evidence for (2): most benefits happen even if you SAT *only* if at least one SAT-d argument has function type. Four exceptions, where SATing non-function-typed args was worthwhile: * Atom. f x y = (x,y) : f x y. Satting this makes an loopy list; result 97% reduction in runtime. * SAT may make a function small enough to fit inside inlining threshold. * Puzzle. Recursive SAT-able function called just once outside. After SAT, it can be inlined, and hence specialised for the (single) call site. One program got worse when SATing non-function-typed args * Listcompr. The cold-branch problem happens. Thoughts: * No point in SAT if function is big. Maybe SAT only if EITHER small OR single call site outside. * Max’s idea: * Lambda lift everything * !SpecConstr * Lambda-drop * Export unfoldings * Selectively lambda-lift (lambda-lift functions of only one argument) [SLPJ: this is Nick Frisby's work] * Codegen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nfrisby): Hi Simon, Jan. Thanks for including my on these recent ticket comments. I apologize for the stagnant branch. I've merged a recent master into my local copy of the late-lam-lift branch. 1) I believe I've successfully completed the merge. There was one subtle bug that I recently caught though, so I'm concerned. 2) My push to origin/late-lam-lift is being rejected due to some submodule stuff I don't grok. I need to find the correct ghc-devs email with the right conjury in it. (I have also emailed Austin and hvr asking them to move the branch to the wip/ folder so it's less restricted.) 1 and 2 are done. The rest are my current plan, including longer-term things. 3) In light of the host of changes that got merged in, I'm developing the status notes from scratch. These are destined for a web page. The meat will focus on each flag (there are several), what it does, and why. Most of the flags are for developers/power-users only. 4) I will simplify/clean-up the code itself. 5) I will add tests for when the late lambda float is enabled. (Is the test-suite configurable for this sort of predicate?) After 3--5 are complete, someone else could pick-up the work. I hesitate to estimate a timeline because I'm moving across the country in the next week. My goal is by mid-August. 6) My partial paper draft is still on a borked laptop's hard drive. Once the code and notes are in a state where someone can pick them up, I'm going to move the paper back on to my todo list, but with less immediacy. If someone beats me to the write-up, I'll happily hand over what I have. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nfrisby): There are several concepts in your quote from Max that are not familiar to me; I can't immediately predict much accurately about the late lambda float's interaction with SAT. I'd be happy to collaborate with anyone who would like to investigate. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Nick: mid August would be great! The surrounding documentation and explanation (even paper) is important. The job turned out to be trickier than I expected when you started. It took weeks to work out why a handful of programs were getting worse and to devise analysis/heuristics to avoid them. I don't want someone else to have to re-invent that knowledge, and it's very hard to reverse-engineer it from the code. Moreover, I remain hopeful that, once written down, someone may see a way to achieve the goal with less trickiness. Thanks Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by nfrisby): I merged my work with a recent master. See the `wip/llf` branch and the (growing) notes at LateLamLift. Please email me with any questions you have. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Excellent work, thank you. This ticket is about SAT, so I've started a new ticket, #9476, to track progress on late lambda lifting. Let's move further discussion about LLF to there. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): When fixing this ticket, do #9561 at the same time. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): This issue (if it's an issue) isn't with SAT, but may affect it: Sometimes `Rec` groups include things they don't (seem to) need to, so the the current SAT will see "mutual recursion" when there's only self recursion, and SAT won't be applied. Should I open a separate ticket to investigate/fix this, or is it desirable for some reason? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): I can't tell without a concrete example. Can you offer one? Thanks. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:10 simonpj]:
I can't tell without a concrete example. Can you offer one? Thanks.
Simon
Not yet. Dan Doel's work on Takano Akio's `foldrW/buildW` fusion stuff (with some help from me) shows that it often creates static arguments. It also sometimes leads to apparently-splittable `Rec` groups. I have not ''yet'' seen it create a splittable `Rec` group in which it introduces a static argument. We still don't know if this fusion framework is viable as a replacement for classic `foldr/build`, but it seems likely that giving it a really fair performance test would require a late SAT run of some kind. It may be that there won't be splittable-`Rec` issues, but I figured I'd mention that possibility. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): As I mentioned elsewhere, one situation where SAT seems always good is when the static arg is actually available in an outer scope or even statically known. I have seen things that look approximately like this after simplification: {{{#!hs fixedError = error "Bad things!" wfoo x y z = case blah of p1 -> e1 p2 -> wfoo e2 e3 z _ -> z foo x y = wfoo x y fixedError }}} It would seem in this case that instead of having a static argument in place of a closure variable, there's a static argument that just doesn't need to be there at all. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): Here's an example where SAT would be a big win. See [http://www.haskell.org/pipermail/ghc-devs/2014-September/006332.html email thread]. {{{ scanr = \ @ a_akP @ a1_akQ f_ah8 b_ah9 eta_B1 -> letrec { go_amb go_amb = \ ds_amc eta1_Xa eta2_B2 eta3_Xc -> case ds_amc of _ { [] -> eta1_Xa eta2_B2 eta3_Xc; : y_amh ys_ami -> go_amb ys_ami (\ x_an9 eta4_Xj -> let { b'_ana b'_ana = f_ah8 y_amh x_an9 } in eta1_Xa b'_ana (: b'_ana eta4_Xj)) eta2_B2 eta3_Xc }; } in go_amb eta_B1 scanr1 b_ah9 (: b_ah9 ([])) }}} The 3rd and 4th arg to `go` are static, and since there is only one call to `go`, doing SAT would yield much better code by specialising `go` for the particular parameters: {{{ scanr = \ @ a_akP @ a1_akQ f_ah8 b_ah9 eta_B1 -> let { listend listend = : b_ah9 ([])} in letrec { go_amb go_amb = \ ds_amc eta1_Xa -> case ds_amc of _ { [] -> eta1_Xa b_ah9 listend; : y_amh ys_ami -> go_amb ys_ami (\ x_an9 eta4_Xj -> let { b'_ana b'_ana = f_ah8 y_amh x_an9 } in eta1_Xa b'_ana (: b'_ana eta4_Xj)) }; } in go_amb eta_B1 scanr1 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: | Blocked By: None/Unknown | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Description changed by jstolarek: Old description:
At the moment the Static Argument Transformation (SAT) optimisation is not run unless explicitly enabled with `-fstatic-argument- transformation`. The comment in DynFlags says:
{{{ Max writes: I think it's probably best not to enable SAT with -O2 for the 6.10 release. The version of SAT in HEAD at the moment doesn't incorporate several improvements to the heuristics, and I'm concerned that without those changes SAT will interfere with some attempts to write "high performance Haskell", as we saw in some posts on Haskell-Cafe earlier this year. In particular, the version in HEAD lacks the tail call criterion, so many things that look like reasonable loops will be turned into functions with extra (unneccesary) thunk creation. }}}
6.10 was a long time ago. Has anything changed since then? Does it make sense to enable that optimisation now? What are the mentioned heuristics and were they finally implemented? Does anyone know what Haskell-cafe posts does Max refer to?
New description: At the moment the Static Argument Transformation (SAT) optimisation is not run unless explicitly enabled with `-fstatic-argument-transformation`. There was a comment by Max Bolingbroke in DynFlags that said this (that comment is now removed and replaced with a reference to this ticket): {{{ Max writes: I think it's probably best not to enable SAT with -O2 for the 6.10 release. The version of SAT in HEAD at the moment doesn't incorporate several improvements to the heuristics, and I'm concerned that without those changes SAT will interfere with some attempts to write "high performance Haskell", as we saw in some posts on Haskell-Cafe earlier this year. In particular, the version in HEAD lacks the tail call criterion, so many things that look like reasonable loops will be turned into functions with extra (unneccesary) thunk creation. }}} 6.10 was a long time ago. Has anything changed since then? Does it make sense to enable that optimisation now? What are the mentioned heuristics and were they finally implemented? Does anyone know what Haskell-cafe posts does Max refer to? -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 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): Wiki Page: | -------------------------------------+------------------------------------- Changes (by mpickering): * cc: mpickering (added) Comment: There are lots of cases where this transformation would be very beneficial. I am interested in reviving it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 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): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Good! Can you give specifics about "lots of cases"? It is good for optimisations to be informed by concrete use-cases. See [https://www.microsoft.com/en-us/research/publication/compilation- transformation-non-strict-functional-languages/ Andre Sansos's thesis] which has a whole chapter. Also [http://ojs.statsbiblioteket.dk/index.php/brics/article/view/18785 Danvy's lambda-dropping paper] Keep me posted! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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 mpickering): * keywords: => StaticArgumentTransformation -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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 simonpj): * cc: kavon (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by mpickering): Here are the results of running nofib with and without `-fstatic-argument- transformation`. {{{ -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- CS 0.0% 0.0% 0.181 0.180 0.0% CSD -0.6% -100.0% -98.0% -98.0% 0.0% FS 0.0% 0.0% -7.5% -7.5% 0.0% S 0.0% 0.0% -0.1% -0.1% 0.0% VS 0.0% 0.0% -0.1% -0.1% 0.0% VSD 0.0% 0.0% 0.008 0.008 0.0% VSM 0.0% 0.0% -10.9% -10.9% 0.0% anna -0.4% +1.4% 0.059 0.059 0.0% ansi 0.0% 0.0% 0.000 0.000 0.0% atom +0.2% -98.6% 0.003 0.003 -33.3% awards 0.0% 0.0% 0.000 0.000 0.0% banner 0.0% 0.0% 0.000 0.000 0.0% bernouilli -0.0% 0.0% 0.093 0.093 0.0% binary-trees 0.0% 0.0% -1.6% -1.6% 0.0% boyer 0.0% 0.0% 0.023 0.023 0.0% boyer2 0.0% 0.0% 0.004 0.004 0.0% bspt +1.0% -0.4% 0.004 0.004 0.0% cacheprof 0.0% -0.1% -0.9% -0.9% -0.9% calendar 0.0% 0.0% 0.000 0.000 0.0% cichelli +0.4% -8.3% 0.037 0.037 0.0% circsim +0.0% 0.0% +1.3% +1.3% 0.0% clausify +0.0% 0.0% 0.020 0.020 0.0% comp_lab_zift +0.9% +0.1% 0.102 0.102 0.0% compress -0.0% -0.1% 0.075 0.075 0.0% compress2 0.0% 0.0% 0.086 0.086 0.0% constraints 0.0% 0.0% +0.3% +0.3% 0.0% cryptarithm1 0.0% 0.0% +8.3% +8.2% 0.0% cryptarithm2 0.0% 0.0% 0.004 0.004 0.0% cse -0.0% 0.0% 0.001 0.001 0.0% digits-of-e1 0.0% 0.0% +5.2% +5.2% 0.0% digits-of-e2 0.0% 0.0% +5.7% +5.7% 0.0% eliza 0.0% 0.0% 0.000 0.000 0.0% event +0.0% +1.2% 0.085 0.085 +9.5% exact-reals 0.0% 0.0% +1.2% +1.2% 0.0% exp3_8 0.0% 0.0% 0.129 0.130 0.0% expert -0.0% +0.0% 0.000 0.000 0.0% fannkuch-redux 0.0% 0.0% -1.2% -1.2% 0.0% fasta 0.0% 0.0% +2.0% +2.1% 0.0% fem 0.0% 0.0% 0.013 0.013 0.0% fft +0.0% -1.0% 0.018 0.018 0.0% fft2 0.0% 0.0% 0.026 0.026 0.0% fibheaps -0.0% +5.9% 0.014 0.014 0.0% fish 0.0% 0.0% 0.006 0.006 0.0% fluid 0.0% 0.0% 0.004 0.004 0.0% fulsom 0.0% 0.0% 0.161 0.161 0.0% gamteb 0.0% 0.0% 0.025 0.025 0.0% gcd 0.0% 0.0% 0.024 0.024 0.0% gen_regexps 0.0% 0.0% 0.000 0.000 0.0% genfft -0.0% -2.6% 0.017 0.017 0.0% gg +0.0% -1.8% 0.005 0.005 0.0% grep 0.0% 0.0% 0.000 0.000 0.0% hidden +0.0% 0.0% -4.9% -5.0% 0.0% hpg +0.0% -0.0% 0.049 0.049 0.0% ida +0.7% +0.1% 0.046 0.046 0.0% infer -0.0% +0.0% 0.029 0.029 0.0% integer 0.0% 0.0% -4.5% -4.5% 0.0% integrate 0.0% 0.0% 0.079 0.079 0.0% k-nucleotide 0.0% 0.0% +0.7% +0.7% 0.0% kahan 0.0% 0.0% 0.195 0.195 0.0% knights +0.0% -0.2% 0.002 0.002 0.0% lambda 0.0% 0.0% 0.0% -0.0% 0.0% last-piece -0.2% +4.6% +3.2% +3.2% 0.0% lcss 0.0% 0.0% -0.6% -0.6% 0.0% life 0.0% 0.0% 0.149 0.149 0.0% lift 0.0% 0.0% 0.001 0.001 0.0% linear 0.0% 0.0% +0.1% +0.1% 0.0% listcompr +0.0% -0.4% 0.055 0.055 0.0% listcopy +0.0% -0.4% 0.059 0.059 0.0% maillist 0.0% 0.0% 0.032 0.033 -2.3% mandel -0.1% 0.0% 0.040 0.040 0.0% mandel2 +0.1% 0.0% 0.002 0.002 0.0% mate +0.2% -5.5% -4.6% -4.6% 0.0% minimax 0.0% 0.0% 0.001 0.001 0.0% mkhprog 0.0% 0.0% 0.001 0.001 0.0% multiplier +0.9% +0.7% 0.054 0.054 0.0% n-body 0.0% 0.0% -0.5% -0.5% 0.0% nucleic2 0.0% 0.0% 0.045 0.045 0.0% para +0.7% -0.5% 0.162 0.162 0.0% paraffins 0.0% 0.0% 0.064 0.064 0.0% parser 0.0% 0.0% 0.015 0.015 0.0% parstof +1.0% +4.0% 0.004 0.004 0.0% pic +0.0% 0.0% 0.004 0.004 0.0% pidigits 0.0% 0.0% -0.1% -0.3% 0.0% power +0.7% +1.5% 0.210 0.210 +9.1% pretty 0.0% 0.0% 0.000 0.000 0.0% primes 0.0% 0.0% 0.039 0.039 0.0% primetest 0.0% 0.0% 0.060 0.060 0.0% prolog +0.1% +0.0% 0.001 0.001 0.0% puzzle 0.0% 0.0% 0.073 0.073 0.0% queens 0.0% 0.0% 0.007 0.007 0.0% reptile +0.3% +0.0% 0.006 0.006 0.0% reverse-complem 0.0% 0.0% 0.061 0.061 0.0% rewrite -0.1% -1.8% 0.010 0.010 0.0% rfib 0.0% 0.0% 0.009 0.009 0.0% rsa +0.1% +0.0% 0.014 0.014 0.0% scc +0.0% +0.2% 0.000 0.000 0.0% sched 0.0% 0.0% 0.012 0.012 0.0% scs 0.0% 0.0% -0.1% -0.1% 0.0% simple 0.0% 0.0% 0.119 0.119 0.0% solid +0.6% -14.8% 0.065 0.065 0.0% sorting -0.1% 0.0% 0.001 0.001 0.0% spectral-norm 0.0% 0.0% +0.9% +0.9% 0.0% sphere 0.0% 0.0% 0.027 0.027 0.0% symalg +0.0% -0.8% 0.005 0.005 0.0% tak 0.0% 0.0% 0.007 0.007 0.0% transform -0.1% -0.4% 0.190 0.190 0.0% treejoin +0.0% +2.3% 0.094 0.094 -3.6% typecheck +0.5% -1.9% 0.151 0.151 0.0% veritas -1.3% -0.0% 0.001 0.001 0.0% wang +0.1% -1.1% 0.055 0.055 -5.3% wave4main -0.0% -0.0% 0.156 0.156 0.0% wheel-sieve1 0.0% 0.0% +10.1% +10.0% 0.0% wheel-sieve2 0.0% 0.0% 0.135 0.135 0.0% x2n1 0.0% 0.0% 0.003 0.003 0.0% -------------------------------------------------------------------------------- Min -1.3% -95.0% -95.0% -95.0% -33.3% Max +1.0% +5.9% +10.1% +10.0% +9.5% Geometric Mean +0.1% -5.3% -10.2% -10.2% -0.3% }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Wow, a geometric mean of -10% is quite impressive if it is real. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by nomeata): It seems that this mean is greatly skewed by `CSD` with -98%. There is one other with -10, the rest of the improvements are less extreme, and there are some regressions. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by simonpj): Good data, thank you. Next step: * Characterise where the big wins come from * Characterise where the regressions come from I usually start with allocations and use `-ticky` to localise it. I think SAT is quite hard to ALWAYS win. But I speculate that SAT on a join point IS always a win. Joachim is the expert there. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by mpickering): I looked at all the examples where allocations changed a significant amount. Essentially it seems to me the transformation is bad for allocations if it doesn't lead to more simplification but potentially very good if it does. There were particular situations where overloaded functions were satted as they had a normal static argument and a known dictionary argument. Normally the specialiser would be expected to deal with these but self- recursive functions are only specialised across modules if `-fspecialise- aggresively` is turned on or they are marked with an `INLINABLE` pragma. (For example `CSD`, `gg`). In situations where the definition was not further simplified, allocations tended to increase by a few %. So I'm not convinced that the example in comment:13 would be a win. There were also some situations where the unfolding for the satted definition was not exported as it was too big so there was never any potential for improvement. To sum up, there were some wins where SAT acted across modules where normal specialisation failed. Satting static function arguments could also be very good but only if there are actually some cases where the function is called with a static function argument. (For example #14211) In general though there was very little benefit satting as it seems that static values are not usually consumed by functions (and so no further simplification takes place after the sat). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by simonpj): I'm having trouble understanding comment:24. Would it be possible to give a concrete example for each situation you describe? And what's the bottom line? Are there any situations where it predictably wins? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by mpickering): The main benefit (in nofib) was when SAT was acting to eliminate dictionary arguments which the specialiser has failed to deal with for whatever reason. The other big benefit is like in #14211 where a lot more simplification could happen by a function being inlined into a loop. There were not any of these cases that I saw in nofib but might be more common in real code. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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 nomeata): * cc: nomeata (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation 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: | -------------------------------------+------------------------------------- Comment (by osa1): I don't know what changed since comment:20, but I get literally no difference in allocations with `-fstatic-argument-transformation` when I run nofib with GHC 8.4.2. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:28 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation, | LateLamLift 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 simonpj): * keywords: StaticArgumentTransformation => StaticArgumentTransformation, LateLamLift -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation, | LateLamLift Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 14816 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * related: => 14816 Comment: For anyone working on this who has problems debugging performance regressions, #14816 might be worth taking a look at. TLDR; The Demand Analyser tries hard to be precise about parameters, but gives up early on demands on free variables for analysis performance reasons. So, when SAT turns parameters into free variables, there is the slight chance that e.g. SATed single-entry thunks are no longer identified. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:30 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9374: Investigate Static Argument Transformation -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: (none) Type: task | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.9 Resolution: | Keywords: | StaticArgumentTransformation, | LateLamLift Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: 14816 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by maoe): * cc: maoe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9374#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC