Core.tuple() warntype

[aviatesk]

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

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

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

[tomtom]

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!
however, even mymap3() also avoids warntype, somehow it’s much slower!!!

[Per]

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)))

[tomtom]

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

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)

[Per]

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.)

[tomtom]

… 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 quote … end ???

thanks!

[Per]

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

[tim.holy]

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.)

[tomtom]

Base uses the Any16 mechanism to explicitly “punt” on inferrable tuple manipulations for long tuples.

(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.

Because of compiler specialization, tuples aren’t really recommended for long “vectors.”

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

[Tamas_Papp]

(what does “punt” actually mean?)

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

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

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

[tomtom]

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

… 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”?

[tim.holy]

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.

[tomtom]

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.

[Tamas_Papp]

See

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

[tomtom]

I had read the doc but could not understand…

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.

[Tamas_Papp]

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.

[tomtom]

The discussion is getting away from your original question.

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

unless you work on the low-level parts of Base or the compiler.

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

[Tamas_Papp]

Just search for dicussions with examples, eg

When should we use `@nospecialize`?

The manual is sketchy about the use of @nospecialize (maybe it is still WIP?). I gather it is a necessary optimisation to avoid overburdening the dispatch tables. Is the end user advised to use this macro in some specific circumstance or coding pattern?

Very large compilation time (and space)

In a previous post, I mentioned a small interpreter that I wrote both in direct style and in continuation-passing style. In the first case, Julia very quickly compiles the interpreter methods as they are being used. In the second case, however, this process takes inordinate amounts of time even for trivial inputs and, for simple but non-trivial inputs, it does not even finish because it exhausts the memory (32 GB). Given the size of the interpreter, it was not practical to show it here so I tri…

[tomtom]

You risk filling up your code cache

what will happen once the code cached got filled up?
would it crash Julia?
Or, the cache would be reset? If it’s the case, the worst thing we get is (the time used in the) re-compilation of generated functions.

[Per]

Sorry, I wasn’t very clear. What I meant by “code cache” was the L1 instruction cache of the CPU. This might be something like 32 kilobytes, so if you code-generate a length-1000 tuple, and each element results in 32 bytes of code, then each time the function runs, all other functions will be pushed out of the cache.

Nothing will crash, all that will happen is that the next few function calls will take a few extra nanoseconds as instructions are fetched from the next level cache. The net effect is that your program runs slower even though @btime says that your function is faster.