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

Do not capture recursive local function's self-identifier (to avoid box) #53295

Open
uniment opened this issue Feb 12, 2024 · 3 comments
Open
Labels
compiler:lowering Syntax lowering (compiler front end, 2nd stage)

Comments

@uniment
Copy link

uniment commented Feb 12, 2024

Consider the function:

julia> fibby = let
           fib(n) = n1 ? n : fib(n-1)+fib(n-2)
       end
(::var"#fib#3") (generic function with 1 method)

This is approximately equivalent to:

struct var"#fib#3" <: Function
    fib :: Core.Box
end
(fib::var"#fib#3")(n) = n1 ? n : fib.fib.contents(n-1)+fib.fib.contents(n-2)
fibby = let 
    fib = var"#fib#3"(Core.Box())
    fib.fib.contents = fib
end

The fact that the recursive function boxes its reference to itself here is obviously inefficient and undesirable.

My understanding is that fib's reference to itself must be boxed because of the rule that whenever a capture is or can be assigned after its closure's instantiation, then that capture must be boxed: obviously this is usually a good rule, since the capture's new value could otherwise be unknown to the closure during the closure's lifetime. Here, lowering detects that the local fib identifier's first and only assignment occurs after the local functor object's instantiation, so following this rule, it boxes fib.

However, I propose we carve an exception to this rule for the function's own identifier: if the function's local identifier is only ever assigned to the functor object itself and has no other syntactical assignments anywhere, then it is obvious that the value this identifier is assigned to is always known to the closure throughout its lifetime—it is itself! Thus, with such an exception made, I would hope that lowering could be changed such that the code above would instead become approximately equivalent to:

struct var"#fib#3" <: Function end
(fib::var"#fib#3")(n) = n1 ? n : fib(n-1)+fib(n-2)
fibby = let 
    fib = var"#fib#3"()
end

(this proposal solves #47760 but more elegantly so I'm closing that issue)

@vtjnash
Copy link
Sponsor Member

vtjnash commented Feb 17, 2024

Duplicate of #40990

@vtjnash vtjnash marked this as a duplicate of #40990 Feb 17, 2024
@vtjnash vtjnash closed this as completed Feb 17, 2024
@uniment
Copy link
Author

uniment commented Feb 17, 2024

This is not a duplicate of #40990: whereas that issue presents a problem, this issue presents a solution.

Additionally, #40990 actually exhibits two simultaneous problems: that described here, and also that described in #53338.

@JeffBezanson
Copy link
Sponsor Member

I will close #40990 in favor of this, as it has more detail and along with #53338 splits it into two more specific issues.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler:lowering Syntax lowering (compiler front end, 2nd stage)
Projects
None yet
Development

No branches or pull requests

3 participants