Core.tuple() warntype

I’m studying Tuples and find that (in base/tuple.jl) a lot of methods to create them (e.g. map(), NTuple{}(), etc.) at the end would return something like (x..., ), which calls Core.tuple().

However, I found that this call gives warntype as below:

julia> a = collect(1:16);

julia> f() = (a..., )
f (generic function with 3 methods)

julia> @code_warntype f()
Variables
  #self#::Core.Compiler.Const(f, false)
Body::Tuple
1 ─ %1 = Core._apply(Core.tuple, Main.a)::Tuple
└──      return %1

and seems like Core.tupe() is so basic that could not be inspected:

julia> @code_warntype tuple(a)
ERROR: ArgumentError: argument is not a generic function
julia> @edit tuple(a)
ERROR: ArgumentError: argument is not a generic function

so, how could we create a tuple without any warntype? Thanks.

a is a non-constant global variable, so there’s no way it can be inferred. It’s also a vector, so the length of the resulting tuple isn’t known by the compiler. Fixing those issues solves the problem:

julia> const b = (1, 2, 3)
(1, 2, 3)

julia> f() = (b...,)
f (generic function with 1 method)

julia> @code_warntype f()
Variables
  #self#::Core.Compiler.Const(f, false)

Body::Tuple{Int64,Int64,Int64}
1 ─ %1 = Core._apply(Core.tuple, Main.b)::Core.Compiler.Const((1, 2, 3), false)
└──      return %1
3 Likes

what about this?

julia> const nt16 = (1:16..., )
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)

julia> @code_warntype map(x -> x + 1, nt16)
Variables
...
  @_6::Union{Nothing, Tuple{Int64,Int64}}
Body::Tuple
...
4 ┄ %20 = Core._apply(Core.tuple, A)::Tuple
└──       return %20

now even I define mymap(), it still gives warntype:

function mymap(f, t::NTuple{N, T} ) where {T, N}
    A = Vector{T}(undef, N)    # A now is Vector{T} rather than Vector{Any}
    for i=1:N
        A[i] = f(t[i])
    end
    (A..., )           # warntype
    # NTuple{N, T}(A)  # also warntype
end

julia> @code_warntype mymap(x -> x + 1, nt16)
Variables
...
  @_5::Union{Nothing, Tuple{Int64,Int64}}
Body::Tuple{Vararg{Int64,N} where N}
...
4 ┄ %19 = Core._apply(Core.tuple, A)::Tuple{Vararg{Int64,N} where N}
└──       return %19

For getting inferred return type of builtin functions, you can check

Core.Compiler.return_type(Core.tuple, Tuple{Int, Int}) # => Tuple{Int64, Int64}
1 Like

the problem now is calling (a..., ) inside a function would give warntype when a is a Vector (NOT a Tuple). It happens inside map() (see base\tuple.jl line 186).

using a SizedVector instead of a Vector, and using StaticArrays.Tuple() instead of Core.tuple() would avoid warntype:

using StaticArrays
function mymap2(f, t::Base.All16{T, N} ) where {T, N}
    N_ = 16 + N
    A = SizedVector{N_, T}(undef)
    for i=1:N_
        A[i] = f(t[i])
    end
    # (A..., )    # warntype
    Tuple(A)      # NO warntype
end

julia> const nt1000 = (1:1000..., );
julia> @code_warntype mymap2(x -> x + 1, nt1000);  # NO warntype

okay, now I’m thinking ways of avoiding whatever vector: to use recursion of recursions like:

mymap3(f, t::Tuple{})              = ()                           # same as map()
mymap3(f, t::Tuple{Any,})          = (f(t[1]),)                   # same as map()
mymap3(f, t::Tuple{Any, Any})      = (f(t[1]), f(t[2]))           # same as map()
mymap3(f, t::Tuple{Any, Any, Any}) = (f(t[1]), f(t[2]), f(t[3]))  # same as map()
mymap3(f, t::Tuple) = (Base.@_inline_meta; (f(t[1] ), mymap3(f,Base.tail(t) )... ) )

argheadtail(x1, x2, x3, x4,
            x5, x6, x7, x8,
            x9, x10, x11, x12,
            x13, x14, x15,
            rest...) = ((x1, x2, x3, x4,
                         x5, x6, x7, x8,
                         x9, x10, x11, x12,
                         x13, x14, x15),
                         rest)
headtail(x::Tuple) = argheadtail(x...)
mymap3(f, t::Base.All16) = (Base.@_inline_meta; 
                            (head, tail) = headtail(t);
                            (mymap3(f, head)..., mymap3(f, tail)... ) )


julia> map(x->x+1,nt1000)===mymap2(x->x+1,nt1000)===mymap3(x->x+1,nt1000)
true
julia> @code_warntype mymap3(x -> x + 1, nt1000);   # NO warntype

finally, mymap3() avoids any warntype.

now, check the performance:

julia> @btime map(x -> x + 1, $nt1000);      # Vector & Core.tuple()
  25.667 μs (494 allocations: 39.34 KiB)

julia> @btime mymap2(x -> x + 1, $nt1000);   # SizedVector & Tuple()
  1.413 μs (1 allocation: 7.94 KiB)

julia> @btime mymap3(x -> x + 1, $nt1000);   # recursion of recursions
  2.118 ms (50195 allocations: 2.59 MiB)

mymap2() has no warntype and is much faster! :grinning:
however, even mymap3() also avoids warntype, somehow it’s much slower!!!

If you’re looking for maximum compilation effort to minimize runtime, then how about:

mymap4(f, t::Tuple) = ntuple(i -> f(t[i]), Val(length(t)))
2 Likes

wow! thanks! mymap4() has no warntype and is the fastest so far: :grinning:

julia> @btime map(x -> x + 1, $nt1000);
  25.183 μs (494 allocations: 39.34 KiB)

julia> @btime mymap2(x -> x + 1, $nt1000);
  1.390 μs (1 allocation: 7.94 KiB)

julia> @btime mymap3(x -> x + 1, $nt1000);
  2.118 ms (50195 allocations: 2.59 MiB)

julia> @btime mymap4(x -> x + 1, $nt1000);
  575.929 ns (0 allocations: 0 bytes)

Yes, but note that it ends up in a generated function, so using it on a length-1000 tuple is probably not a good idea in practice. (You risk filling up your code cache.)

… I have difficulty in understanding what is a “generated function”?

actually, I came across with ntuple(, ::Val) and could not understand. Below is the definition from base\ntuple.jl line 45:

@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

could you be nice enough to teach me:

  1. what is if @generated ??? how could a macro used after if, also, nothing after @generated?
  2. what do the codes mean inside quoteend ???

thanks!

That’s an “optionally generated function.” It’s explained here: https://docs.julialang.org/en/v1/manual/metaprogramming/#Generated-functions-1 (last section)

2 Likes

Because of compiler specialization, tuples aren’t really recommended for long “vectors.” StaticArrays.jl explicitly warns you against using it for large arrays, and Base uses the Any16 mechanism to explicitly “punt” on inferrable tuple manipulations for long tuples. It can be fun to play around with this stuff but in real life I would recommend against going beyond the Any16 limit unless you really know what you are doing. (For example, if very much Julia code did such manipulations on very long tuples, you could easily increase our current “time to first plot” by orders of magnitude.)

2 Likes

(what does “punt” actually mean?)
In the context of map() at least, I don’t think that the introduction of Any16 was intended to “discourage” the use of long tuples. Rather, it’s essential to avoid stack overflow caused by deep recursions.

That said, if we omit the method function map(f, t::Any16) ... end and rely solely on the recursion map(f, t::Tuple) = (@_inline_meta; (f(t[1]), map(f,tail(t))...)), stack overflow will throw when a long tuple (say, 2000 elements) is used.

That’s why I had an attempt mymap3() that breaks a single deep recursions into multiple shallow recursions. It’s slow though.

why? and how? could I know more in depth about this issue? thanks.

http://www.catb.org/~esr/jargon/html/P/punt.html

Mostly because a specialized version would be compiled for every length, which is usually not what you want.

1 Like

… I don’t understand… actually Julia is always compiling a specialized version for each (combination) of type variables … now, if we treat the length as a (static) type variable also, it’s just the usual case… what’s exceptional then?

of course, if the program is manipulating a lot of tuples with all different lengths, that may be a problem. But then it’s a problem of “number of different lengths”, not the problem of “long length”?

The point being that with the constructs you’re playing with here, “long length” leads directly to “many different lengths.” Most tuple algorithms are written recursively.

2 Likes

help?> @nospecialize
@nospecialize
Applied to a function argument name, hints to the compiler that the method should not be specialized for different types of that argument, but instead to use precisely the declared type for each argument.

please help… I could not understand what the above says… could anyone help to give some examples? thanks.

See

https://docs.julialang.org/en/v1/devdocs/functions/#Compiler-efficiency-issues-1

I had read the doc but could not understand… :cry: :tired_face:

to be precise, what the difference if the original definition:

length(@nospecialize t::Tuple) = nfields(t)

being replaced by:

length(t::Tuple) = nfields(t)

?

thanks.

Generally, @nospecialize will prevent producing a compiled version for each tuple type. Though for this particular function, I believe it is mostly inlined anyway in practice.

The discussion is getting away from your original question. While knowing about @nospecialize is useful for advanced users of Julia, I am not sure that getting deep into the internals is useful, unless you work on the low-level parts of Base or the compiler.

IMO 99% of Julia users can make productive use of the language without every using @nospecialize.

Not at all, as we’ve discussed that using long tuples would introduce a lot of methods each for a different length of tuple.

That’s what I’m trying hard to do. So I went into base\tuple.jl and found a lot of @nospecialize, which seems to be related to the generation of the method table.

so… could you be nice enough to give an example that show the difference between using vs. not using @nospecialize? many thanks :dizzy_face: