RFC: Some Ideas to Tackle #15276 - performance of captured variables in closures

Internals & Design
, ,
55

To make Idea 1 of the OP work with @goto, scrap the above idea of working with the AST and instead work closer to the IR. Seems easier overall (less special cases).

Draft Pseudo-Code of Idea 1 (with goto):

(assumption: all AST has been lowered to flattened IR, but no Core.Boxes have been inserted yet. There might currently be no point during lowering where this is true, but the concept could be adapted.)

With prior knowledge that a local variable x is captured by a closure, decide whether to box x by the following procedure (true for box, false for no-box):

Define assigns(n,x,checked) to take a line number n, a symbol x, and a set of previously explored line numbers checked. assigns operates as follows:

  1. If n ∈ checked, return false.
  2. Push n into checked.
  3. While true:
    a. If expression at line n is a Expr(:(=), x, ...), return true.
    b. If expression at line n is a :method of a closure known to capture x, push n into checked. Loop over every sub-expression in its CodeInfo’s .code. If any is a Expr(:(=), x, ...), return true.
    c. If expression at line n is a Core.GotoNode, return assigns(ex.label,x,checked).
    d. If expression at line n is a Core.GotoIfNot, return assigns(n+1,x,checked)||assigns(ex.label,x,checked).
    e. If expression at line n is a Core.ReturnNode, or if there are no more expressions, return false.
    f. Increment n.

Then, initialize checked to an empty set; let n be the line at which the closure :method is defined; and if assigns(n,x,checked), then box x. If multiple closures are known to capture x, simply call assigns on them without emptying checked to save some computations.

The basic gist is: Explore all expressions that are syntactically reachable in and after the closure’s declaration. If any is an assignment to the captured variable, then box it—but otherwise don’t. Keep a record checked of labels and methods that have been visited, to avoid repeated work and getting stuck in loops. As before:

cc @simeonschaub you seem to have a pretty good grasp of closure capture boxing; do you mind if I entice you to opine?