Performance regression in "spellcheck" string processing benchmark

[KristofferC]

The benchmark at https://github.com/JuliaCI/BaseBenchmarks.jl/blob/master/src/problem/SpellCheck.jl has a ~4x regression vs 1.9. A repro that can be copy pasted is

using Downloads
spellcheck = "https://raw.githubusercontent.com/JuliaCI/BaseBenchmarks.jl/master/src/problem/data/norvig_spellcheck.txt"
mkpath("data")
Downloads.download(spellcheck, joinpath("data", "norvig_spellcheck.txt"))

module ProblemBenchmarks
    using Downloads
    const PROBLEM_DATA_DIR = joinpath(dirname(@__FILE__), "data")
    file = Downloads.download("https://raw.githubusercontent.com/JuliaCI/BaseBenchmarks.jl/master/src/problem/SpellCheck.jl")
    include(file)
end

using BenchmarkTools

@btime ProblemBenchmarks.SpellCheck.perf_spellcheck()

This gives

1.324 s (23983215 allocations: 1.49 GiB) # 1.9
4.900 s (133224596 allocations: 4.76 GiB) # 1.10

Quickly looking at a profile, this looks suspicious:

 13╎    ╎    ╎    ╎    ╎    ╎    ╎   2154 none:0; (::Main.ProblemBenchmarks.SpellCheck.var"#4#9")(::Tuple{Tuple{String, String}, Char})
 18╎    ╎    ╎    ╎    ╎    ╎    ╎    2057 @Base/strings/substring.jl:225; string
489╎    ╎    ╎    ╎    ╎    ╎    ╎     489  @Base/strings/substring.jl:229; _string(::String, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
156╎    ╎    ╎    ╎    ╎    ╎    ╎     156  @Base/strings/substring.jl:231; _string(::String, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
  3╎    ╎    ╎    ╎    ╎    ╎    ╎     555  @Base/strings/substring.jl:243; _string(::String, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
551╎    ╎    ╎    ╎    ╎    ╎    ╎    ╎ 552  @Base/tuple.jl:72; iterate(t::Tuple{String, Vararg{Union{Char, SubString{String}, String, Symbol}}}, i::Int64)
165╎    ╎    ╎    ╎    ╎    ╎    ╎     165  @Base/strings/substring.jl:246; _string(::String, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
  1╎    ╎    ╎    ╎    ╎    ╎    ╎     593  @Base/strings/substring.jl:254; _string(::String, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
586╎    ╎    ╎    ╎    ╎    ╎    ╎    ╎ 592  @Base/tuple.jl:72; iterate(t::Tuple{String, Vararg{Union{Char, SubString{String}, String, Symbol}}}, i::Int64)

In 1.9, there seems to be way less time spent in that part:

   24╎    ╎    ╎    ╎    ╎    ╎    ╎   201   @Base/array.jl:0; (::Main.ProblemBenchmarks.SpellCheck.var"#4#9")(::Tuple{Tuple{String, String}, Char})
     ╎    ╎    ╎    ╎    ╎    ╎    ╎    63    @Base/strings/substring.jl:237; string(::String, ::Char, ::Vararg{Union{Char, SubString{String}, String, Symbol}})
   63╎    ╎    ╎    ╎    ╎    ╎    ╎     63    @Base/strings/string.jl:90; _string_n

[gbaraldi]

I'm pretty sure #49249 is the same as this?

[gbaraldi]

This is very similar to what I posted on the other issue, specificically

appears in both

[oscardssmith]

Is this fixed by #50444?

[gbaraldi]

Also no ;)

[oscardssmith]

reduced to

@btime string("a", 'b')

On 1.9: 29.058 ns (3 allocations: 88 bytes)
On 1.10 175.154 ns (6 allocations: 184 bytes)

[oscardssmith]

reduced further to

julia> Core.Compiler.tmerge(Tuple{Base.BitSigned, Int}, Nothing)
Union{Nothing, Tuple{Any, Any}}

julia> Core.Compiler.tmerge(Tuple{Any, Int}, Nothing)
Union{Nothing, Tuple{Any, Int64}}

fixed by #50927.
That said I still think we might want to merge #50891. Thoughts?

[oscardssmith]

fixed by #50929 (once that gets backported)