Revisiting type stability

Type Stability is one of the most important concept in Julia but never properly defined. Instead, it is described with examples; most examples are similar to the following:

function t1(n)
  s = 0
  t = 1
  for i in 1:n
     s += s/i
     t = div(t, i)
  end
  return t
end

function t2(n)
  s  = 0.0
  t = 1
  for i in 1:n
     s += s/i
     t = div(t, i)
  end
  return t
end

where t1 is unstable and t2 is stable. The reason given is that s changes type. However, I managed to produce a type stable code but still changing s's type within. See the following

function t3(n)
  s = 0
  t = 1
  for i in 1:n
  s/i; s = 0.0
  t = div(t, i)
  end
  return t
end

Here s changes from Integer to Floating-point in the loop.

So how should we understand the type stability without relying on @code_native?

No that’s not the reason. The reason is the use of s in the loop could be of different types.

@code_native is never what you should use, especially not for type stability. Use @code_warntype instead.

2 Likes

And there’s basically no way to properly define it in an implementation independent way while still being useful. The proper definition should probably be that if in the program, the use of a variable in a specialization of the function could be of different types at runtime, then there’s type instability. However, this definition is basically undecidable so in practice, the useful definition is that if the compiler cannot figure out the leaf type of a use then there’s type instability. This is what @code_warntype shows you. Since it depend on what the compiler can do, I would not call it a “proper” definition, even though it is nonetheless the only useful one.

2 Likes

Hi @yuyichao, thanks for the reply. Could you also comment on my function t3 and explain why it is type stable (or not)?

Well if the definition is, what @code_warntype shows you, then it is not type stable. This is not a good definition if you e.g. want to build a mathematical paper on top of it. But as @yuyichao said its very practical. E.g. I only write @code_warntype-stable code in performance critical spots (at least in julia 0.6).

In this case it’s not type stable. However, since the operation that this insability is on is so trivial, together with the type inference union splitting and LLVM DCE there will end up not being any performance issue. This is a very unusual case though since most code won’t really write expressions that are not used.