methodinstance(foo, types) returns MethodError permanently if method is not defined

[topolarity]

julia> using GPUCompiler

julia> function foo end
foo (generic function with 0 methods)

julia> methodinstance(Base._stable_typeof(foo), Base.to_tuple_type(()))
ERROR: MethodError: no method matching foo()
Stacktrace:
 [1] macro expansion
   @ GPUCompiler ~/.julia/packages/GPUCompiler/U36Ed/src/jlgen.jl:0 [inlined]
 [2] methodinstance(ft::Type{typeof(foo)}, tt::Type{Tuple{}})
   @ GPUCompiler ~/.julia/packages/GPUCompiler/U36Ed/src/jlgen.jl:123
 [3] top-level scope
   @ REPL[3]:1

julia> foo() = nothing
foo (generic function with 1 method)

julia> methodinstance(Base._stable_typeof(foo), Base.to_tuple_type(()))
ERROR: MethodError: no method matching foo()
The applicable method may be too new: running in world age 25447, while current world is 25448.

Closest candidates are:
  foo() (method too new to be called from this world context.)
   @ Main REPL[4]:1

Stacktrace:
 [1] macro expansion
   @ GPUCompiler ~/.julia/packages/GPUCompiler/U36Ed/src/jlgen.jl:0 [inlined]
 [2] methodinstance(ft::Type{typeof(foo)}, tt::Type{Tuple{}})
   @ GPUCompiler ~/.julia/packages/GPUCompiler/U36Ed/src/jlgen.jl:123
 [3] top-level scope
   @ REPL[5]:1

If I had made no mistake and defined the method before calling methodinstance:

julia> using GPUCompiler

julia> function foo end
foo (generic function with 0 methods)

julia> foo() = nothing
foo (generic function with 1 method)

julia> methodinstance(Base._stable_typeof(foo), Base.to_tuple_type(())).def
foo()
     @ Main REPL[3]:1

julia> foo() = nothing
foo (generic function with 1 method)

julia> methodinstance(Base._stable_typeof(foo), Base.to_tuple_type(())).def
foo()
     @ Main REPL[5]:1

[maleadt]

Ah, interesting, I hadn't considered that. @vtjnash how should invalidation work here?

[vtjnash]

methodinstance_generator seems like it really should not be @generated, since it seems that it cannot generate the required edges, and likely really does not need to either

[maleadt]

We index the GPUCompiler compilation cache with a (methodinstance, world_age, compiler_config) key, so the look-up of a methodinstance is very performance critical, hence the generated function. Or what are you proposing?

GPUCompiler.jl/src/execution.jl

Lines 91 to 99 in e5cd575

	world = tls_world_age()
	key = (objectid(src), world, cfg)
	# NOTE: we store the MethodInstance's objectid to avoid an expensive allocation.
	# Base does this with a multi-level lookup, first keyed on the mi,
	# then a linear scan over the (typically few) entries.
	# NOTE: no use of lock(::Function)/@lock/get! to avoid try/catch and closure overhead
	lock(cache_lock)
	obj = get(cache, key, nothing)

[vtjnash]

Looking up a methodinstance is usually faster than computing most hash functions

[maleadt]

Can you explain how to implement / where to find such a fast lookup? The fallback one I've implemented in GPUCompiler (for Julia <1.10, without a generator) is relatively slow:

julia> tls_world_age() = ccall(:jl_get_tls_world_age, UInt, ())
tls_world_age (generic function with 1 method)

julia> @inline function typed_signature(ft::Type, tt::Type)
           u = Base.unwrap_unionall(tt)
           return Base.rewrap_unionall(Tuple{ft, u.parameters...}, tt)
       end
typed_signature (generic function with 1 method)

julia> function methodinstance(ft::Type, tt::Type, world::Integer=tls_world_age())
           sig = typed_signature(ft, tt)

           match, _ = Core.Compiler._findsup(sig, nothing, world)
           match === nothing && throw(MethodError(ft, tt, world))

           mi = Core.Compiler.specialize_method(match)

           return mi::Core.MethodInstance
       end
methodinstance (generic function with 2 methods)

julia> methodinstance(typeof(sin), Tuple{Float32})
MethodInstance for sin(::Float32)

julia> using BenchmarkTools

julia> @benchmark methodinstance(typeof(sin), Tuple{Float32})
BenchmarkTools.Trial: 10000 samples with 214 evaluations.
 Range (min … max):  348.313 ns …   8.419 μs  ┊ GC (min … max): 0.00% … 94.22%
 Time  (median):     365.136 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   374.696 ns ± 251.231 ns  ┊ GC (mean ± σ):  2.38% ±  3.38%

                        ▁▃▆█▆▄▂▁
  ▂▁▂▂▂▂▂▂▂▂▂▂▂▃▃▃▃▄▅▆▆▇████████▇▆▅▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  348 ns           Histogram: frequency by time          388 ns <

 Memory estimate: 288 bytes, allocs estimate: 6.

julia> @benchmark GPUCompiler.methodinstance(typeof(sin), Tuple{Float32})
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  2.119 ns … 10.350 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     2.150 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   2.151 ns ±  0.120 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

                 ▄             ▆            ▁█             ▆ ▁
  ▃█▁▁▁▁▁▁▁▁▁▁▁▁▆█▁▁▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▇█ █
  2.12 ns      Histogram: log(frequency) by time     2.16 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

[vtjnash]

It used to be exported as jl_lookup_generic (a thin wrapper around jl_lookup_generic_), but looks like that export is gone now

[maleadt]

I see. We have slightly different inputs here, e.g., function and argument types instead of values. Would it be OK to change jl_lookup_generic_ to take those, and adapt callers like jl_apply_generic to perform the necessary typeofs?

[vchuravy]

I was looking at this earlier. I think the worry is that we would need to construct the tuple type unecessarily.

In particular the hot-path here https://github.com/JuliaLang/julia/blob/e746ba4085b7de0036e596e19c0979071ee0a920/src/gf.c#L3007
avoids the construction of TT, I saved what I was working on here vchuravy/julia@ec7c2e3 (I was trying to allow for either one to be passed and then got stuck on the fast-path)

[MasonProtter]

Would it be feasible to make jl_lookup_generic be able to take a method_table argument? It's important sometimes to get a methodinstance from a specific table (ref #532)

[vchuravy]

I looked at this some more. The fast lookup heavily uses F and args as value and avoids forming the signature type.
In particular jl_typemap_assoc_exact and behind that hides some gnarly code.

[maleadt]

What's the cost of a slow TT vs fast arg lookup?

EDIT: answering my own question, JuliaLang/julia#52176 (comment)