Why are generated functions (maybe) impossible to statically compile?

Internals & Design
1

I’m finally getting around to understanding generated functions, and the first paragraph under Optionally-generated functions raises a couple questions for me. I’ll repost the text here as it’s not too long:

Generated functions can achieve high efficiency at run time, but come with a compile time cost: a new function body must be generated for every combination of concrete argument types. Typically, Julia is able to compile “generic” versions of functions that will work for any arguments, but with generated functions this is impossible. This means that programs making heavy use of generated functions might be impossible to statically compile.

  1. The smaller question: “compile generic versions…for any arguments” refers to generic function definitions, right? Because the compiled code is usually specific for concrete argument types.

  2. Why would generating new function bodies be an issue for static compilation? It seems equivalent to manually writing new function definitions for different concrete argument types, and couldn’t those also be precompiled the same way a generic function can be? Sure, no runtime compilation means you can’t throw new concrete argument types at runtime into a generated function, but that limitation is also true for generic functions. Or am I misunderstanding what “static compilation” means here?

2 Likes
2

My sense is that generated functions are bandaid. A better solution is to use Val or some other way of moving the argument values into the type domain which can be dispatched upon.

1 Like
3

Generated functions seem unrelated to value-based dispatch, no? And if they’re a bandaid, they’re a bandaid with muscle.

4

As far as I know, using an @generated function in statically compiled code is perfectly fine if the input types are statically known. The part that doesn’t work for static compilation is “generate new function bodies” during dynamic dispatch, since static compilation (by definition) doesn’t include dynamic generation of code (i.e., there’s no eval, and no codegen at all). This is the same case for regular dynamic dispatch that would require code specialization & compilation at runtime.

You can in theory still have dynamic dispatch with just the runtime & without codegen, as long as the specialization you end up calling has already been compiled ahead of time.

You still need to do that with cases of @generated that are more than just ensuring you have some value available as a constant to encourage the compiler to propagate that constant. As an example of where you need @generated:

julia> using Base.Cartesian: @ntuple

julia> @generated function foo(x::Val{N}) where N
           return quote
               @ntuple $N i -> "This is a compile time constant with interpolated $i"
           end
       end
foo (generic function with 1 method)

julia> @code_warntype foo(Val(2))
MethodInstance for foo(::Val{2})
  from foo(x::Val{N}) where N @ Main REPL[4]:1
Static Parameters
  N = 2
Arguments
  #self#::Core.Const(foo)
  x::Core.Const(Val{2}())
Body::Tuple{String, String}
1 ─ %1 = Base.string("This is a compile time constant with interpolated ", 1)::String
│   %2 = Base.string("This is a compile time constant with interpolated ", 2)::String
│   %3 = Core.tuple(%1, %2)::Tuple{String, String}
└──      return %3

You can’t interpolate that N into @ntuple, due to @ntuple working on an expression and needs a literal value, which you can only get here with an @generated function. Compare this to a version without @generated, which needs optimizations turned on to eliminate the anonymous function:

julia> function bar(x::Val{N}) where N
           return ntuple(i -> "This is a runtime value with interpolated $i", x)
       end
bar (generic function with 1 method)

julia> @code_warntype bar(Val(2))
MethodInstance for bar(::Val{2})
  from bar(x::Val{N}) where N @ Main REPL[6]:1
Static Parameters
  N = 2
Arguments
  #self#::Core.Const(bar)
  x::Core.Const(Val{2}())
Locals
  #4::var"#4#5"
Body::Tuple{String, String}
1 ─      (#4 = %new(Main.:(var"#4#5")))
│   %2 = #4::Core.Const(var"#4#5"())
│   %3 = Main.ntuple(%2, x)::Tuple{String, String}
└──      return %3


julia> @code_warntype optimize=true bar(Val(2))
MethodInstance for bar(::Val{2})
  from bar(x::Val{N}) where N @ Main REPL[6]:1
Static Parameters
  N = 2
Arguments
  #self#::Core.Const(bar)
  x::Core.Const(Val{2}())
Locals
  #4::var"#4#5"
Body::Tuple{String, String}
1 ─ %1 = invoke Base.print_to_string("This is a runtime value with interpolated "::String, 1::Vararg{Any})::String
│   %2 = invoke Base.print_to_string("This is a runtime value with interpolated "::String, 2::Vararg{Any})::String
│   %3 = Core.tuple(%1, %2)::Tuple{String, String}
└──      return %3

This is just an example of course since there’s an almost-equivalent to @ntuple in ntuple, but since the two work at different levels of the compilation stack (an AST transform vs. a maybe-not-applied compiler optimization), the former can give semantic guarantees that the latter can’t. There’s bound to be examples that are a bit more complicated than this where the constant propagation fails, while interpolating into the expression directly still works.

1 Like
5

Yes, I think so. Static compilation means you create a binary executable from Julia (this is rarely done right now, in practice, because of the limitations in Julia for doing this). In this case you don’t have the compiler available, so if you hit a new set of types at runtime for your generated function it can’t be compiled and no generic implementation is possible. In contrast, a normal function can have a generic implementation available at runtime.

2 Likes
6

These seem about what I interpreted static compilation as.

But that’s only with Function/Type/VarArgs/@nospecialize arguments, right? Otherwise (and usually), a generic function must also be JAOT-compiled for each set of concrete argument types. Basically what Sukera said in more detail in their first paragraph.

7

My understanding is that if types are unknown at static compile time a dynamic version of a function can be generated. This isn’t possible with @generated.

8

That’s news to me - an @generated function goes through dispatch just the same, the only conceptual difference is that the source code that’s compiled per tuple of argument types may be entirely different.

9

That’s what I understand the following to mean:

a new function body must be generated for every combination of concrete argument types

There are no generic generated functions.

10

Been a while since I looked into internals, but iirc the dynamic compiled code (e.g. unknown argument types are designated Any) dynamically dispatches to compiled code with concrete argument types. If the latter does not yet exist, the former triggers JIT/JAOT compilation of the latter. I didn’t check generated functions then.

11

Sure there are, that’s what “optionally @generated” functions are. I.e., those with a block like this:

if @generated
    # generated stuff
else
    # generic fallback
end

All of this goes through the same dispatch machinery, the only conceptual special case for @generated is that the source code can change per argument type as well, not just the compiled specialization as with regular dispatch.

1 Like
12

I certainly haven’t looked at the internals. The documentation seems wrong to me (or poorly worded) if what you and @Benny say is true. Am I mistaken?

13

I don’t think anything we’ve said contradicts the documentation :thinking: Do you have a link to the section you think says otherwise?

1 Like
14

I’m referring to the quoted documentation in the OP. As written that section seems to imply that only generated functions require concrete types to avoid issues at runtime (without a JIT).

Typically, Julia is able to compile “generic” versions of functions that will work for any arguments, but with generated functions this is impossible.

15

No, that’s not what it says, though I can see why you think that. When a method is dispatched to, we ALWAYS know the concrete type of the given object, because objects ALWAYS have a concrete type. They never have an abstract type. This concrete type is then used in the @generated function. What the section refers to is that sometimes, julia doesn’t compile a specialized method for a concrete argument (e.g. if it’s @nospecialize or one of these apply). In contrast, @generated always specializes for the given argument types. The function is still generic (in the sense that new specializations can be compiled per argument type), but you can’t ever fall back to a version that ignores the argument types (i.e. doesn’t specialize). The only way to do that is with the if @generated escape hatch.

For example, this function is @generated and generic:

julia> @generated function foo(::T) where T
           :(T)
       end
foo (generic function with 1 method)

julia> foo(1)
Int64

julia> foo(.20)
Float64

julia> foo("soo")
String

julia> @code_warntype foo("foo")
MethodInstance for foo(::String)
  from foo(::T) where T @ Main REPL[1]:1
Static Parameters
  T = String
Arguments
  #self#::Core.Const(foo)
  _::String
Body::Type{String}
1 ─     return $(Expr(:static_parameter, 1))


julia> @code_warntype foo(1)
MethodInstance for foo(::Int64)
  from foo(::T) where T @ Main REPL[1]:1
Static Parameters
  T = Int64
Arguments
  #self#::Core.Const(foo)
  _::Int64
Body::Type{Int64}
1 ─     return $(Expr(:static_parameter, 1))
1 Like
16

This sort of implementation detail should be documented in one place with a warning that it’s subject to lots of change. It’s hard to pick up this stuff from scattered unintuitive places like the Performance Tips section you linked. Or at least that section should also mention this bit about @generated functions.

Concrete types are always available at runtime, maybe you mean inferable concrete types at compile-time. Based on this discussion, that section also misled me into thinking @generated functions had some issue generic functions did not, but it’s both an issue with dynamic dispatch requiring further compilation.

17

I’m sorry, this has all left me more confused than when I started commenting here.

Maybe it’s useful to clarify what I mean. I don’t mean that the concrete types aren’t available at run time.

My understanding is that when compiling a normal function, if the types have are inferable, a generic version of said function that calls into dynamic dispatch can be generated; thus, there are no issues at runtime for normal functions, because dynamic dispatch resolves any methods (at runtime) to be called inside that function.

This is not possible with a generated function; there is no generic machine code because you need source code that changes as a function of the (unknown-at-compile-time) types to generate that machine code.

What am I getting wrong here?

2 Likes
18

Maybe I’m misunderstanding you completely, but I think your definitions are backwards. When the argument types to a function call are inferrable to concrete types, the compiler doesn’t generate a generic version, it generates a specialized version, just for those argument types, while compiling the outer function that’s calling this one. If, on the other hand, the types are not inferrable, the compiler instead inserts dynamic dispatch, which checks the actual concrete types the objects have at runtime, and only compiles that specialization once that codepath is actually hit, instead of ahead of time.

All we’re talking about is that this second part of dynamic dispatch at runtime is impossible in static compilation, but that’s orthogonal to whether the called function is @generated or not. No matter whether it’s @generated, type inference still runs for the code inside that function, even if it comes from an @generated function.

You can still end up with dynamic dispatch in the code that’s put out by @generated, if that code is itself not type stable.

1 Like
19

That sounds mostly right to me, the need to generate a function body is the compile time cost the docs says.

Maybe an example helps explain the disconnect? Let’s say we have a type_unstable_foo(i) = inner_bar(one( global_Type_dict[i] )) method, and we call type_unstable_foo(3). The native code for type_unstable_foo(::Int) must dynamically dispatch inner_bar. The JIT compiler must be ready to compile new native code for inner_bar, whether it is @generated or not.

I think maybe the disconnect is you were thinking there’s a generic native code for inner_bar, but there’s one for type_unstable_foo.

It wouldn’t make a difference if type_unstable_foo were @generated, type_unstable_foo(::Int) would behave the same way, just with a different function body from type_unstable_foo(::Float64).