Method definition can take quadratic time

[aviatesk]

MRE:

julia> function time_definition(n)
           ex = Expr(:block)
           var = gensym()
           push!(ex.args, :($var = x))
           for _ = 1:n
               newvar = gensym()
               push!(ex.args, :($newvar = $var + 1))
               var = newvar
           end
           @time @eval global function quadratic(x)
               $ex
           end
       end;

julia> function time_execution()
           s = time_ns()
           @eval quadratic(42)
           e = time_ns()
           Base.time_print(e - s)
       end;

julia> time_definition(1000)
  0.044844 seconds (11.15 k allocations: 628.467 KiB)
quadratic (generic function with 1 method)

julia> time_execution()
  0.027912 seconds

julia> time_definition(10000)
  1.738030 seconds (118.12 k allocations: 6.034 MiB)
quadratic (generic function with 1 method)

julia> time_execution()
  0.400399 seconds

julia> time_definition(20000)
  6.889014 seconds (238.12 k allocations: 12.108 MiB, 0.23% gc time)
quadratic (generic function with 1 method)

julia> time_execution()
  1.125169 seconds

It's nice to have this improved as we are going to fix the quadratic behavior of inference soonish (#45276 )

[oscardssmith]

does this have significant TTFP implications?

[aviatesk]

Probably not, this extreme pattern won't be seen that often.

[jmichel7]

see #45395

[KristofferC]

Are you saying that issue is related to this in some way?

[jmichel7]

I do not know, but it is (another?) quadratic or exponential thing happening while compiling a method

[aviatesk]

Now we merged #45276 and it seems to be the lowering time is a dominant factor of the whole compilation for this kind of case:

julia> function time_definition(n)
           ex = Expr(:block)
           var = gensym()
           push!(ex.args, :($var = x))
           for _ = 1:n
               newvar = gensym()
               push!(ex.args, :($newvar = $var + 1))
               var = newvar
           end
           @time @eval global function quadratic(x)
               $ex
           end
       end
time_definition (generic function with 1 method)

julia> function time_execution()
           s = time_ns()
           @eval quadratic(42)
           e = time_ns()
           Base.time_print(e - s)
       end
time_execution (generic function with 1 method)

julia> time_definition(1000)
  0.044844 seconds (11.15 k allocations: 628.467 KiB)
quadratic (generic function with 1 method)

julia> time_execution()
  0.027912 seconds
julia> time_definition(10000)
  1.738030 seconds (118.12 k allocations: 6.034 MiB)
quadratic (generic function with 1 method)

julia> time_execution()
  0.400399 seconds
julia> time_definition(20000)
  6.889014 seconds (238.12 k allocations: 12.108 MiB, 0.23% gc time)
quadratic (generic function with 1 method)

julia> time_execution()
  1.125169 seconds

[aviatesk]

This seems to have been fixed on v1.10.