#9476: Implement late lambda-lifting -------------------------------------+------------------------------------- Reporter: simonpj | Owner: sgraf Type: feature request | Status: closed Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: LateLamLift Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #8763 #13286 | Differential Rev(s): Phab:D5224 Wiki Page: LateLamLift | -------------------------------------+------------------------------------- Comment (by sgraf): OK, it turns out that `paraffins` regresses by 8% in counted instructions when allowing arbitrary closure growth because of the very same function I pinned down as the reason for the alleged speed-up in comment:56. It seems like we don't want to lift the inner loop of such a list comprehension. On the other hand, there's `gen_regexp` which improves by 2-5% in runtime when we lift the next-to-inner function of a list comprehension (`go_s7zy` below): {{{ let { go_s7zy = sat-only \r [x1_s7zz] case ># [x1_s7zz y_s7zx] of { __DEFAULT -> case chr# [x1_s7zz] of ds13_s7zB { __DEFAULT -> let { ds14_s7zC = CCCS C#! [ds13_s7zB]; } in let { z_s7zD = \u [] case +# [x1_s7zz 1#] of sat_s7zE { __DEFAULT -> go_s7zy sat_s7zE; }; } in let { go1_s7zF = sat-only \r [ds15_s7zG] case ds15_s7zG of { [] -> z_s7zD; : y1_s7zI ys_s7zJ -> let { sat_s7zL = \u [] go1_s7zF ys_s7zJ; } in let { sat_s7zK = CCCS :! [ds14_s7zC y1_s7zI]; } in : [sat_s7zK sat_s7zL]; }; } in go1_s7zF lvl13_s7zw; }; 1# -> [] []; }; } in case ord# [c1_s7za] of sat_s7zM { __DEFAULT -> go_s7zy sat_s7zM; }; }}} Lifting `go_s7zy` leads to a very slight increase in allocation (so would be disallowed from the perspective of closure growth), but a decrease in runtime. Maybe this is some low-level thing again, I don't know. The difference in Cmm is as expected and I wouldn't have expected a speed-up. So, to sum this up: Deactivating closure growth checks, thus allowing arbitrary closure growth resulting from lambda lifting - leads to an improvement of ~0.1% in runtime and counted instructions (though the two don't necessarily coincide). - also leads to unpredictable regressions in total allocations, like +28.6% in `wheel-sieve1`. From the regressions I investigated (`gen_regexp`, for example), the bindings the lifting decisions of which are responsible for the biggest regression in allocations (+10% due to the inner loop above, `go1_s7zF`) are not necessarily the same bindings which contribute the speed-ups (`go_s7zy` above). I'm not sure how to come up with a criterion that separates the two classes (beneficial to lift vs. not) of bindings, so I suggest we stick to the current closure growth heuristic. Which is a little more conservative than necessary, but avoids arbitrary regressions in allocations on STG level. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9476#comment:76 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler