Type instability of nested recursive function

General Usage Performance
1

I was writing some code where I need an inner function to be recursive, something like (highly simplified)

function f1(x::Vector{Int64})
    function g(i, val)
        i <= length(x) || return
        g(i + 1, val)
        x[i] = val
    end
    g(1, 1)
    x
end

And when I ran it with @code_warntype I was surprised to see a Core.Box:

Arguments
  #self#::Core.Const(f1)
  x::Vector{Int64}
Locals
  g@_3::Core.Box
  g@_4::Union{}
  g@_5::Union{}
Body::Vector{Int64}
1 ─       (g@_3 = Core.Box())
│   %2  = Main.:(var"#g#17")::Core.Const(var"#g#17")
│   %3  = Core.typeof(x)::Core.Const(Vector{Int64})
│   %4  = Core.apply_type(%2, %3)::Core.Const(var"#g#17"{Vector{Int64}})
│   %5  = %new(%4, x, g@_3)::var"#g#17"{Vector{Int64}}
│         Core.setfield!(g@_3, :contents, %5)
│   %7  = Core.isdefined(g@_3, :contents)::Bool
└──       goto #3 if not %7
2 ─       goto #4
3 ─       Core.NewvarNode(:(g@_5))
└──       g@_5
4 ┄ %12 = Core.getfield(g@_3, :contents)::Any
│         (%12)(1, 1)
└──       return x

From the message it appears that the type instability is caused by g trying to capture g itself in its defining environment. This causes a self-referential type to be created and confuses the compiler.

My temporary solution is to use

function f2(x::Vector{Int64})
    function h(i, val, self)
        i <= length(x) || return
        self(i + 1, val, self)
        x[i] = val
    end
    h(1, 1, h)
    x
end

then h would not need to capture itself. This does prevents some memory allocations, but I am unsure if this is the fastest way.

Is there a better way to work around this issue? (while keeping the recursion. In the actual code it is very difficult to convert the recursion into a loop)

2

Is there a reason you need the closure over x? This looks like it would do the same thing, and is type-stable.

function f1(x::Vector{Int64})
    g!(x, 1, 1)
    return x
end

function g!(x, i, val)
    if i > length(x)
        g!(x, i + 1, val)
        x[i] = val
    end
    return nothing
end

@code_warntype f1([1,2,3])
MethodInstance for f1(::Vector{Int64})
  from f1(x::Vector{Int64}) in Main at REPL[22]:1
Arguments
  #self#::Core.Const(f1)
  x::Vector{Int64}
Body::Vector{Int64}
1 ─     Main.g!(x, 1, 1)
└──     return x

@code_warntype g!([1,2,3],1,1)
MethodInstance for g!(::Vector{Int64}, ::Int64, ::Int64)
  from g!(x, i, val) in Main at REPL[23]:1
Arguments
  #self#::Core.Const(g!)
  x::Vector{Int64}
  i::Int64
  val::Int64
Body::Nothing
1 ─ %1 = Main.length(x)::Int64
│   %2 = (i > %1)::Bool
└──      goto #3 if not %2
2 ─ %4 = (i + 1)::Int64
│        Main.g!(x, %4, val)
└──      Base.setindex!(x, val, i)
3 ┄      return Main.nothing
1 Like
3

Thanks! This approach does work, but the actual g in my code uses 5 bindings from the outer function, so moving the inner function outsides would add a lot of arguments.

4

while it may look ugly perhaps @inline g!(.... will make sure it adds no overhead

5

You can always use a NamedTuple to pack everything together and then unpack the value in inner function. A macro can automate this approach.

1 Like