Constants not propagated when taking a slice of a tuple

bug

#1

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.


#2

It seems getindex(t::Tuple, r::AbstractUnitRange{<:Real}) is made type unstable on purpose to help compiler https://github.com/JuliaLang/julia/commit/c3f3b489d5c7e3267c545fa1c42351643fb71b96

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)
CodeInfo(
...
) => 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)
CodeInfo(
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
v"1.1.0-DEV.865"

#3

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


#4

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.


#5

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?


#6

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


#7

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


#8

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?


#9

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.


#10

Thanks for filing the issue!


#11

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)

#12

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