Function for Tuple is Not Type-Stable

[kylincaster]

Dear all,

I found that the following function is not type-stable:

julia> test(x::NTuple{N, Any}) where {N} = x[1:2:end];
julia> x = (1, 2, 3, 1:4, 1:10)
(1, 2, 3, 1:4, 1:10)

julia> test(x)
(1, 3, 1:10)

julia> @code_warntype test(x)
MethodInstance for test(::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}})
  from test(x::Tuple{Vararg{Any, N}}) where N @ Main REPL[42]:1
Static Parameters
  N = 5
Arguments
  #self#::Core.Const(test)
  x::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}}
Body::Tuple
1 ─ %1 = Base.lastindex(x)::Core.Const(5)
│   %2 = (1:2:%1)::Core.Const(1:2:5)
│   %3 = Base.getindex(x, %2)::Tuple
└──      return %3

As seen above, the return type of %3 could be determined by the input types of the tuple. Ideally, the return type should be type-stable.

I have created the following function to produce a tuple of odd-numbered elements stably:

julia> @inline @generated function _filter(x::NTuple{N, Any}, ::Val{n}, f = i -> i) where {N, n}
    expr = Expr(:tuple)
    for i in 1:n:N
        Base.push!(expr.args, Expr(:ref, :x, i))
    end
    return :(f($expr))
end

julia> _filter(x, Val(2))
(1, 3, 1:10)

julia> @code_warntype _filter(x, Val(2))
MethodInstance for _filter(::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}}, ::Val{2})
  from _filter(x::Tuple{Vararg{Any, N}}, ::Val{n}) where {N, n} @ Main none:0
Static Parameters
  N = 5
  n = 2
Arguments
  #self#::Core.Const(_filter)
  x::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}}
  @_3::Core.Const(Val{2}())
Locals
  #2::var"#2#3"
Body::Tuple{Int64, Int64, UnitRange{Int64}}
1 ─      nothing
│        (#2 = %new(Main.:(var"#2#3")))
│   %3 = #2::Core.Const(var"#2#3"())
│   %4 = (#self#)(x, @_3, %3)::Tuple{Int64, Int64, UnitRange{Int64}}
└──      return %4

With this approach, the return type is stable, as shown above. If we want to know the total number of elements in the tuple for all odd elements, we can obtain 12 as follows:

julia> _filter(x, Val(2), i -> mapreduce(Base.length, +, i; init = 0))
12

However, the number of n is still hard-coded in the _filter function. The issue arises when we want to create a function that handles an arbitrary number n. Currently, I could only define a function to handle the tuple with a definite length:

julia> function filterF(x::NTuple{5, Any}, n::Integer, f = i->i, default = 0) # where {5}
	n <= 0 && return default
	n >= 5 && return _filter(x, Val(5), f)
	n == 4 && return _filter(x, Val(4), f)
	n == 3 && return _filter(x, Val(3), f)
	n == 2 && return _filter(x, Val(2), f)
	n == 1 && return _filter(x, Val(1), f)
end

julia> filterF(x, 3)
(1, 1:4)

julia> filterF(x, i -> mapreduce(Base.length, +, i; init = 0))
5

However, I cannot generalize such a definition as function oddF(x::NTuple{N, Any}, n::Integer, f = i -> i, default = 0) where {N} for arbitrary tuple lengths. This is because N in such a function definition is treated as a TypeVar rather than an Integer like in C++ templates.

I tried the following function, but it still failed:

julia> function _filter_loop(x::NTuple{N, Any}, ::Val{X}, n, f = i->i, default = 0) where {N, X}
	n >= X && return _filter(x, Val(X), f)
	return n <= 0 ? default : _filter_loop(x, Val(X-1), n, f, default)
end

julia> @code_warntype _filter_loop(x, Val(5), 2, i -> mapreduce(Base.length, +, i; init = 0))
MethodInstance for _filter_loop(::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}}, ::Val{5}, ::Int64, ::var"#12#13")
  from _filter_loop(x::Tuple{Vararg{Any, N}}, ::Val{X}, n, f) where {N, X} @ Main REPL[5]:1
Static Parameters
  N = 5
  X = 5
Arguments
  #self#::Core.Const(_filter_loop)
  x::Tuple{Int64, Int64, Int64, UnitRange{Int64}, UnitRange{Int64}}
  @_3::Core.Const(Val{5}())
  n::Int64
  f::Core.Const(var"#12#13"())
Body::Any
1 ─ %1 = (#self#)(x, @_3, n, f, 0)::Any
└──      return %1

How can we make filterF work for any N without hard-coding? Is there a more elegant solution?

Thank you for your assistance.

---

[Seelengrab]

Type instabilities in general are not a bug - in some cases they are unavoidable. In the case of test, it's because the getindex call iterates over the tuple, resulting in mixed types for the iteration variable (Int64 and UnitRange{Int64}). Type inference is allowed to "give up" and fall back to inferring Any, so that's what's happening in this case.

---

Please direct usage questions to the discourse forum, the #helpdesk channel on Slack or one of the other platforms mentioned on the community tab of the julialang.org website.

[nsajko]

In x[1:2:end], the step size 2 isn't in the type domain, so this can't be type stable for heterogeneous tuples.