Length of varargs not inferred from type signature

[nalimilan]

I've tried to find information about how varargs are supposed to be handled with regard to specialized compilation and inlining (e.g. #4374), but I still don't know much. IIUC, it seems that vararg functions are compiled for each type signature so that they are as efficient as manually writing several functions, which is why e.g. sum() was rewritten with only one varags definition here: #4751.

If I'm correct, then it seems that the fact that the length of the varargs is not correctly inferred. This matters for me as it incurs a major performance penalty when indexing arrays with tuples of the same length as the varargs. See this discussion and the link to the gist: https://groups.google.com/d/topic/julia-users/o310JmWd7kg/discussion

Here's an illustration:

julia> fun(x::Int...) = length(x)
fun (generic function with 1 method)

julia> code_typed(fun, (Int,))
1-element Array{Any,1}:
 :($(Expr(:lambda, {:(x::top(apply_type)(Vararg,Int))}, {{},{{:x,(Int64,),0}},{}}, quote  # none, line 1:
        return tuplelen(x::(Int64,))::Int64
    end)))

I would have thought that this would be return 1, since tuplelen(x::(Int64,)) can obviously only be 1 due to the type assertion.

[JeffBezanson]

Yes, I suppose we could inline the tuplelen to the value 1. But this does not necessarily limit the compiler's understanding of the length of the tuple. For example

function foo(is...)
    a = rand(4,4)
    a[is...]
end

julia> code_typed(foo,(Int,Int))
1-element Array{Any,1}:
 :($(Expr(:lambda, {:(is::top(apply_type)(Vararg,Any))}, {{:a},{{:is,(Int64,Int64),0},{:a,Array{Float64,2},18}},{}}, quote  # none, line 2:
        a = $(GetfieldNode(Base.Random,:dsfmt_gv_fill_array_close_open!,Any))(top(ccall)(:jl_new_array,$(Array{Float64,2}),$((Any,Any)),$(Array{Float64,2}),0,$(Expr(:call1, :(top(tuple)), 4, 4))::(Int64,Int64),0)::Array{Float64,2})::Array{Float64,2} # line 3:
        return arrayref(a::Array{Float64,2},top(tupleref)(is::(Int64,Int64),1)::Int64,top(tupleref)(is::(Int64,Int64),2)::Int64)::Float64
    end)))

As you can see, the code is lowered to the equivalent of indexing a with 2 arguments.
In general the compiler infers types, not values; 1 is not a type. The length of a tuple is kept implicit in the tuple itself. In some cases code generation does the transformation you want:

function bar()
    t = (1,)
    length(t)
end

julia> code_llvm(bar,())

; Function Attrs: sspreq
define internal i64 @julia_bar() #2 {
top:
  ret i64 1, !dbg !561
}

But we do need to improve codegen of varargs functions; right now it can be quite bad.

The length of the result of ntuple is hard to infer, as this code demonstrates:

    n = rand(1:10)
    t = ntuple(n, i->0)

Clearly the length of t cannot be statically inferred.

I think the code in the gist demonstrates the general problems we have with writing code to manipulate N-dimensional things, which has always been difficult. Maybe there is a way to write this in the form A[vecs...] += 1 where each element of vecs is an index vector, to take advantage of the N-d iteration implemented inside indexing, until we have a better solution.

[JeffBezanson]

closed in favor of #5402

[nalimilan]

OK, thanks. Does that mean that when #5402 is fixed, doing something of the form A[vecs...] += 1 will not trigger memory allocation, i.e. be as fast as indexing when you know the number of dimensions? Until then the code for frequency tables can probably leave with the current performance hit, it's not that terrible.

Also, could you elaborate on that? I don't understand what you mean.

Maybe there is a way to write this in the form A[vecs...] += 1 where each element of vecs is an index vector, to take advantage of the N-d iteration implemented inside indexing, until we have a better solution.