Type instability when slicing tuples

[cnliao]

The following change seems to introduce type instability when slicing tuples, which is sometimes not desired. (identified by @tkf )

julia/base/range.jl

Line 197 in c3f3b48

function getindex(t::Tuple, r::AbstractUnitRange{<:Real})

MWE:

shiftleft(x1, xs...) = (xs..., x1) # (1,2,3) -> (2,3,1)
shiftright1(xs...) = (xs[end], xs[1:end-1]...) # (1,2,3) -> (3,1,2)
shiftright2(xs...) = (xs[end], reverse(Base.tail(reverse(xs)))...) # awkward, right?
@code_typed shiftleft(1,2,3) # infers fine
@code_typed shiftright1(1,2,3) # julia fails to decide the number of elements returned.
@code_typed shiftright2(1,2,3) # infers fine

See also discussion on discourse.

[tkf]

Here is the relevant commit by @JeffBezanson c3f3b48 included in PR #27634

[JeffBezanson]

Did this infer before that commit? The compiler generally doesn't know the values inside a range. For xs[1:end-1] it would be better to add a butlast function.

[tkf]

It seems so?

julia> f(xs) = xs[1:end-1]
f (generic function with 1 method)

julia> @inferred f((1, 2, 3))
ERROR: return type Tuple{Int64,Int64} does not match inferred return type Tuple{Vararg{Int64,N} where N}
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] top-level scope at none:0

julia> Base.getindex(t::Tuple, r::AbstractUnitRange{<:Real}) =
           (o = first(r) - 1; ntuple(n -> t[o + n], length(r)))

julia> @inferred f((1, 2, 3))
(1, 2)

julia> VERSION
v"1.1.0-DEV.865"

[KristofferC]

const propagation seems to handle it:

julia> @code_typed optimize=false f((1, 2, 3))
CodeInfo(
1 ─ %1 = (Base.lastindex)(xs)::Const(3, false)
│   %2 = (%1 - 1)::Const(2, false)
│   %3 = (1:%2)::Const(1:2, false)
│   %4 = (Base.getindex)(xs, %3)::Tuple{Int64,Int64}
└──      return %4
) => Tuple{Int64,Int64}

[JeffBezanson]

Well, that's impressive I guess :) However it was not inferrable in 0.6, 0.7, or 1.0 (or any other prior version). I changed this because it was a compiler performance hot spot. So any change to make this inferrable needs to show minimal compile-time cost.

[timholy]

Try using the Any16 mechanism to limit the array-based implementation to large tuples.

[bramtayl]

I think there’s still the case when you might slice by truly variable indices, in which case attempting to infer this will lead to slowdowns even in the <16 case

[timholy]

True, though before special-casing this in inference it might be worth seeing how bad it is. I'd be a bit surprised if it's common. Jeff, were you just looking at the compilation of julia itself or some other compiler-performance test?

Also noticed above:

For xs[1:end-1] it would be better to add a butlast function.

This already exists and is currently called Base.front. (Can't use head since that refers to a singleton.)