performance regression on 1.8.0-rc3

[matthias314]

The function f given below runs dramatically slower on 1.8.0-rc3 than on 1.7.3 and master. Here are the timings for f([1,1,1,1], 4).

1.7.3
  74.809 μs (2537 allocations: 189.16 KiB)
1.8.0-rc3
  1.298 ms (19877 allocations: 603.53 KiB)
1.9.0-DEV.1087
  75.896 μs (2197 allocations: 178.53 KiB)

The differences get larger for larger arguments.

Here is the code. f(n::Int, k::Int) computes a list of all decompositions of the non-negative number n into k non-negative summands. f(v::Vector{Int}, k::Int) does the same for vectors with non-negative entries. Only this latter version displays the difference in runtime.

function f(n::Int, k::Int)
    if k == 0
        n == 0 ? [Int[]] : Vector{Int}[]
    elseif k == 1
        [[n]]
    else
        L = Vector{Int}[]
        for m in 0:n
            append!(L, map(l -> push!(l, m), f(n-m, k-1)))
        end
        L
    end
end

function f(v::Vector{Int}, k::Int)
    if k == 0
        iszero(v) ? [Vector{Vector{Int}}[]] : Vector{Vector{Vector{Int}}}[]
    elseif isempty(v)
        [[Int[] for _ in 1:k]]
    else
        L = Vector{Vector{Int}}[]
        L1 = f(v[1:end-1], k)
        L2 = f(v[end], k)
        for p1 in L1, p2 in L2
            push!(L, [[v1; m2] for (v1, m2) in zip(p1, p2)])
        end
	L
    end
end

julia> versioninfo()
Julia Version 1.8.0-rc3
Commit 33f19bcbd25 (2022-07-13 19:10 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i3-10110U CPU @ 2.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, skylake)
  Threads: 1 on 4 virtual cores

[KristofferC]

Looks fast again on #46075.