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

**URL:** <https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366>\
**Category:** Internals & Design\
**Created:** [March 20, 2023, 11:08pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366 "2023-03-20T23:08:12Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 20, 2023, 11:08pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/1 "2023-03-20T23:08:12Z")

</div>

I’m finally getting around to understanding generated functions, and the first paragraph under [Optionally-generated functions](https://docs.julialang.org/en/v1/manual/metaprogramming/#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?

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [March 21, 2023, 7:20am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/2 "2023-03-21T07:20:57Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![uniment](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/uniment/32/24532_2.png) [@uniment](https://discourse.julialang.org/u/uniment)\
**Post date:** [March 21, 2023, 7:58am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/3 "2023-03-21T07:58:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 21, 2023, 8:50am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/4 "2023-03-21T08:50:14Z")

</div>

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.

> [@mkitti](#):
>
> 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.

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
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
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.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 21, 2023, 11:50am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/5 "2023-03-21T11:50:11Z")

</div>

> [@Benny](#):
>
> Or am I misunderstanding what “static compilation” means here?

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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 21, 2023, 10:47pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/6 "2023-03-21T22:47:15Z")

</div>

These seem about what I interpreted static compilation as.

> [@haberdashPI](#):
>
> In contrast, a normal function can have a generic implementation available at runtime.

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.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 23, 2023, 11:51am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/7 "2023-03-23T11:51:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 23, 2023, 12:58pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/8 "2023-03-23T12:58:50Z")

</div>

> [@haberdashPI](#):
>
> This isn’t possible with @generated.

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.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 23, 2023, 3:33pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/9 "2023-03-23T15:33:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 23, 2023, 8:27pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/10 "2023-03-23T20:27:49Z")

</div>

> [@haberdashPI](#):
>
> if types are unknown at static compile time a dynamic version of a function can be generated. This isn’t possible with @generated.

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.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 23, 2023, 8:36pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/11 "2023-03-23T20:36:02Z")

</div>

> [@haberdashPI](#):
>
> There are no generic generated functions.

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 24, 2023, 11:44am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/12 "2023-03-24T11:44:25Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 24, 2023, 11:46am UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/13 "2023-03-24T11:46:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 24, 2023, 6:38pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/14 "2023-03-24T18:38:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 24, 2023, 6:43pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/15 "2023-03-24T18:43:18Z")

</div>

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](https://docs.julialang.org/en/v1/manual/performance-tips/#Be-aware-of-when-Julia-avoids-specializing) 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
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))

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 24, 2023, 10:04pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/16 "2023-03-24T22:04:30Z")

</div>

> [@Sukera](#):
>
> sometimes, julia doesn’t compile a specialized method for a concrete argument (e.g. if it’s `@nospecialize` or one of [these](https://docs.julialang.org/en/v1/manual/performance-tips/#Be-aware-of-when-Julia-avoids-specializing) apply). In contrast, `@generated` _always_ specializes for the given argument types.

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.

> [@haberdashPI](#):
>
> As written that section seems to imply that only generated functions _require_ concrete types to avoid issues at runtime (without a JIT).

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.

> [@Sukera](#):
>
> 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.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [March 25, 2023, 8:41pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/17 "2023-03-25T20:41:05Z")

</div>

> [@Benny](#):
>
> but it’s both an issue with dynamic dispatch requiring further compilation.

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?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [March 25, 2023, 10:25pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/18 "2023-03-25T22:25:44Z")

</div>

> [@haberdashPI](#):
>
> 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.

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.

> [@haberdashPI](#):
>
> 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?

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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [March 25, 2023, 10:27pm UTC](https://discourse.julialang.org/t/why-are-generated-functions-maybe-impossible-to-statically-compile/96366/19 "2023-03-25T22:27:04Z")

</div>

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)`.