New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Better compilation of local functions only used for tail calls #6242
Comments
Comment author: @mshinwell I wonder if Pierre Chambart's work on better inlining might subsume these cases. (In particular, I have a feeling that the return continuations might usually be small enough that it would be reasonable to inline them every time they occur.) If fully inlined, the definition of [ret] is dead code. |
Comment author: @alainfrisch It's true that a more aggressive inlining (and a fix to remove the closure allocation if it is not needed) could optimize away some cases, but in many cases I have in mind, there is a complex continuation (maybe called rarely enough) which won't be inlined. |
Comment author: @chambart In those particular examples, the main limitation of the current compiler seems to An other way to improve this kind of code would be to do some lambda lifting. You |
Comment author: @alainfrisch Inlining require heuristics, which might be hard to predict, and it will not always be applicable (it could blow up the code size). Lambda lifting seems to be a better fit, and it would indeed be applicable to more contexts (although it would require special care for the case where the surrounding function is a recursive function called by the continuation). But for the specific cases I have in mind (sharing continuation between several branches), the overhead of crossing a function boundary can be eliminated, and the corresponding optimization is not only very simple, but also very predictable. Unboxing at function interface is possible (and I hope it will be included!), but it will probably introduce multiple entry points or a wrapping function, in a case where this is useless (so we'd need to rely on a further optimization to remove this extra stuff). And there are more optimizations possible within a single function (not only register allocation and unboxing), such as turning references into mutable variables. |
Comment author: @alainfrisch Uploaded an improved patch:
|
Comment author: @alainfrisch Added a version (local_continuations_3.diff) adapted for trunk. |
Comment author: @mshinwell I tend to think we should leave all of this to Flambda. It should already be able to do the lambda lifting and I think we could add a contification rule in the forthcoming version to avoid having to lambda lift. As an aside, I don't think use-based optimisations such as inlining functions used once should be on by default, since they produce fragility at the user level. |
Comment author: @alainfrisch Ref: #2143 |
Original bug ID: 6242
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: resolved (set by @alainfrisch on 2018-11-27T17:05:07Z)
Resolution: fixed
Priority: normal
Severity: feature
Target version: later
Fixed in version: 4.08.0+dev/beta1/beta2
Category: back end (clambda to assembly)
Tags: patch
Related to: #5879 #7017
Monitored by: @gasche @chambart @jmeber
Bug description
It is a common idiom to define local functions to share a "continuation" (used in several branches of the current function). Example:
This requires to allocate a closure, even if it won't be called. I propose to detect such cases of local binding of a function which is only used, fully applied, in tail position within the body of the local binding. This can be compiled more efficiently by turning the function into a "staticcatch" handler. I attach a patch which implements this optimization at the level of the lambda code.
Benefits:
Avoid the allocation of the local closure.
Can benefit for function-wide register allocation and float unboxing.
More chance of inlining the whole function (because its body becomes simpler).
Possible drawbacks:
Slower compilation. The optimization is currently implemented as a single pass over the lambda code, plus an extra traversal to count the number of uses in tail position for each local binding to a function. It's possible to do a single traversal (but it's probably useless for hand-written code at least).
Remove chances of inlining the local function (currently, even when it is inlined, the closure is still allocated).
Micro-benchmark of the code above with:
with -inline 0:
BEFORE: 5.19s
AFTER: 3.94s (25% speedup)
with -inline 10000:
BEFORE: 4.98s
AFTER: 3.04s (39% speedup)
Micro-benchmark of the code above with:
with -inline 0:
BEFORE: 5.36s
AFTER: 3.88s (27% speedup)
with -inline 10000:
BEFORE: 5.36s
AFTER: 0.64s (88% speedup)
Possible improvements to the patch:
Detect the case where the "continuation" takes a single () argument (and remove it from the static handler). This is probably going to be mostly cosmetic.
Detect more "tail" contexts (in particular the r.h.s. of || and &&).
Note: the same effect could be achieved manually for critical code with "local exceptions" (#5879), but it doesn't seem they will be included.
File attachments
The text was updated successfully, but these errors were encountered: