Constants not propagated when taking a slice of a tuple

I wrote some functions that shifts tuples and run into the following:

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

Generally I find it hard to spot issues when type inference works in my mind but not work in julia. Can you shed some light on me ? Many Thanks.

It seems getindex(t::Tuple, r::AbstractUnitRange{<:Real}) is made type unstable on purpose to help compiler

Reverting back to the old definition makes it type stable.

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

julia> @code_typed shiftright1(1,2,3)
) => Tuple{Int64,Vararg{Int64,N} where N}

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

julia> @code_typed shiftright1(1,2,3)
1 ─ %1 = (Base.getfield)(xs, 3, true)::Int64
│   %2 = (Base.add_int)(0, 1)::Int64
│   %3 = (Base.getfield)(xs, %2, true)::Int64
│   %4 = (Base.add_int)(0, 2)::Int64
│   %5 = (Base.getfield)(xs, %4, true)::Int64
│   %6 = (Core.tuple)(%1, %3, %5)::Tuple{Int64,Int64,Int64}
└──      return %6
) => Tuple{Int64,Int64,Int64}

julia> VERSION
1 Like

Thank you! That’s very interesting. Would you elaborate on how type instability can help the compiler?

Well, the commit message says “remove a couple uses of ntuple to help the compiler” so I just copied the phrase. My guess is that it makes it impossible to infer the type so that compiler gives up early which in turn makes JIT completion time shorter.

That make sense. By the way how did you spot this issue? (By your amazing InteracticeCodeSearch.jl I guess?) Do you think it is possible to automatically scan up a call chain to detect where type instability happens?

I unmarked your answer as the solution so that this post can live longer:wink:

I just guessed xs[1:end-1] was the problematic part and then ran xs = (1, 2, 3); @edit xs[1:2]. It led me to the code using Vector which didn’t seem very nice for the type system so I ran git blame to find the commit.

(@search from InteractiveCodeSearch.jl actually does not work this case since it evaluates xs[1:2]. It would be nice to support this but @edit works perfectly fine so I’m not super motivated to fix this at the moment…)

I just read ?@code_typed and it turned out you can pass optimize=false to do:

julia> @code_typed optimize=false shiftright1(1,2,3)
1 ─ %1 = (Base.lastindex)(xs)::Const(3, false)
│   %2 = (Base.getindex)(xs, %1)::Int64
│   %3 = (Core.tuple)(%2)::Tuple{Int64}
│   %4 = (Base.lastindex)(xs)::Const(3, false)
│   %5 = (%4 - 1)::Const(2, false)
│   %6 = (1:%5)::Const(1:2, false)
│   %7 = (Base.getindex)(xs, %6)::Tuple{Vararg{Int64,N} where N}
│   %8 = (Core._apply)(Core.tuple, %3, %7)::Tuple{Int64,Vararg{Int64,N} where N}
└──      return %8
) => Tuple{Int64,Vararg{Int64,N} where N}

which tells you that the type instability happens at getindex. It only takes care of the “first level” of the call chain but I guess it can be handy.

1 Like

I think it would be very useful if slicing is type stable. I don’t know what’s the best way to get attention from core devs, though. Maybe move to “internals” category?

Thank you! That’s already way better than what I am doing now: calling methods and following calls in base/*.jl…

I will be a happy user from today on :smiley:

Issue filed.

1 Like

Thanks for filing the issue!

JeffBezanson suggested a butlast function. That indeed sounds nice. Even so as we already have Base.tail.

butlast(t::Tuple) = _butlast(t...)
_butlast(x1) = ()
_butlast(x1, xs...) = (x1, _butlast(xs...)...)

shiftright(xs...) = (xs[end], butlast(xs)...)
@code_typed shiftright(1,2,3)

We have one, just not in the right place :wink:

1 Like