Recursive closures/inner functions -- how to avoid boxing?

Consider code like

julia> function outer()
       function inner()
       false && inner()
       end
       inner
       end

julia> typeof(outer()).types
svec(Core.Box)

So this kind of code creates a box for the local variable inner which is captured by inner itself, because it is needed in the method body of inner().

Alas, I see no obvious way of using let blocks to avoid the boxing.

So my questions are:

  1. is this kind of boxing semantically necessary?
  2. is this a recent lowering bug?
  3. is there a nice trick to avoid the boxing?
  4. is this a missing point in Performance Tips · The Julia Language ?

If this was my own personal code, I wouldn’t particularly care and just use an explicit callable struct. But that is inappropriate for shared projects (drive-by-fixes on github are nice, drive-by-refactorings are obnoxious).

An example in the wild is julia/base/file.jl at 9b1ea1a880e1c47ebdc549a12fca288b5cc60013 · JuliaLang/julia · GitHub where the local variable _walkdir is boxed due to the reentrency of the _walkdir method body.

Apologies if I failed to find prior discussions on that – I’d also appreciate a pointer.

You could do:

julia> function outer2()
       function inner(_inner)
       false && _inner()
       end
       () -> inner(inner)
       end

This doesn’t seem to have boxes anywhere but tbh I am not quite sure how to check thoroughly:

julia> typeof(outer2()).types
svec(var"#inner#3")

julia> typeof(outer2()).types[1]
var"#inner#3"

julia> typeof(outer2()).types[1].types
svec()

@uniment was on quite the crusade against this issue a while ago, and there’s some issues and discussions all over the place here on Discourse and Github about it from that era.

Here’s some breadcrumbs if you want to explore (a subset of) the discussion that happened back then:

One hacky trick you can use here is var"#self#" to refer to the function itself, i.e.

julia> function outer()
           function inner()
               false && var"#self#"()
           end
           inner
       end
outer (generic function with 1 method)

julia> typeof(outer()).types
svec()

julia> @btime outer()()
  1.082 ns (0 allocations: 0 bytes)
false

This is not a particularly good idea though, and I would not recommend doing it in general. The PR I mention in "A Tragedy of Julia’s Type System" - #36 by Mason should be able to fix this issue as well.

2 Likes

Why?

That seems like a perfectly workable suggestion that should go into the official performance tips and be used everywhere, like e.g. in Base / walkdir?

There’s no reason to be ashamed of compiler limitations, we just need to be honest about them (instead of cosplaying “temporarily embarrassed millionaire”).

If lowering is currently, and for the last 8 years, too dumb to unbox recursive closures that are referred by name, then var"#self#" has been the idiomatic way of writing recursive inner functions for the last 8 years, full stop.

Also, big thanks, TIL!

It’s a bad idea because

  1. it’s an interal implementation detail that may not be stable
  2. it’s a very easy to hit sharp edges and ‘surprising’ behaviour with it.

For instance, consider

function outer()
    function inner()
        [var"self"() for i in 1:10]
    end
end

or

function outer()
    function inner()
        t = @spawn var"#self#"()
    end
end

One could very easily be forgiven for thinking that in both of those cases that the var"#self#"'s refer to inner but in fact, they refer to inner closures sneakily created by the list comprehension and the @spawn macro respectively, in ways that are semi-opaque to the user.

This makes it a massive potential footgun to go around referring to var"#self#" unless you deeply understand the exact details of what lexical scope you are calling it from.

2 Likes

Ok, var"#self#" has some sharp edges. And if it’s not officially supported (i.e. not guaranteed to work and have same semantics until 2.0) then it’s not really an option anyways.

Compiler limitations and capability shape the language.

For example, inductive range check elimination completely reshaped when @inbounds is appropriate.

Given today’s compiler, what is today’s idiomatic way of expressing Base.walkdir (linked above)?

Is it “don’t do recursive inner functions, use an explicit callable struct”?

That is something we should

  1. explain in the performance tips
  2. apply to walkdir in Base/file.jl etc (what’s good for the goose is good for the gander)

The easiest way is to just pass the function to itself. Instead of the walkdir example, I’ll show fib:

julia> let
           # Create a local function _fib whose first argument is a function fib
           function _fib(fib, n) 
               if n <= 1
                   return n
               else
                   # inside _fib, we recurse using fib, *not* _fib
                   fib(fib, n-1) + fib(fib, n-2)
               end
           end
           # now create a new local function fib that calls _fib(_fib, n)
           fib(n) = _fib(_fib, n)
       end
(::var"#fib#18"{var"#_fib#17"}) (generic function with 1 method)

julia> @btime $ans(10)
  212.570 ns (0 allocations: 0 bytes)
55

I showed a macro in Performant Recursive Anonymous Functions - #17 by Mason that automates this process:

using ExprTools: splitdef, combinedef
using MacroTools: postwalk, @capture

"""
This is only worth using for locally scoped recursive functions.
"""
macro fast_recursion(fdef)
    d = splitdef(fdef)
    name = get!(d, :name, gensym(:f))
    fargs = copy(get!(d, :args, []))
    fkwargs = get!(d, :kwargs, [])
    _name = gensym(name)
    __name = gensym(Symbol(:_, name))
    d[:body] = postwalk(d[:body]) do ex
        if @capture(ex, f_(args__))
            if f == name
                return :($__name($__name, $(args...),))
            end
        elseif @capture(ex, f(args__; kwargs__))
            if f == name
                return :($__name($__name, $(args...); $(kwargs...),))
            end
        end
        ex
    end
    d[:name] = _name
    d[:args] = pushfirst!(d[:args], __name)
    quote
        $(combinedef(d))
        $name($(fargs...); $(fkwargs...),) = $_name($_name, $(fargs...); $(fkwargs...),)
    end |> esc
end

and then we see

julia> @btime let
           fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
           fib(10)
       end
  2.620 μs (2 allocations: 32 bytes)
55

julia> @btime let
           @fast_recursion fib(n) = n ≤ 1 ? n : fib(n-1) + fib(n-2)
           fib(10)
       end
  212.815 ns (0 allocations: 0 bytes)
55

Docs to improve walkdir and the performance tips would be a great idea!

And if someone wants to put @fast_recursion into a little package and register it, you’d certainly have my blessing (as with any code code I post here or other julia help channels)

2 Likes