Function specialization for tuple arguments?

[timholy]

Functions receiving a tuple argument do not appear to be specialized for the tuple-of-types:

function sumindexes_tuple(I)
    I1 = I[1]
    I2 = I[2]
    s = 0
    for i2 in I2
        for i1 in I1
            s += i1*i2
        end
    end
    s
end

function sumindexes_direct(I1, I2)
    s = 0
    for i2 in I2
        for i1 in I1
            s += i1*i2
        end
    end
    s
end

I1 = 1:1000
I2 = 1:1:1001
I = (I1, I2)

Benchmark (after one run to compile):

julia> @time sumindexes_tuple(I)
elapsed time: 0.312181922 seconds (79722592 bytes allocated)
251001250500

julia> @time sumindexes_direct(I...)
elapsed time: 0.001694039 seconds (64 bytes allocated)
251001250500

Not sure whether this is a TODO, a bug, or a deliberate design decision, but I thought it was worth bringing to attention.

Interestingly, this doesn't apply for a type defined by a tuple-of-types:

module TupleWrapper

export TWrap

type TWrap{I<:(Any...,)}
    t::I
end

TWrap(t::(Any...,)) = TWrap{typeof(t)}(t)

TWrap(args...) = TWrap(args)

end

IW = TupleWrapper.TWrap(I1,I2)

function sumindexes_tuplewrapper(I::TupleWrapper.TWrap)
    I1 = I.t[1]
    I2 = I.t[2]
    s = 0
    for i2 in I2
        for i1 in I1
            s += i1*i2
        end
    end
    s
end

julia> @time sumindexes_tuplewrapper(IW)
elapsed time: 0.001751796 seconds (64 bytes allocated)
251001250500

One place this comes up in practice if you write a copy! function to work between two regions of two arrays, e.g., copy!(dest::Array, destindexes, src::Array, srcindexes). In such cases you lose information if you try to write it with ... notation.

[JeffBezanson]

For now a workaround for this is to use a static parameter:

function sumindexes_tuple2{T}(I::T)
    ...

This will force specialization.

The problem with tuple types is that there are too many of them (O(n^k)).

[timholy]

I wondered if combinatorial explosion was the issue.

Your tip was a huge help, many thanks.

[simonster]

I ran into this today, and I can't help but wonder if this behavior could be refined. Consider:

julia> f(x) = length(x) == 1 ? x[1] : x;

julia> g() = f((1, 2));

julia> g()
(1,2)

It seems like we perform type inference for f((Int, Int)) but only compile/execute f(Tuple). Perhaps it makes sense to generate a specialized method for tuple types for which we have performed type inference? We'd still avoid specialization explosion for cases like f(tuple(x::Vector{Any}...)) and unless code gen is substantially slower than type inference there shouldn't be a big impact on compilation time.

[memeplex]

@JeffBezanson your paper states that the heuristic is "[to] avoid specializing methods for tuple types of every length". Does this mean that specializations are indeed generated for prefixes of the tuple of types up to some fixed limit k?