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

**URL:** <https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260>\
**Category:** Internals & Design\
**Tags:** inference, type-stability, corebox\
**Created:** [February 27, 2023, 10:09am UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260 "2023-02-27T10:09:31Z")\
**Posts on this page:** 1\
**Showing post:** 53

<div class="post-metadata">

**Author:** ![uniment](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/uniment/32/24532_2.png) [@uniment](https://discourse.julialang.org/u/uniment)\
**Post date:** [March 6, 2023, 10:34am UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/53 "2023-03-06T10:34:18Z")

</div>

Edit: See [comment 55](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/55) for better draft pseudo-code.

> [@mbauman](#):
>
> in general, proving that a re-assignment does not occur during the “lifetime” of a closure is tantamount to solving the halting problem … it’s very easy to walk yourself into abhorrently bad O(n^2) (or worse) compiler performance

Drafting some rough psuedo-code of the proposal I’ve been imagining for Idea 1, barring any egregious oversight, it appears to be O(n) in the number of expressions in the function body. I’d appreciate a sanity check.

**Draft Pseudo-Code of Idea 1:**

Define `assigns` to take an expression and a symbol `x`. Return true if it or any of its subexpressions (recursive) makes any assignment to `x` [excluding nested scopes with their own local `x`]—i.e., check for `Expr(:(=), x, ...)` and similar assignments, as well special-cased handling of `:tuple` assignments. Otherwise, return false.

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

1. Check inside body of closure. If it `assigns` to `x`, return true.
2. Set `parent` as closure’s parent expression, `child` as closure expression.
3. While true: # climb tree, search neighbors for assignments  
a. If `parent` is the body of a `for` or `while` loop, and if `x` is bound to an outer scope, check subexpressions of `parent` that preceed `child`. If any `assigns` to `x`, return true.  
b. If `parent` is a `for` or `while` loop, and if `x` is bound to an outer scope, check if `parent`’s condition `assigns` to `x`. If so, return true.  
c. If `parent` is the `.args[2]` of a `if` or `elseif` conditional, continue. # next branch is syntactically mutually exclusive.  
d. If `parent` is a `tuple` expression, check if it `assigns` to `x`. If so, return true.  
e. Check subexpressions of `parent` that succeed `child`. If any `assigns` to `x`, return true.  
f. If `parent` is the scope `x` is bound to, break.  
g. Set `child=parent` and `parent` to its own parent and continue loop.
4. Return false.

The basic gist is: if the captured variable has any assignment expression in or after the closure’s declaration, or before it if in a loop, and discounting branches that are syntactically unreachable from the closure’s declaration, then box it—but otherwise don’t. Allowing for identifiers to be rebound unboxed before the closure is declared (and only boxing if identifiers can be rebound _after_ closure declaration) should cause a good number of boxes to go away (such as [this](https://github.com/JuliaLang/julia/issues/15276#issuecomment-233107381), [this](https://discourse.julialang.org/t/spawn-large-memory-allocation-reduced-when-some-code-abstracted-out-in-a-function/88691), [this](https://discourse.julialang.org/t/strange-memory-allocations/95203), [this](https://github.com/JuliaLang/julia/issues/47539), [this](https://github.com/JuliaLang/julia/issues/45725), [this](https://github.com/JuliaLang/julia/issues/42996), [this](https://github.com/JuliaLang/julia/issues/42052), [this](https://discourse.julialang.org/t/type-unstable-function-because-same-variable-name-used-twice/58810/9), [this](https://discourse.julialang.org/t/base-generator-being-slow-because-type-inference-fails-with-isnothing/57297), [this](https://discourse.julialang.org/t/type-instability-of-nested-function/57007), [this](https://discourse.julialang.org/t/type-instability-in-closure-after-reassigning-a-variable/33656), [this](https://discourse.julialang.org/t/redefining-an-integer-makes-computing-time-blow-up/10535), and [these](https://discourse.julialang.org/t/call-fastclosures-jl-closure-in-array-comprehensions/93622/3), not to mention [the one from Performance Tips](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-captured) as well as most others that I’ve encountered), and barring any mistakes [and excluding `@goto`], afaict it should be a strict improvement over current behavior.

Notes:

- There may be a way to accommodate `@goto`—initial thoughts suggest it’s still O(n), though it seems likely to require more computation—but I’ll defer those thoughts for later until I gain confidence in this one.
- Local named functions also present a unique challenge, but on initial thought they too seem doable. I can think of some degenerate behavior, but it coincides with [existing degenerate behavior](https://github.com/JuliaLang/julia/issues/5148#issuecomment-1336341977) so introduces no new concern.
- Local recursive named functions [deserve consideration](https://github.com/JuliaLang/julia/issues/47760).

---

_[View the full topic](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260)._