When does the Julia compiler step in

[Sukera]

@HashBrown

What about when the code is type stable and a method inside is surely to be called. Why not just compile that too while you are at it and put the appropriate address to jump to (do it recursively)? Basically go as far as you can until you hit a type instability or a point at which you are not sure whether or not the function will even be called?

That is exactly what happens in completely type stable code, yes. Your original type stable example just didn’t have a top level call to go into - it was all in global scope. The first function call was foo, so it only gets compiled then.

@HashBrown

Separately, if the code in the for loop is type stable and the function foo has been generated already, is there a lookup to find where the generated code for foo is or whether or not it exists? Or do we just jump straight to the code?

Yes and Yes. You can do methods(f) to query the methods of a function, and one of those methods has a field specializations to check which specializations exist for that method. While you can manually call these, it’s not necessary - the compiler will already insert the appropriate call to the code (or inline it entirely, based on some heuristics).

@HashBrown

For the stable version I imagine an if statement checking if its the first iteration. If so lookup the type in the table. It returns memory address or null (potentially compiled by a different part of the code). If null call back to compiler to generate code. Call to compiler returns a memory address to where it put the code. Store that locally and in the table. Jump to it. In future iterations just jump straight to the address you stored locally without performing lookups.

Does that seem to capture the general gist at a conceptual level?

Conceptually, yes, though it’s not implemented that way.

Again, this lookup only happens only because you’re in global scope in the first place. In global scope, you could in theory have some other code in a background task eval new methods or overwrite an existing method, which would require that new foo to be called in your globally scoped loop.

In regards to inlining & already compiling called functions in local scope (i.e. inside a function), take these for example:

f(x) = x^3
g(x) = 2*f(x)
h(x) = g(x)/4

If we just look at @code_warntype, we still see the call:

julia> @code_warntype h(1)
MethodInstance for h(::Int64)
  from h(x)
     @ Main REPL[3]:1
Arguments
  #self#::Core.Const(h)
  x::Int64
Body::Float64
1 ─ %1 = Main.g(x)::Int64
│   %2 = (%1 / 4)::Float64
└──      return %2

But that’s only because @code_warntype is a very high level view. If we already take a look at the generated LLVM IR, we can see that both g and f got inlined:

julia> @code_llvm h(1)
;  @ REPL[3]:1 within `h`
define double @julia_h_359(i64 signext %0) #0 {
top:
; ┌ @ REPL[2]:1 within `g`
; │┌ @ REPL[1]:1 within `f`
; ││┌ @ intfuncs.jl:320 within `literal_pow`
; │││┌ @ operators.jl:580 within `*` @ int.jl:88
      %1 = shl i64 %0, 1
      %2 = mul i64 %1, %0
; │└└└
; │┌ @ int.jl:88 within `*`
    %3 = mul i64 %2, %0
; └└
; ┌ @ int.jl:97 within `/`
; │┌ @ float.jl:269 within `float`
; ││┌ @ float.jl:243 within `AbstractFloat`
; │││┌ @ float.jl:146 within `Float64`
      %4 = sitofp i64 %3 to double
; │└└└
; │ @ int.jl:97 within `/` @ float.jl:386
   %5 = fmul double %4, 2.500000e-01
; └
  ret double %5
}

The inlining is of course not guaranteed, but it generally is reliable that type stable code does get compiled all the way through. That’s why it’s important to keep code type stable.

Of course, some operations are inherently type unstable, like parsing. Colloquially speaking, “parsing” is always a map of some String or Vector{UInt8} to some type T that’s more specific than Any. Since the parsing can return any of the subtypes of Any though, it’s an inherently type unstable operation that will fall back to Any in the worst case (or some abstract type in a better case).

I should note that eval does not affect function calls in local scope - the results of an eval are only “visible” to existing functions once they return to global scope. The mechanism this is tracked by is called “world age”, which is a sort of advanced topic that’s not really relevant for regular development. Suffice it to say that it’s the core mechanism that allows julia to compile type stable calls to native machine code, while still staying semantically dynamic.