Type unstable function returning a tuple

I think you’re getting your point across, but I’m not. Both getindex and ntuple take integers as input, but ntuple also takes integers wrapped in Val. They both make equal amounts of ‘sense’ as far as I can tell, but implementing this (efficiently) for arrays is probably pretty different challenge.

ntuple has a special implementation for Val inputs, so as far as I understand, the type instability did disappear because of “Val magic”. You can see that from the function

fun(v, n) = ntuple(i -> sum(v[1]), n)

where the type instability comes or goes depending on whether you write fun(v, 4) or fun(v, Val(4)).

No. This means Julia is compiling a specialized version of ntuple for every possible Val and the problem that caused type-instability is only inside ntuple so the function barrier is already present and provided by the Base but apparently not documented. If people knew ntuple already takes Val values directly then they would not need to wrap a function barrier around ntuple. Also, if it is not documented, I would not rely on it to not break in Julia minor or patch version changes, it is not part of the public API.

Isn’t that what you refer to as “Val magic”? Now I don’t understand what we are disagreeing about.

Ok, magic clearly is a vague term.

What I mean is that there is nothing special about Val (i.e., the compiler has no mention to it coded inside it, it is literally struct Val{x}; end in the Base) and, therefore, the way Val solves the type-instability could be replicated by any structure you yourself created, it only needs to encode the tuple size in type space. (This is different, for example, of Array that is hard/impossible to replicate without using Array internally, and that is not implemented in Julia itself.)

Also, you do not need ntuple to take a Val, you could wrap ntuple in a function that takes a Val and unwrap the value back to a number before passing to ntuple and this could also solve the type-unstability (or instead unwraping Val, unwraping any alternative you use).

The only magic here, which I don’t like, is that ntuple does not document that it may also take a Val as second parameter (which as I said, is not strictly necessary to deal with type-instability), what is probably a implementation detail being leaked and that should not be relied on.

The source code that defines the Val ntuple is:

# inferrable ntuple (enough for bootstrapping)
ntuple(f, ::Val{0}) = ()
ntuple(f, ::Val{1}) = (@_inline_meta; (f(1),))
ntuple(f, ::Val{2}) = (@_inline_meta; (f(1), f(2)))
ntuple(f, ::Val{3}) = (@_inline_meta; (f(1), f(2), f(3)))

@inline function ntuple(f::F, ::Val{N}) where {F,N}
    N::Int
    (N >= 0) || throw(ArgumentError(string("tuple length should be ≥ 0, got ", N)))
    if @generated
        quote
            @nexprs $N i -> t_i = f(i)
            @ncall $N tuple t
        end     
    else    
        Tuple(f(i) for i = 1:N)
    end     
end

and the non-val ntuple is:

function ntuple(f::F, n::Integer) where F
    t = n == 0  ? () :
        n == 1  ? (f(1),) :
        n == 2  ? (f(1), f(2)) :
        n == 3  ? (f(1), f(2), f(3)) :
        n == 4  ? (f(1), f(2), f(3), f(4)) :
        n == 5  ? (f(1), f(2), f(3), f(4), f(5)) :
        n == 6  ? (f(1), f(2), f(3), f(4), f(5), f(6)) :
        n == 7  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7)) :
        n == 8  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8)) :
        n == 9  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9)) :
        n == 10 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9), f(10)) :
        _ntuple(f, n)
    return t
end

How? As far as I can see from all the examples, the type instability only disappears when ntuple receives a Val. Except the example by @cstjean, which I suspect just unrolls the tuple construction the same way that ntuple(.., Val) does.

I would be interested in seeing an example of that, but it does not seem to be present in this thread.

function my_ntuple(f, ::Val{N}) where {N}
    N::Int;
    return ntuple(f, N);
end
julia> @code_warntype my_ntuple(x -> x * 2, Val(2))

Variables
  #self#::Core.Compiler.Const(my_ntuple, false)
  f::Core.Compiler.Const(var"#7#8"(), false)
  #unused#::Core.Compiler.Const(Val{2}(), false)

Body::Tuple{Int64,Int64}
1 ─      Core.typeassert($(Expr(:static_parameter, 1)), Main.Int)
│   %2 = Main.ntuple(f, $(Expr(:static_parameter, 1)))::Core.Compiler.Const((2, 4), false)
└──      return %2

Or yet:

julia> struct Two; end
julia> function my_ntuple(f, ::Two) = ntuple(f, 2); end
julia> @code_warntype my_ntuple(x -> x * 2, Two())
Variables
  #self#::Core.Compiler.Const(my_ntuple, false)
  f::Core.Compiler.Const(var"#11#12"(), false)
  #unused#::Core.Compiler.Const(Two(), false)

Body::Tuple{Int64,Int64}
1 ─ %1 = Main.ntuple(f, 2)::Core.Compiler.Const((2, 4), false)
└──      return %1


What am I doing wrong here:

julia> using BenchmarkTools

julia> v = [rand(4)];

julia> fun(v, n) = ntuple(i -> sum(v[1]), n);

julia> function my_ntuple(f, ::Val{N}) where {N}
           N::Int;
           return ntuple(f, N);
       end
my_ntuple (generic function with 1 method)

julia> fun1(v, n) = my_ntuple(i -> sum(v[1]), n);

julia> @btime fun($v, Val(4));  # only this seems to be actually type-stable
  17.782 ns (0 allocations: 0 bytes)

julia> @btime fun1($v, Val(4));
  23.662 ns (1 allocation: 48 bytes)

julia> @btime fun($v, 4);
  23.590 ns (1 allocation: 48 bytes)

Similarly here:

julia> struct Two; end

julia> my_ntuple(f, ::Two) = ntuple(f, 2);

julia> @btime fun1($v, Two());  # still allocating
  18.609 ns (1 allocation: 32 bytes)

Trying this as well:

julia> two = Two()
Two()

julia> @btime fun1($v, $two);
  18.622 ns (1 allocation: 32 bytes)

Thanks everyone for the feedback :slight_smile:
So the problem seems to be coming from “constant propagation” (as @CameronBieganek suspected) and calling ntuple with Val is in fact the method to use in this case.

Ok, I am bit puzzled here, the @code_lowered of both is basically the same.

julia> @code_lowered fun(v, Val(4))
CodeInfo(
1 ─ %1 = Main.:(var"#3#4")
│   %2 = Core.typeof(v)
│   %3 = Core.apply_type(%1, %2)
│        #3 = %new(%3, v)
│   %5 = #3
│   %6 = Main.ntuple(%5, n)
└──      return %6
)

julia> @code_lowered fun1(v, Val(4))
CodeInfo(
1 ─ %1 = Main.:(var"#5#6")
│   %2 = Core.typeof(v)
│   %3 = Core.apply_type(%1, %2)
│        #5 = %new(%3, v)
│   %5 = #5
│   %6 = Main.my_ntuple(%5, n)
└──      return %6
)

But the @code_typed is vastly different:

julia> @code_typed fun1(v, Val(4))
CodeInfo(
1 ─ %1 = %new(var"#5#6"{Array{Array{Float64,1},1}}, v)::var"#5#6"{Array{Array{Float64,1},1}}
│   %2 = invoke Main.ntuple(%1::var"#5#6"{Array{Array{Float64,1},1}}, 4::Int64)::Tuple{Vararg{Float64,N} where N}
└──      return %2
) => Tuple{Vararg{Float64,N} where N}

julia> @code_typed fun(v, Val(4))
CodeInfo(
1 ── %1   = Base.arrayref(true, v, 1)::Array{Float64,1}
│    %2   = Base.identity::typeof(identity)
│    %3   = Base.add_sum::typeof(Base.add_sum)
│    %4   = Base.arraysize(%1, 1)::Int64
│    %5   = Base.slt_int(%4, 0)::Bool
│    %6   = Base.ifelse(%5, 0, %4)::Int64
│    %7   = Base.sub_int(%6, 0)::Int64
...

It seems to me that the compiler just gave up on the inference/inlining, but I may be wrong. I am almost sure type-inference is not a guarantee of the language and it may become better or worse (or both in different cases) with each Julia version released. I am using Julia 1.4.2, for reference.

As, @Birgorneau said, it may be a problem of “constant propagation”, however, I am not sure if these methods should be used if they are not documented. Opening a PR would be most wise.

however, I am not sure if these methods should be used if they are not documented. Opening a PR would be most wise.

Sounds like a good idea! In fact, on a different branch of Julia it is documented:

"""
    ntuple(f, ::Val{N})
Create a tuple of length `N`, computing each element as `f(i)`,
where `i` is the index of the element. By taking a `Val(N)`
argument, it is possible that this version of ntuple may
generate more efficient code than the version taking the
length as an integer. But `ntuple(f, N)` is preferable to
`ntuple(f, Val(N))` in cases where `N` cannot be determined
at compile time.
# Examples
julia> ntuple(i -> 2*i, Val(4))
(2, 4, 6, 8)
"""
@inline function ntuple(f::F, ::Val{N}) where {F,N}
    N::Int
    (N >= 0) || throw(ArgumentError(string("tuple length should be ≥ 0, got ", N)))
    if @generated
        quote
            @nexprs $N i -> t_i = f(i)
            @ncall $N tuple t
        end
    else
        Tuple(f(i) for i = 1:N)
    end
end
1 Like

Which branch? It is possible someone already did the work, it just is not in the last release yet.

I just checked on Master

Oh, okay, then someone was faster than us and already solved the problem. Great. There should probably be safe to use ntuple receiving a Val since the first Julia version in which it works up to before Julia 2.0 (in which anything may break).

Here’s the PR for the new ntuple docstring:

https://github.com/JuliaLang/julia/pull/32468

3 Likes