# 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:** 6\
**Page:** 4

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [March 10, 2023, 7:01am UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/61 "2023-03-10T07:01:28Z")

</div>

> Can you offer a source or reference?

Sorry, my memory fails me on this (otherwise I’d have offered a reference originally). All I know is that I did get this strong impression at one point, but I could be wrong. I’d need to read both the original issue and this thread and have a think.

---

<div class="post-metadata">

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

</div>

It seems that first porting the flisp code to Julia without adding any features would be worthwhile to make it more accessible, but it can only be done by someone who already understands the code to some level. The fact that it was written in flisp rather than Julia in the first place makes me think that this is not trivial. On the other hand, with Julia having its roots in LISP maybe there is a translation that is close?  
I find even some core Julia code hard to read but I presume that‘s because the concepts behind it are foreign, not because it is not succinct. The flisp part could be the most succinct representation of the concepts but it not being thoroughly documented makes it impossible for a larger community to understand. So part of the translation work would probably involve documenting why the code is the way it is.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [March 10, 2023, 5:13pm UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/63 "2023-03-10T17:13:20Z")

</div>

I think my comment was basically that one needs to be able to do some of the things that type-inference does, and so for as long as lowering is strictly before type-inference there’s no hope of solving it. That doesn’t mean it will be easy (or possible) even if we can go back-and-forth between the two. Others have thought about this much more than I have, though.

---

<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 11, 2023, 2:10am UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/64 "2023-03-11T02:10:59Z")

</div>

> [@GunnarFarneback](#):
>
> I see no disconnect between changes in lowering being required while not being sufficient.

I suppose this depends on what we consider “sufficient.” We can obviously contrive measures by which only infinite effort would be considered sufficient, and which would demand we first solve the NP-hard class of problems, but such sufficiency measures are unreasonable.

I consider it sufficient if we eliminate any boxes that we obviously can, and we parameterize boxes with whatever concrete types that we obviously can—where obviousness is measured as a function of language semantics, syntax, and function return types, without attempting to solve undecidable problems, nor demand lowering make decisions that would require access to runtime values, nor other unreasonably difficult, unintuitive, and brittle things. Although great strides have been taken, there’s a lot of meat still on the bone here. (The [example](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-captured) in Performance Tips is one such case of a box that’s obviously unnecessary per language semantics.)

By this measure, I would consider the changes that are possible in lowering to be sufficient. As an example of something that such “sufficient” changes in lowering should be able to achieve, this would become type-stable (from knowledge that `return_type(Tuple{typeof(+), Int, Int}) == Int` and thus storing `a` in a `Core.Box{Int}`):

```julia
let a=0
    foreach(1:10) do i::Int
        a += i
    end
    a
end

```

but, remove the `::Int` annotation, and it’s reasonable for it to be type-unstable because it can’t be known from syntax and `return_type` what type `i` will have and thus what type `a` will have.

---

<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 17, 2023, 12:30pm UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/65 "2023-03-17T12:30:29Z")

</div>

To summarize Idea 1:

- Stop boxing captures that have no syntactically reachable assignment in/after the closure’s definition, as demonstrated in pseudo-code [here](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/55). It’s a simple idea which appears to require O(n) time.
- Because assigning a variable multiple times before capturing it, but not after, is a common pattern, the boxes which would be eliminated by Idea 1 are surprisingly numerous, including: [1](https://github.com/JuliaLang/julia/issues/15276#issuecomment-233107381), [2](https://discourse.julialang.org/t/spawn-large-memory-allocation-reduced-when-some-code-abstracted-out-in-a-function/88691), [3](https://discourse.julialang.org/t/strange-memory-allocations/95203), [4](https://github.com/JuliaLang/julia/issues/47539), [5](https://github.com/JuliaLang/julia/issues/45725), [6](https://github.com/JuliaLang/julia/issues/42996), [7](https://github.com/JuliaLang/julia/issues/42052), [8](https://discourse.julialang.org/t/type-unstable-function-because-same-variable-name-used-twice/58810/9), [9](https://discourse.julialang.org/t/base-generator-being-slow-because-type-inference-fails-with-isnothing/57297), [10](https://discourse.julialang.org/t/type-instability-of-nested-function/57007), [11](https://discourse.julialang.org/t/type-instability-in-closure-after-reassigning-a-variable/33656), [12](https://discourse.julialang.org/t/redefining-an-integer-makes-computing-time-blow-up/10535), [13](https://discourse.julialang.org/t/call-fastclosures-jl-closure-in-array-comprehensions/93622/3), [14](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-captured).
- Even as simple as Idea 1 is conceptually, it is still superior to the current boxing decision rule.

Absent legitimate protest, I’ll continue.

**Explaining Idea 2**

> [@Sukera](#):
>
> > [@uniment](#):
> >
> > Again, Idea 2 is simply to type-parameterize `Core.Box`, which doesn’t require any type inference.
> 
> It does require type inference

Again, Idea 2 does _not_ require type inference in lowering; it’s simply making `Core.Box` to be type-parameterizable, akin to `Base.RefValue`. Benefit can be immediately realized in the cases where a variable is type-annotated, which again doesn’t require type inference in lowering.

From [Performance Tips](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-captured):

> if it is known that a captured variable does not change its type, then this can be declared explicitly with a type annotation (on the variable, not the right-hand side)  
> …  
> The type annotation partially recovers lost performance due to capturing because the parser can associate a concrete type to the object in the box.

Consider the following code, in which the programmer follows this guidance by annotating `s` as `Int` to achieve type-stability:

```julia
function f(x::Int)
    s::Int = 0
    foreach(1:x) do i; s += 1 end
    return s
end

```

Inspect the lowered code, and you will see that `s` is contained in a mutable, type-unstable `Core.Box`, and `Int` is asserted whenever `s` is assigned or accessed. _Note that lowering doesn’t need to know what an `Int` is; it just needs to know that `s` is being annotated as one._ It’s obvious that this same information could be used to type-parameterize the `Box`, if only `Box` were type-parameterizable.

To demonstrate the performance improvement to be had, consider two functions: `fa`, which imitates `f` using `Ref{Any}` to mimic the type-unstable `Box`, and `fb`, which uses a `Ref{Int}` to mimic the proposed type-parameterized `Box{Int}`:

```julia
function fa(x::Int)
    s = Ref{Any}(0::Int)
    foreach(1:x) do i; s[] = (s[]::Int + 1)::Int end
    return s[]::Int
end
function fb(x::Int)
    s = Ref{Int}(0)
    foreach(1:x) do i; s[] = s[] + 1 end
    return s[]
end

```

(Note, `fa` asserts `::Int` whenever `s` is accessed or assigned, just like `f`. You can also add `::Int` assertions into `fb`; those don’t matter.)

Let’s check the performance:

```julia
julia> using BenchmarkTools
       a=@btime fa($1000)
       b=@btime fb($1000)
       a ≡ b
  4.143 μs (489 allocations: 7.64 KiB)
  1.800 ns (0 allocations: 0 bytes)
true

```

(Note, you can run `@btime f($1000)` to confirm that `f` and `fa` are similar.)

Clearly, later compiler stages are heavily optimizing `fb`, and the same optimizations aren’t applied to `fa`, which has ~1000x worse performance. If we type-parameterized `Core.Box` as Idea 2 proposes, then `f` would act like `fb` instead of `fa`, and we’d unlock the full performance that type annotation should allow us.

In most cases, the benefit from type-parameterizing `Box` won’t be as great as in this example, but they’re often still quite substantial. For the example `abmult2` in Performance Tips, the benefit is about a 30% timing improvement; other functions I’ve seen improved about 50%. As it stands, we’re leaving a lot of performance on the table.

Notes:

- This idea was proposed by @rapus95 [three years ago](https://github.com/JuliaLang/julia/issues/15276#issuecomment-628988268), but it didn’t receive satisfactory consideration.
- Similar performance improvements could be had for type-annotated globals.
- At some point, when lowering can eventually type-infer, you’d want type-parameterized `Box`es anyway—so this idea should be about as controversial as the round earth.

---

<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:** [February 16, 2024, 8:56pm UTC](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260/66 "2024-02-16T20:56:29Z")

</div>

Issue opened for Idea 1:

[Don’t box captured variables that are not assigned after closure declaration · Issue #53367 · JuliaLang/julia (github.com)](https://github.com/JuliaLang/julia/issues/53367)

[Previous page](https://discourse.julialang.org/t/rfc-some-ideas-to-tackle-15276-performance-of-captured-variables-in-closures/95260.md?page=3)