Why doesn't the compiler infer the type of this function?

General Usage
1

On Julia v1.2.0:

fib1(n::Int64) = n<=1 ? (1,) : (n, fib1(n-1)...)
run1() = fib1(5)

fib2(::Type{Val{n}}) where {n} = n<=1 ? (1,) : (n, fib2(Val{n-1})...)
run2() = fib2(Val{5})

julia> @code_warntype run1()
Variables
  #self#::Core.Compiler.Const(run1, false)

Body::Tuple{Int64,Vararg{Int64,N} where N}
1 ─ %1 = Main.fib1(5)::Core.Compiler.PartialStruct(Tuple{Int64,Vararg{Int64,N} where N}, Any[Core.Compiler.Const(5, false), Vararg{Int64,N} where N])
└──      return %1

julia> @code_warntype run2()
Variables
  #self#::Core.Compiler.Const(run2, false)

Body::NTuple{5,Int64}
1 ─ %1 = Core.apply_type(Main.Val, 5)::Core.Compiler.Const(Val{5}, false)
│   %2 = Main.fib2(%1)::Core.Compiler.Const((5, 4, 3, 2, 1), false)
└──      return %2

I had gotten the impression that the Val{n} idiom is no longer necessary since the compiler can now do constant propagation. So I am surprised that the return type of fib1(5) is not inferred, especially since 5 is (AFAIK) well below the tuple length limit for inference.

2

Constant propagation doesn’t happen on recursion I think.

1 Like
3

I think it’s more that this is a case of a growing tuple. Inference is willing to do it if you have a shrinking or constant-length tuple:

fib1a(::Tuple{Int}) = (1,)
fib1a(t::TT) where TT<:Tuple = (length(t), fib1a(Base.tail(t))...)
run1a() = fib1a(ntuple(i->1, 5))

This is all part of the heuristics used to avoid getting stuck in an infinite inference loop, which I think look something like this:

  • if inference can prove that it will converge, then do it. (Even when it would converge, its attempt to prove so works only some of the time due to the halting problem.) The case of a shrinking tuple or one that has one operation per element is a case where it can be certain that it will converge.
  • if inference can’t prove it, go a little ways down the rabbit hole (e.g., up to tuples of length 2 or so)
  • bail

@benninkrs, hopefully you’re doing this only on small tuples; if not, it’s pretty murderous on the compiler and will lead to long inference times (aka, “time to first [whatever]” will be unpleasant).

1 Like
4

While true, I think what I said is still correct. You are writing

function run1a()
    tmp = ntuple(i->1, 5)
    fib1a(tmp)
end

and the constant propagation on the 5 does not need to recurse here. From the tuple you are then back to “type” recursion where your example does apply. Just to make a super simple example:

julia> f(n) = n == 0 ? 1 : 1 + f(n-1);

julia> g() = f(5)
g (generic function with 1 method)

If constant propagation would go through recursion this should give g() = 6 (but it doesn’t). But perhaps the argument there is that going from n to n-1 is not a simplification so constant propagation stops.

5

Thanks for the explanation. I understand that inference has its limitations, but I thought my example would be pretty easy for the compiler to infer.

This issue came up as part of a module I’m writing for high-dimensional array manipulation. The problem I ran into is that size and the functions I need to use from TensorOperations use tuples, but to do the dimension mangling I need either (1) a mutable data structure, such as a Vector or MVector, in which case the cost of converting between tuples and vectors becomes significant; or (2) to dissect and reassemble multiple tuples, in which case the cost of constructing tuples becomes significant. This led me to explore how quickly tuples can be constructed and how much inference can help, and then to the example above.

It would be a topic for another thread (such as this one), but I find myself wishing there was such a thing as super fast mutable tuples.

6 
julia> Base.setindex((1, 2, 6), 2, 3)
(1, 2, 2)
3 Likes
7

Very interesting. I was not aware of base.setindex. It appears to be very fast for small tuples at least; I need to do a little more experimenting.

Since my previous post, I learned that for my use case it is actually quite expedient to make an MVector out of the tuple, do the manipulations, then convert the result back to a tuple. It turns out the extra cost I was seeing had little to do with creating tuples per se or converting to and from MVector, but was mainly associated with returning tuples whose length could not be inferred. I’ve found some curious behavior regarding that, but that’s probably a topic for another thread.

I thank both of you for your thoughtful replies.

1 Like