Skip to content
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

Closed
vicuna opened this Issue Nov 18, 2013 · 8 comments

Comments

Projects
None yet
2 participants
@vicuna
Copy link
Collaborator

vicuna commented Nov 18, 2013

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:

let foo x y =
  let ret n = x + n * y in
  if x mod 2 = 0 then ret 3
  else if y mod 2 = 0 then ret 4
  else 10

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:

let () =
  for k = 1 to 1000 do
    for i = 1 to 1000 do
      for j = 1 to 1000 do
        ignore (foo i j)
      done
    done
  done

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:

let () =
  for k = 1 to 1000 do
    for i = 1 to 1000 do
      for j = 1 to 1000 do
        ignore (foo 1 1)
      done
    done
  done

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

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Nov 18, 2013

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.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Nov 18, 2013

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.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Nov 18, 2013

Comment author: @chambart

In those particular examples, the main limitation of the current compiler seems to
be its inability to eliminate the useless closure and for the second case, to inline
a function with a local closure.

An other way to improve this kind of code would be to do some lambda lifting. You
loose the possibility of sharing the context for register allocation, but you
could apply this even when the function is not tail called. For the unboxing,
this is doable at function interface, so it is not necessary lost.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Nov 19, 2013

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.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Dec 5, 2013

Comment author: @alainfrisch

Uploaded an improved patch:

  • More tail contexts are detected (r.h.s of || and &&).

  • Apply the rewriting before other optimizations on the lambda-code (in particular, this allows to benefit from the pass which turns local references into mutable variables).

  • Also inline any local function used only once (fully-applied).

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Jun 15, 2015

Comment author: @alainfrisch

Added a version (local_continuations_3.diff) adapted for trunk.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Mar 7, 2017

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.

@vicuna

This comment has been minimized.

Copy link
Collaborator Author

vicuna commented Nov 20, 2018

Comment author: @alainfrisch

Ref: #2143

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.