docs: FAQ's definition of type stability differs from that in code_warntyped

[ulysses4ever]

(Sorry for sending an empty body first)

FAQ says:

[type stable] means that the type of the output is predictable from the types of the inputs

While code_warntyped manual:

The ASTs are annotated in such a way as to cause "non-leaf" types to be emphasized (if color is available, displayed in red). This serves as a warning of potential type instability.

What is the right interpretation of type stability: all intermediate forms have concrete types or only output is concrete?

[timholy]

They're really the same thing; "intermediates are poorly-inferred" means that whatever they called didn't have concretely-inferrable output. If the output is nevertheless concretely inferred, it means the final result type didn't depend on knowing the result of each intermediate (either due to a type annotation or specifics of the internal code logic).

[ulysses4ever]

I'm sorry, I don't quite follow. Do you agree that the two definitions are different? (As in: I can have a method with concrete output but with some abstract intermediaries). Wouldn't it be better to have a single definition throughout the docs?

I probably should mention: we want to formalize this notion for an academic paper and are curious what is the right definition from Julia developer's point of view. We had the one from code_warntyped in mind all along and were quite surprised to find the one from FAQ. And we do think they are different definitions. I can provide a concrete example if that'll help.

[Moelf]

I think what Tim is saying is that you can think of @code_warntype as just applying the definition in FAQ for intermediate variables as well. If you think of something that is type-unstable as saying something "contains type-unstable parts" , it should be clear to see they are talking about the same thing just @code_warntype tells you how to understand its output.

[kimikage]

If I were to compensate for the sentence in the FAQ, it would be:

It means that the type of output "can be predicted by the compiler" from the type of input.

First, there is a gap between the theoretical predictability and the predictability for the compiler implementation.
The gap is caused mainly by the complexity of branching, which causes the compiler to abandon type inference. Closing the gap is not always the right thing to do, as compile time and memory consumption are also important performance indicators.

Secondly, I think the explanation of the case with "non-leaf" input types is context-dependent.

julia> f(x) = x
f (generic function with 1 method)

julia> code_warntype(f, (Integer,))
Variables
  #self#::Core.Compiler.Const(f, false)
  x::**Integer**

Body::**Integer**
1 ─     return x

If the input is boxed, the output type cannot be determined without looking at the "value" inside the box, so strictly speaking, I don't think the methods like f(x) above are type stable. In fact, code_warntype will warn you about that.

On the other hand, I think that in many cases we don't consider methods like f(x) to be "type instable". One reason is that implicitly we know how the method will be used. Another reason is that this is not a source in the propagation of type instability issue.

How it should be defined in the paper also depends on the subject matter, I think.

(BTW, it's not "in red" now. The documentation needs to be updated.)

[julbinb]

My impression is that the only point of telling users about type stability (whatever that is) is to help them write more efficient code. And a good way of achieving efficiency is the ability to generate code where everything is unboxed, not only the output.

In that sense, code_warntype seems to be a more accurate predictor of efficiency than the definition of type stability from FAQ. It is true that "all intermediates are concretely typed" implies type stability, but, as mentioned above, if intermediates don't directly affect the type of the output, a function would be considered type stable even if not all the intermediates are concretely typed.

If this reasoning is correct, the definition of type stability from FAQ seems to be a bit misleading.

On the other hand (related to the @kimikage's example), sometimes it is impossible to eliminate boxing even if all the arguments are concretely typed, e.g. in

myfirst(xs :: Vector{T} where T) = xs[1]

the output type may be abstract even though the argument xs is concrete, but it's not a problem and there is nothing the user can do to improve the performance of the function. In this case, the definition of type stability makes more sense than code_warntype.

[elextr]

My 2c worth:

@ulysses4ever the FAQ provides a description (not a formal definition) of "type instability" to allow a warning of its potential negative performance effects.

Whereas code_warntype is a tool which applies the heuristic that non-leaf types indicate potential type instability and shows where they occur. That isn't a guarantee that type instability based performance problems will occur or that they are avoidable, its a warning to check.

To me the purposes of each are different and the fact they use differing words for the same thing (as @timholy noted) reflects this.

[ulysses4ever]

Thanks everyone for participating in this thread. We wrote up an academic
paper about type stability (presented at OOPSLA '21):
https://a-pelenitsyn.github.io/Projects/stability/ The discussion here was very
useful during the writing.

Here's what we do in the paper.

1. We distinguish between type stability (concrete output type can be computed
   from a concrete input) and another property, deemed type groundedness, that
   follows what code_warntyped shows, i.e.: a method instance is type grounded
   if all slots of it are concrete.

2. We build a simple model of the Julia JIT that allows us two connect:

   • type stability to groundedness: grounded methods can only call stable ones;

   • groudedness to optimizations: grounded methods will be fully
     devirtualized (by our model of JIT).

3. We perform a corpus analysis of the 1K most-starred Julia packages to find
   how much methods in them appear stable and grounded. For that we run their
   test suites and inspect the resulting instances. On average, a Julia package
   from this dataset has 74% of methods stable and 57% grounded.

If you are curious, take a look at the paper, watch a 15 mins video about it,
or play with the artifact (more links are here). At this point, I think the issue can be closed.