Locally-Scoped Named Functions have Surprising Behavior that Causes Poor Performance

[uniment]

Background:

We have four different syntaxes to declare functions: two named function syntaxes and two anonymous function syntaxes. The differentiating feature of the named function syntaxes is function identifier type declaration to stabilize the type. This is convenient (don’t need keyword const), great for performance, and quite useful for declaring recursive functions.

Example:

Named function syntax outperforms [non-const] anonymous functions:

julia> function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
fib (generic function with 1 method)

julia> @btime fib(10)
  364.796 ns (0 allocations: 0 bytes)
55

julia> fib_sad = function(n) n ≤ 1 ? n : fib_sad(n-1)+fib_sad(n-2) end
#1 (generic function with 1 method)

julia> @btime $fib_sad(10)
  6.900 μs (0 allocations: 0 bytes)
55

Problem:

For whatever reason, in local scopes the named function syntax seems to behave for all intents and purposes like anonymous function syntax by allowing the function's identifier to be reassigned. That means that within a local scope, we have loss of performance and four redundant syntaxes for doing basically the same thing. It’s also a break from the behavior that we come to expect from interacting with these syntaxes at global scope. And because recursive functions require their identifier to be declared simultaneous to their function body, we can’t use the let block trick that works for other variables captured by closures, and we can’t use type-annotation. And because const is disallowed in local scopes, the problem is inescapable.

Examples:

Locally-declared named functions can be reassigned arbitrarily, causing surprising behavior:

julia> f = let
           function test(item) "Let us test $item very carefully." end
           test(item::CarefulType) = "Especially $item must be treated with care."
           test="Syke!"
       end
"Syke!"

Locally-declared recursive functions have very poor performance due to boxing their self-reference:

julia> function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
fib (generic function with 1 method)

julia> @btime fib(10)
  358.081 ns (0 allocations: 0 bytes)
55

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

julia> @btime $fibby(10)
  6.250 μs (0 allocations: 0 bytes)
55

Current Solutions:

It is suggested here to declare the functions as global. This however circumvents the issue and pollutes the global namespace with what should have been local function definitions.

For recursive functions, it is suggested here to use var"#self#". However this is not official API, and also circumvents the issue.

For recursive functions, it is suggested here to use Y-combinators. However this causes performance degradation, and also circumvents the issue.

For recursive functions, it is suggested here to rewrite recursive functions to take themselves as an argument, and wrap them in a calling closure, in a macro-automated fashion. However the extra closure causes increased compile time, and also circumvents the issue.

Proposed Solution:

It seems the right thing to do is to disallow functions declared with named function syntax in local scopes from having their identifier reassigned, consistent with the behavior of named function syntax at the global scope, so that references to them don’t need to be boxed and so that their identifiers' behavior is unsurprising.

Would Solve:

This problem (non-recursive).

This problem (recursive).

This problem (non-recursive)

This problem (recursive)

Probably more.

[giordano]

Isn't the problem that fibby isn't const?

[uniment]

Isn't the problem that fibby isn't const?

No. Declaring fibby to be const does nothing for the locally-defined fib containing a boxed reference to itself.

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

julia> @btime fibby(10)
  6.500 μs (0 allocations: 0 bytes)
55

[vchuravy]

In some sense this is how globals/variables work. I think the solution might in the end be to document:

For recursive functions, it is suggested here to use var"#self#". However this is not official API, and also circumvents the issue.

[uniment]

In some sense this is how globals/variables work.

Can you elaborate or offer a reference? Is there a law of nature that determines this behavior?

My understanding is that the function's reference is being boxed because it cannot be proven that its identifier will not be reassigned. If it is simply imposed that its identifier cannot be reassigned due to the use of special syntax, then boxing its reference can be avoided, no?

[StefanKarpinski]

This is effectively equivalent to implementing #5148. The proposed solution is to:

disallow functions declared with named function syntax in local scopes from having their identifier reassigned, consistent with the behavior of named function syntax at the global scope, so that references to them don’t need to be boxed and so that their identifiers' behavior is unsurprising

This requires deciding on a "local const rule"; as discussed in #5148 this is non-obvious. If we have a rule that works for local functions then it would also work for any other kind of binding. It would be technically breaking to make function definition in local scope implicitly const when it has not been previously, but I suspect we can justify that as a "minor change", although we'd have to do a PkgEval run to be sure.

[vtjnash]

It is a bit more subtle than that, which is that if this was actually detectable to be valid for const, it would already have optimized this. But the code actually currently needs to assume it violates any meaningful definition const, since semantically the first use must appear slightly before the first (and only) assignment.

Which is to say, const is actually the wrong notion here. The actual notion it needs is that there is no use of fib between the syntactic definition of fib and the first usage of fib, so we should detect that it can be syntactically moved to the first usage point by extending the lifetime of the captured variables beyond their initial scope, and then doing some analysis trickiness around the internal usage of fib to detect that it will be the same as #self# at runtime (this is sort of like calling it const, but without all the fuzziness around what const means), allowing lowering to first do a transform to rewrite that usage to eliminate the dependency (I think that is known as the y-combinator pattern)

[StefanKarpinski]

[uniment]

But the code actually currently needs to assume it violates any meaningful definition const, since semantically the first use must appear slightly before the first (and only) assignment. Which is to say, const is actually the wrong notion here.

Is it though? Using anonymous function syntax, const at global scope works to prevent the reference from being boxed:

julia> const fib_happy = n -> n ≤ 1 ? n : fib_happy(n-1)+fib_happy(n-2)
#110 (generic function with 1 method)

julia> @btime fib_happy(10)
  361.658 ns (0 allocations: 0 bytes)
55

So intuitively anyway, it seems like whatever notion this is, just needs to be extended to local scopes.

The actual notion it needs is that there is no use of fib between the syntactic definition of fib and the first usage of fib

This made my brain explode.

then doing some analysis trickiness around the internal usage of fib to detect that it will be the same as #self# at runtime

This proposal is to assert that when a function is declared with named function syntax, this will always hold true regardless of its attempted internal usage.

Unless this behavior is intentional:

Named Functions Declared at Global Scope:

julia> begin
           function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
           function fib() fib = "I'm sure this behavior is desired, yes?" end
       end
fib (generic function with 2 methods)

julia> fib(10)
55

julia> fib()
"I'm sure this behavior is desired, yes?"

julia> fib(10)
55

Named Functions Declared in Local Scope:

julia> fibby = let
           function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
           function fib() fib = "I'm sure this behavior is desired, yes?" end
       end
(::var"#fib#1") (generic function with 2 methods)

julia> fibby(10)
55

julia> fibby()
"I'm sure this behavior is desired, yes?"

julia> fibby(10)
ERROR: MethodError: objects of type String are not callable

[vtjnash]

works to prevent the reference from being boxed

But fib_happy is boxed there, so I am not entirely sure what this example was supposed to prove. I think you mean to say something about how it was dynamically observed to be assigned before the first time it was used, but that is what I attempted to explain above is the necessary property, and can sometimes be satisfied by const, but is not the same.

[vtjnash]

Unless this behavior is intentional:

This is intentional, and should probably move discussion to discourse of this, since this is just basic scope rule stuff related to declaring fib as a local in the first example (no explicit global annotation from local scope) and declaring it global in the second example (no explicit local annotation from global scope)

[uniment]

But fib_happy is boxed there

Sorry, I do not understand what you mean. fib_happy runs around 20x faster than fib_sad because its reference to itself is not boxed:

julia> fib_sad = n -> n ≤ 1 ? n : fib_sad(n-1)+fib_sad(n-2)
#1 (generic function with 1 method)

julia> const fib_happy = n -> n ≤ 1 ? n : fib_happy(n-1)+fib_happy(n-2)
#3 (generic function with 1 method)

julia> @btime $fib_sad(10)
  6.320 μs (0 allocations: 0 bytes)
55

julia> @btime $fib_happy(10)
  337.019 ns (0 allocations: 0 bytes)
55

This is intentional

Then we disagree about what ought to be intended: my assertion is that named function syntax should take special behaviors regarding the function's name, to have the local fib be an unboxed reference to var"#fib#1", because a) this closes a fairly large hole in the language's ability to achieve performant locally-declared functions, and b) because it more closely mimics its behavior at global scope. From a usability perspective, these seem like more beneficial objectives than maintaining whatever "basic scope rule stuff" is currently implemented.

As it stands, within local scopes, named function syntax provides nothing of real use that anonymous function syntax doesn't already provide, and so if this situation is not improved, then it seems advisable that the use of named function syntax within local scopes should simply be deprecated, or at least discouraged, to avoid confusion and loss of performance (e.g., avoid multiple dispatch in favor of argument-type-dependent branches in order to avoid function reference boxing).

But let's return to happy thoughts, and entertain the idea of fixing the problem. I suppose the behavior I'm proposing could be summarized with this concept:

fibby = let
    function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
    function fib() fib = "I'm sure this behavior is desired, yes?" end
end

would be conceptually equivalent to (assuming gensym has generated the global identifier var"#fib#1", and assuming local const is valid):

function var"#fib#1" end
function var"#fib#1"(n)
    let fib = var"#fib#1"
        n ≤ 1 ? n : fib(n-1)+fib(n-2)
    end
end
function var"#fib#1"()
    let fib = var"#fib#1"
        fib = "I'm sure this behavior is desired, yes?"
    end
end

fibby = let
    local const fib = var"#fib#1"
end

(I'm being a little bit verbose for emphasis.) Namely, named function syntax would cause the function to treat its own identifier in a different way than how it treats other variables it has captured from its enclosing scope, so that it will behave as it would when it has been declared at global scope with no surprises.

Is this too tall an ask?

[uniment]

It looks like we get 95% of what we want here simply by inserting :(local $fun_name = var"#self#") into the beginning of named function definitions. It will, of course, be *nice* if the functions' identifiers in their parent scope become local consts too to achieve full consistency with the behavior at global scope, but that's not a prerequisite to solving the performance/type stability problem.

julia> using REPL, BenchmarkTools

julia> function zoomzoom!(ex) # harmless to insert into global fcns
          if ex isa Expr && ex.head ∈ (:function, :(=)) && ex.args[1] isa Expr && ex.args[1].head == :call
              pushfirst!(ex.args[2].args, :(local $(ex.args[1].args[1]) = var"#self#"))
          end
          ex isa Expr && map(zoomzoom!, ex.args)
          ex
      end
zoomzoom! (generic function with 1 method)

julia> pushfirst!(Base.active_repl_backend.ast_transforms, zoomzoom!); # ;-)

julia> fibby = let
          function fib(n) n ≤ 1 ? n : fib(n-1)+fib(n-2) end
          function fib()  fib = "I'm sure this behavior is desired, yes?" end
      end
(::var"#fib#1") (generic function with 2 methods)

julia> @btime $fibby(10) # fast like globally defined named fcn
 360.101 ns (0 allocations: 0 bytes)
55

julia> fibby()
"I'm sure this behavior is desired, yes?"

julia> fibby(10) # consistent w/ globally defined named fcn behavior
55

julia> @code_warntype fibby(10) # type-stable; notice local `fib`
MethodInstance for (::var"#fib#1")(::Int64)
 from (::var"#fib#1")(n) in Main at REPL[4]:2
Arguments
 #self#::Core.Const(var"#fib#1"())
 n::Int64
Locals
 fib::var"#fib#1"
Body::Int64
1 ─      (fib = #self#)
│   %2 = (n ≤ 1)::Bool
└──      goto #3 if not %2
2 ─      return n
3 ─ %5 = (n - 1)::Int64
│   %6 = (fib)(%5)::Int64
│   %7 = (n - 2)::Int64
│   %8 = (fib)(%7)::Int64
│   %9 = (%6 + %8)::Int64
└──      return %9

[vtjnash]

You do realize irony in claiming that you need it to be const, and for your example fix show assigning it values twice, right?

That measurement shows the benefit of inference, not the absence of boxing.

[uniment]

You do realize irony

Not really. I just want it to behave like it does when declared at global scope, in terms of performance and user interface, and this is how it behaves when it is declared at global scope.

[uniment]

This issue applies to @MasonProtter's StaticModules.jl and @mauro3's Parameters.jl as well:

julia> using BenchmarkTools, StaticModules, Parameters

julia> module Foo
           fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
       end
Main.Foo

julia> @btime Foo.fib(10)
  354.450 ns (0 allocations: 0 bytes)
55

julia> @const_staticmodule Bar begin
           fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
       end
StaticModule Bar containing
  fib = fib

julia> @btime Bar.fib(10)
  7.700 μs (0 allocations: 0 bytes)
55

julia> @with_kw struct BazType{F}
           fib::F = (fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2))
       end
BazType

julia> const Baz = BazType()
BazType{var"#fib#8"}
  fib: fib (function of type var"#fib#8")


julia> @btime Baz.fib(10)
  8.200 μs (0 allocations: 0 bytes)
55

Whereas @code_warntype shows Foo.fib(10) to be type-stable, Bar.fib(10) and Baz.fib(10) are not (despite property-access Bar.fib and Baz.fib being type-stable).

Testing shows the proposed partial fix solves these issues.

[MasonProtter]

This issue applies to @MasonProtter's StaticModules.jl and @mauro3's Parameters.jl as well:

Well, yeah of course it does. Both of those create a local scope, that's not new information and doesn't require new benchmarks.

[uniment]

This issue was mentioned in 44029:

The most common remaining case stems from inner
functions calling themselves.

[bb010g]

The actual notion it needs is that there is no use of fib between the syntactic definition of fib and the first usage of fib, so we should detect that it can be syntactically moved to the first usage point by extending the lifetime of the captured variables beyond their initial scope, and then doing some analysis trickiness around the internal usage of fib to detect that it will be the same as #self# at runtime (this is sort of like calling it const, but without all the fuzziness around what const means), allowing lowering to first do a transform to rewrite that usage to eliminate the dependency (I think that is known as the y-combinator pattern)

@vtjnash IIUC, this doesn't address the case of two mutually recursive local const functions, which can't have their body definitions syntactically ordered such that each will be after the function definition of what it references.

[uniment]

Closing in favor of #53295

[bb010g]

Given that #53295 was closed, maybe this issue should remain open to track the performance issue, which is different from the implementation of a specific strategy that addresses it.

[uniment]

@bb010g #53295 was reopened, so I'll leave this closed.

However, it might be good to open a new issue specific to your case of mutually-recursive local functions.

There are two sub-cases:

Case 1: Mutually-recursive singleton local functions (no captures except for each other): we can change references to each others' local name to reference their global names instead so they don't have to capture each other.

Example:

# this code:
let
    is_even(x) = x==0 ? true : is_odd(x-1)
    is_odd(x) = x==0 ? false : is_even(x-1)
end

# is currently approximately this:
struct var"#is_even#3"
    is_odd :: Core.Box
end
struct var"#is_odd#4"{T}
    is_even :: T
end
(var"#self#" :: var"#is_even#3")(x) = x==0 ? true : var"#self#".is_odd.contents(x-1)
(var"#self#" :: var"#is_odd#4")(x) = x==0 ? false : var"#self#".is_even(x-1)
let
    is_even = var"#is_even#3"(Core.Box())
    is_odd = var"#is_odd#4"(is_even)
    is_even.is_odd.contents = is_odd
end

# would become approximately this:
struct var"#is_even#3" end
struct var"#is_odd#4" end
(::var"#is_even#3")(x) = x==0 ? true : var"#is_odd#4"()(x-1)
(::var"#is_odd#4")(x) = x==0 ? false : var"#is_even#3"()(x-1)
let
    is_even = var"#is_even#3"()
    is_odd = var"#is_odd#4"()
end

Case 2: Mutually-recursive closures: mutually-recursive local functions that capture other values too must be closures and must capture each other; we can rearrange struct definitions so that they can capture each other in a type-stable manner, so long as they're declared one-after-the-other with no new captures introduced in between.

# this code:
let a=0, b=0
    is_even(x) = x==a ? true : is_odd(x-1)
    is_odd(x) = x==b ? false : is_even(x-1)
end

# is currently approximately this:
struct var"#is_even#3"{A}
    is_odd :: Core.Box
    a :: A
end
struct var"#is_odd#4"{T, B}
    is_even :: T
    b :: B
end
(var"#self#" :: var"#is_even#3")(x) = x==var"#self#".a ? true : var"#self#".is_odd.contents(x-1)
(var"#self#" :: var"#is_odd#4")(x) = x==var"#self#".b ? false : var"#self#".is_even(x-1)
let a=0, b=0
    is_even = var"#is_even#3"(Core.Box(), a)
    is_odd = var"#is_odd#4"(is_even, b)
    is_even.is_odd.contents = is_odd
end

# would become approximately this (notice struct def'ns in opposite order):
struct var"#is_odd#4"{T, B}
    is_even :: T
    b :: B
end
mutable struct var"#is_even#3"{B,A}
    const a :: A
    is_odd :: var"#is_odd#4"{var"#is_even#3"{B,A}, B}
    var"#is_even#3"{B}(a::A) where {B,A} = new{B,A}(a)
end
(var"#self#" :: var"#is_even#3")(x) = x==var"#self#".a ? true : var"#self#".is_odd(x-1)
(var"#self#" :: var"#is_odd#4")(x) = x==var"#self#".b ? false : var"#self#".is_even(x-1)
let a=0, b=0
    is_even = var"#is_even#3"{typeof(b)}(a)
    is_odd = var"#is_odd#4"(is_even, b)
    is_even.is_odd = is_odd
end

In this latter case where the closures must capture each other, an allocation must still occur. However, at least it is type-stable.

If the mutually-recursive local functions can be singleton as in Case 1, it is more performant to make them so.

(see discussion)