# How to explain recursive generation of method instances for non-concrete types

**URL:** <https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020>\
**Category:** Internals & Design\
**Created:** [April 28, 2023, 4:15am UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020 "2023-04-28T04:15:41Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![JohnnyChen94](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/johnnychen94/32/29979_2.png) [@JohnnyChen94](https://discourse.julialang.org/u/JohnnyChen94)\
**Post date:** [April 28, 2023, 4:15am UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020/1 "2023-04-28T04:15:41Z")

</div>

I’m trying to understand under what circumstances Julia would trigger a compilation for “bad” Julia codes, so I use MethodAnalysis.jl to help the diagnosis. My first assumption is that each creation of a method instance in Julia indicates a native code object is generated.

Let’s start with a simple case:

```julia
julia> using MethodAnalysis

julia> function count_number(A::AbstractArray)
                  rst = 0
                  for x in A
                      rst += count_number(x)
                  end
                  return rst
              end
count_number (generic function with 1 method)

julia> count_number(x::Number) = 1
count_number (generic function with 2 method)

julia> count_number(x) = 0
count_number (generic function with 3 methods)

julia> count_number([1, 2, 3])
3

julia> methodinstances(count_number)
2-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Int64})
 MethodInstance for count_number(::Int64)

```

If we restart Julia and instead execute `count_number([1, 2, "julia", 3.0])`. Without checking `methodinstances` result, I’m expecting it to return 4 method instances:

- `count_number(::Vector{Any})`
- `count_number(::Int)`
- `count_number(::Float64)`
- `count_number(::String)`

But instead, it returns:

```julia
julia> methodinstances(count_number)
7-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Any})
 MethodInstance for count_number(::AbstractArray)
 MethodInstance for count_number(::Number)
 MethodInstance for count_number(::Int64)
 MethodInstance for count_number(::Float64)
 MethodInstance for count_number(::Any)
 MethodInstance for count_number(::String)

```

This is a bit surprising to me. **Why would Julia ever try to generate `count_number(::AbstractArray)` when `count_number(::Vector{Any})` is sufficient?**

* * *

My first guess is that `count_number`’s recursively calling itself complicates this, so I made a simpler version of it:

```julia
julia> function count_number(A::AbstractArray)
                  rst = 0
                  for x in A
                      rst += _count_number(x)
                  end
                  return rst
              end
count_number (generic function with 1 method)

julia> _count_number(x::Number) = 1
_count_number (generic function with 1 method)

julia> _count_number(x) = 0
_count_number (generic function with 2 methods)

julia> count_number([1, 2, "julia", 3.0])
3

julia> methodinstances(count_number)
1-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Any})

julia> methodinstances(_count_number)
2-element Vector{Core.MethodInstance}:
 MethodInstance for _count_number(::Number)
 MethodInstance for _count_number(::Any)

```

This raises more questions:

- why Julia generates the non-specialized `_count_number(::Number)` and `_count_number(::Any)` instead of the specialized `_count_number(::Int64)`, `_count_number(::Float64)` and `_count_number(::String)`?
- if `_count_number(::Number)` and `_count_number(::Any)` is sufficient, why would the recursive version generate `count_number(::Int64)`, `count_number(::Float64)` and `count_number(::String)`?

I assume @tim.holy would be interested in these questions?

---

<div class="post-metadata">

**Author:** ![aviatesk](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aviatesk/32/7610_2.png) [@aviatesk](https://discourse.julialang.org/u/aviatesk)\
**Post date:** [April 28, 2023, 10:25am UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020/2 "2023-04-28T10:25:34Z")

</div>

> [@JohnnyChen94](#):
>
> My first assumption is that each creation of a method instance in Julia indicates a native code object is generated.

This assumption is wrong, and the truth is each creation of method instance is (essentially) associated with inference on the method – and I think it answers all the questions.  
In Julia, `MethodInstance` object does not necessarily come with native code cache. `MethodInstance` object is created by inference (or by interpreter if `MethodInstance` represents top-level code thunk, but let’s ignore this fact for the sake of simplicity), and we associate it with `CodeInstance` object that holds the result of the analysis on the method instance. `CodeInstance` may or may not be associated with the generated native code. For example, if the result of method execution can safely be constant folded, there is no need to generate a native code and thus we simply holds the constant return value in `CodeInstance`.

Now, the important note is that Julia compiler’s type inference can deal with abstract method calls, i.e. it doesn’t require analyzed method instance to represent concrete method call. For example, when inference tries to infer `count_number(::Any)`, it will look for existing methods that can be dispatched for the signature, and figure out there are only 3 of them (i.e. `count_number(::AbstractVector)`, `count_number(::Number)`, `count_number(::Any)`, so it will try to infer all of them using their declared signatures. This is why you observed abstract method instances in the first example.

This behavior depends on the implementation detail of inference, so if you add one additional method, you will see the different result. For example, inference will give up abstract call inference when there are \>3 matching method candidates, so if you add one additional method, we will not get abstract method instances, but only concrete method instances. This is because abstract call inference does not happen, and the call is runtime dispatched, causing concrete call inference to happen:

```julia
julia> using MethodAnalysis

julia> function count_number(A::AbstractArray)
                  rst = 0
                  for x in A
                      rst += count_number(x)
                  end
                  return rst
              end
count_number (generic function with 1 method)

julia> count_number(x::Number) = 1
count_number (generic function with 2 methods)

julia> count_number(x) = 0
count_number (generic function with 3 methods)

julia> count_number(::String) = 0
count_number (generic function with 4 methods)

julia> count_number([1, 2, "julia", 3.0])
3

julia> methodinstances(count_number)
4-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Any})
 MethodInstance for count_number(::Int64)
 MethodInstance for count_number(::Float64)
 MethodInstance for count_number(::String)

```

---

<div class="post-metadata">

**Author:** ![aviatesk](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aviatesk/32/7610_2.png) [@aviatesk](https://discourse.julialang.org/u/aviatesk)\
**Post date:** [April 28, 2023, 10:38am UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020/3 "2023-04-28T10:38:25Z")

</div>

I missed to answer the second question. Why we saw abstract method instance only in the first example? That’s because, the compiler does not generate runtime dispatch call for the second example, but it does generate it for the first example. You can confirm it with `code_typed`.

> The first example

```julia
julia> code_typed(count_number, (Vector{Any},))
1-element Vector{Any}:
 CodeInfo(
1 ── %1 = Base.bitcast(UInt64, 1)::UInt64
│ %2 = Base.sub_int(%1, 0x0000000000000001)::UInt64
│ %3 = Base.arraylen(A)::Int64
│ %4 = Base.sle_int(0, %3)::Bool
│ %5 = Base.bitcast(UInt64, %3)::UInt64
│ %6 = Base.ult_int(%2, %5)::Bool
│ %7 = Base.and_int(%4, %6)::Bool
└─── goto #3 if not %7
2 ── %9 = Base.arrayref(false, A, 1)::Any
│ %10 = Base.add_int(1, 1)::Int64
└─── goto #4
3 ── goto #4
4 ┄─ %13 = φ (#2 => false, #3 => true)::Bool
│ %14 = φ (#2 => %9)::Any
│ %15 = φ (#2 => %10)::Int64
└─── goto #5
5 ── %17 = Base.not_int(%13)::Bool
└─── goto #11 if not %17
6 ┄─ %19 = φ (#5 => %14, #10 => %36)::Any
│ %20 = φ (#5 => %15, #10 => %37)::Int64
│ %21 = φ (#5 => 0, #10 => %23)::Any
│ %22 = Main.count_number(%19)::Any
│ %23 = (%21 + %22)::Any
│ %24 = Base.bitcast(UInt64, %20)::UInt64
│ %25 = Base.sub_int(%24, 0x0000000000000001)::UInt64
│ %26 = Base.arraylen(A)::Int64
│ %27 = Base.sle_int(0, %26)::Bool
│ %28 = Base.bitcast(UInt64, %26)::UInt64
│ %29 = Base.ult_int(%25, %28)::Bool
│ %30 = Base.and_int(%27, %29)::Bool
└─── goto #8 if not %30
7 ── %32 = Base.arrayref(false, A, %20)::Any
│ %33 = Base.add_int(%20, 1)::Int64
└─── goto #9
8 ── goto #9
9 ┄─ %36 = φ (#7 => %32)::Any
│ %37 = φ (#7 => %33)::Int64
│ %38 = φ (#7 => false, #8 => true)::Bool
│ %39 = Base.not_int(%38)::Bool
└─── goto #11 if not %39
10 ─ goto #6
11 ┄ %42 = φ (#9 => %23, #5 => 0)::Any
└─── return %42
) => Any

```

> The second example

```julia
julia> code_typed(count_number, (Vector{Any},))
1-element Vector{Any}:
 CodeInfo(
1 ── %1 = Base.bitcast(UInt64, 1)::UInt64
│ %2 = Base.sub_int(%1, 0x0000000000000001)::UInt64
│ %3 = Base.arraylen(A)::Int64
│ %4 = Base.sle_int(0, %3)::Bool
│ %5 = Base.bitcast(UInt64, %3)::UInt64
│ %6 = Base.ult_int(%2, %5)::Bool
│ %7 = Base.and_int(%4, %6)::Bool
└─── goto #3 if not %7
2 ── %9 = Base.arrayref(false, A, 1)::Any
│ %10 = Base.add_int(1, 1)::Int64
└─── goto #4
3 ── goto #4
4 ┄─ %13 = φ (#2 => false, #3 => true)::Bool
│ %14 = φ (#2 => %9)::Any
│ %15 = φ (#2 => %10)::Int64
└─── goto #5
5 ── %17 = Base.not_int(%13)::Bool
└─── goto #16 if not %17
6 ┄─ %19 = φ (#5 => %14, #15 => %43)::Any
│ %20 = φ (#5 => %15, #15 => %44)::Int64
│ %21 = φ (#5 => 0, #15 => %30)::Int64
│ %22 = (isa)(%19, Number)::Bool
└─── goto #8 if not %22
7 ── goto #11
8 ── goto #10 if not true
9 ── goto #11
10 ─ Core.throw(ErrorException("fatal error in type inference (type bound)"))::Union{}
└─── unreachable
11 ┄ %29 = φ (#7 => 1, #9 => 0)::Int64
│ %30 = Base.add_int(%21, %29)::Int64
│ %31 = Base.bitcast(UInt64, %20)::UInt64
│ %32 = Base.sub_int(%31, 0x0000000000000001)::UInt64
│ %33 = Base.arraylen(A)::Int64
│ %34 = Base.sle_int(0, %33)::Bool
│ %35 = Base.bitcast(UInt64, %33)::UInt64
│ %36 = Base.ult_int(%32, %35)::Bool
│ %37 = Base.and_int(%34, %36)::Bool
└─── goto #13 if not %37
12 ─ %39 = Base.arrayref(false, A, %20)::Any
│ %40 = Base.add_int(%20, 1)::Int64
└─── goto #14
13 ─ goto #14
14 ┄ %43 = φ (#12 => %39)::Any
│ %44 = φ (#12 => %40)::Int64
│ %45 = φ (#12 => false, #13 => true)::Bool
│ %46 = Base.not_int(%45)::Bool
└─── goto #16 if not %46
15 ─ goto #6
16 ┄ %49 = φ (#14 => %30, #5 => 0)::Int64
└─── return %49
) => Int64

```

In the first example, there is `%22 = Main.count_number(%19)::Any` that indicates the call to `count_number` will be runtime dispatched nevertheless inference has analyzed all the dispatch candidates. On the other hand, there is no such a statement, meaning that `_count_number` call has been resolved statically and no runtime dispatch will happen.  
So only the first example contains concrete method instances because runtime dispatch happened.

This behavior actually depends on our inlining algorithm. This behavior can be configured by users with the `@nospecialize` annotation.

```julia
julia> using MethodAnalysis

julia> count_number(@nospecialize x::Number) = 1;

julia> count_number(@nospecialize x) = 0;

julia> function count_number(@nospecialize A::AbstractArray)
            rst = 0
            for x in A
                rst += count_number(x)
            end
            return rst
        end;

julia> count_number([1, 2, "julia", 3.0])
3

julia> methodinstances(count_number)
4-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Number)
 MethodInstance for count_number(::AbstractArray)
 MethodInstance for count_number(::Vector{Any})
 MethodInstance for count_number(::Any)

```

---

<div class="post-metadata">

**Author:** ![JohnnyChen94](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/johnnychen94/32/29979_2.png) [@JohnnyChen94](https://discourse.julialang.org/u/JohnnyChen94)\
**Post date:** [April 28, 2023, 2:16pm UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020/4 "2023-04-28T14:16:17Z")

</div>

> [@aviatesk](#):
>
> On the other hand, there is no such a statement, meaning that `_count_number` call has been resolved statically and no runtime dispatch will happen.

Thanks for pointing it out! I also tried adding a few more method candidates for `_count_number` for the second example, and it now becomes runtime dispatch

```julia
julia> using MethodAnalysis

julia> function count_number(A::AbstractArray)
                  rst = 0
                  for x in A
                      rst += _count_number(x)
                  end
                  return rst
              end
count_number (generic function with 1 method)

julia> _count_number(x::Number) = 1
_count_number (generic function with 1 method)

julia> _count_number(x) = 0
_count_number (generic function with 2 methods)

julia> _count_number(x::String) = 0
_count_number (generic function with 3 methods)

julia> _count_number(x::Real) = 1
_count_number (generic function with 4 methods)

julia> count_number([1, 2, "julia", 3.0])
3

julia> methodinstances(count_number)
1-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Any})

julia> methodinstances(_count_number)
3-element Vector{Core.MethodInstance}:
 MethodInstance for _count_number(::Int64)
 MethodInstance for _count_number(::Float64)
 MethodInstance for _count_number(::String)

```

This is also slightly counter-intuitive: my mental model tells me that if you see a red un-inferrable part in `@code_warntype`, a runtime dispatch happens… Turns out Julia is too smart for me to predict its behavior 😂 .

---

<div class="post-metadata">

**Author:** ![JohnnyChen94](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/johnnychen94/32/29979_2.png) [@JohnnyChen94](https://discourse.julialang.org/u/JohnnyChen94)\
**Post date:** [April 28, 2023, 2:27pm UTC](https://discourse.julialang.org/t/how-to-explain-recursive-generation-of-method-instances-for-non-concrete-types/98020/5 "2023-04-28T14:27:01Z")

</div>

> [@aviatesk](#):
>
> > [@JohnnyChen94](#):
> >
> > My first assumption is that each creation of a method instance in Julia indicates a native code object is generated.
> 
> This assumption is wrong, and the truth is each creation of method instance is (essentially) associated with inference on the method – and I think it answers all the questions.

I’m not sure if I get it correct here. It seems that we can’t also assume that native code compilation indicates a new method instance creation.

```julia
julia> using MethodAnalysis

julia> function count_number(A::AbstractArray)
           rst = 0
           for x in A
               if is_positive(x)
                   rst += 1
               end
           end
           return rst
       end
count_number (generic function with 1 method)

julia> is_positive(x) = x > 0
is_positive (generic function with 1 method)

julia> count_number(Bool[1, 0, 1])
2

julia> methodinstances(count_number)
1-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Bool})

julia> methodinstances(is_positive)
1-element Vector{Core.MethodInstance}:
 MethodInstance for is_positive(::Bool)

```

if we add one more method to trigger invalidation (without restarting a new Julia):

```julia
julia> is_positive(x::Bool) = x
is_positive (generic function with 2 methods)

julia> count_number(Bool[1, 0, 1])
2

julia> methodinstances(count_number)
1-element Vector{Core.MethodInstance}:
 MethodInstance for count_number(::Vector{Bool})

julia> methodinstances(is_positive)
2-element Vector{Core.MethodInstance}:
 MethodInstance for is_positive(::Bool)
 MethodInstance for is_positive(::Bool)

julia> map(x->x.def, ans)
[1] is_positive(x::Bool) @ Main REPL[7]:1
[2] is_positive(x) @ Main REPL[2]:1

```

Here we get two `is_positive(::Bool)` instances but only one `count_number` instance. I guess it’s because `is_positive(::Bool)` doesn’t change the return type, and thus there’s no need to redo the type inference for `count_number`. Am I correct?

Does `count_number` recompile here? Intuitively I think it recompiles but I’m not 100% sure of it 😂. If we can’t track the compilation by tracking method instances, is there a way to directly track and analyze when Julia compiles native code, `CodeInstance`?