Track backedges through not-yet-defined bindings?

[Tortar]

I was reading the thread at https://discourse.julialang.org/t/julia-slower-than-python-for-finding-pangrams/112481 and I found a very strange behaviour, consider this code to be run on the REPL:

input = "wjjqevffkkgbcehhiqpvqutmwxawzvjnbvukmlzxyhkgfddzfjhcujnlkjbdfgghjhujkiuytghjioplkjhgfdsaqwertyujioplkjhgfdsaqwertzuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkj"

function ispangram10(input::String)
    a,A,z,Z = UInt8('a'),UInt8('A'),UInt8('z'),UInt8('Z')
    appears::UInt32 = ~((one(UInt32)<<26)-one(UInt32))
    @inbounds for b in codeunits(input)
        if A ≤ b ≤ Z
            appears |= one(UInt32) << shift_safe(UInt32, b-A)
        elseif a ≤ b ≤ z
            appears |= one(UInt32) << shift_safe(UInt32, b-a)
        end
        appears == (-1%UInt32) && return true
    end
    return false
end
           
ispangram10(input) # this will error

shift_safe(::Type{T}, s::Integer) where {T} = s & (8 * sizeof(T) - 1)

ispangram10(input)
@time ispangram10(input)

you will see that the last timing is

julia> @time ispangram10(input)
  0.000032 seconds (137 allocations: 2.141 KiB)

now if you instead run this:

input = "wjjqevffkkgbcehhiqpvqutmwxawzvjnbvukmlzxyhkgfddzfjhcujnlkjbdfgghjhujkiuytghjioplkjhgfdsaqwertyujioplkjhgfdsaqwertzuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsazxcvbnmlkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkjhgfdsaqwertyuioplkj"

function ispangram10(input::String)
    a,A,z,Z = UInt8('a'),UInt8('A'),UInt8('z'),UInt8('Z')
    appears::UInt32 = ~((one(UInt32)<<26)-one(UInt32))
    @inbounds for b in codeunits(input)
        if A ≤ b ≤ Z
            appears |= one(UInt32) << shift_safe(UInt32, b-A)
        elseif a ≤ b ≤ z
            appears |= one(UInt32) << shift_safe(UInt32, b-a)
        end
        appears == (-1%UInt32) && return true
    end
    return false
end
           
#ispangram10(input) # this is the only difference, it is commented in this version

shift_safe(::Type{T}, s::Integer) where {T} = s & (8 * sizeof(T) - 1)

ispangram10(input)
@time ispangram10(input)

it returns instead

julia> @time ispangram10(input)
  0.000002 seconds

What is it happening here? Why the error in the first version makes the function perf much worse afterwards?

julia> versioninfo()
Julia Version 1.10.2
Commit bd47eca2c8a (2024-03-01 10:14 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × AMD Ryzen 5 5600H with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 1 default, 0 interactive, 1 GC (on 12 virtual cores)

edit: tested also on 1.11-alpha2, same behaviour

[mbauman]

If shift_safe doesn't yet exist, there's no place for ispangram10 to record its backedge, and so there's no way for it to know it needs to be invalidated. The compiler knows this limitation, so it compiles it conservatively — with a dynamic call and a type instability in it. If you have a function shift_safe end defined from the get-go then ispangram10 will be able to be properly invalidated, even if it still throws a MethodError on its first invocation.

[Tortar]

thanks @mbauman for the clarification, if this can't be improved then I just learnt something :D I changed the title to properly reflect the real issue anyway

[Tortar]

I'm thinking if a warning when something like this happens could be beneficial in any case

[vchuravy]

Essentially a duplicate of #40399 and #8870

Bindings (defined or not defined) are not tracked by the system.