Unused `where T` causes a function to become very slow

We noticed that an unused where T in a function declaration can cause the function to become much slower and to allocate a lot more memory. Consider for example the following two functions which are identical except that the second one has an unnecessary where T:

function f1(x::Int)
    return mod(2 * x + 1, 1000)
end
function f2(x::Int) where T # Note the unused `where T`
    return mod(2 * x + 1, 1000)
end

Comparing performance of the two functions reveals that the second is much slower:

function test(f::Function)
    x = 0
    for i = 1:100000000
        x = f(x)
    end
    x
end
test(f1)
@time test(f1) # 0.389844 seconds
test(f2)
@time test(f2) # 2.278735 seconds (96.00 M allocations: 1.431 GiB, 0.51% gc time)

Is this a bug? Is it possible to add an optimization to Julia to ignore unused where arguments so that they don’t impact performance anymore? Such unused arguments can sometimes occur in large Julia codebases as leftovers from previous reversions, etc. Another potential solution is to treat such unused arguments as syntax errors…

12 Likes

This can be reproduced on Julia 1.4.0. Here is my versioninfo():

julia> versioninfo()
Julia Version 1.4.0
Commit b8e9a9ecc6 (2020-03-21 16:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)
1 Like

Wow, that’s wild! I would’ve guessed that would be a parse error, yeah.

I can also reproduce it on 1.5, on Commit c3d6a463be* (12 days old master).

2 Likes

Note that you can do this, to check your package for such problems:

module UnTee
    function f1(x::Int)
        return mod(2 * x + 1, 1000)
    end
    function f2(x::Int) where T # Note the unused `where T`
        return mod(2 * x + 1, 1000)
    end
end

using Test
@test isempty(detect_unbound_args(UnTee)) # fails
12 Likes

Is there any reason why anyone would ever want unbound type parameters? Can this just be a parse error? Can they be used for anything?

Making things even more interesting, f1 and f2 have identical code_lowered, and code_typed. There are some differences in the code_native, but that’s above my pay grade.

I’m sure this has come up before, but I can’t for my life find an issue or discussion about it. It feels like it warrants an issue though :slight_smile:

3 Likes

You would have to look at test(f1) vs test(f2).

2 Likes

Thanks all! I filed this as a github issue https://github.com/JuliaLang/julia/issues/35935 and linked to this discussion

2 Likes

Unfortunately, this has a lot of false positive, preventing me from adding it to my test suites.

But extremely useful – I found a few!
But, this remains:

julia> using VectorizationBase, Test
[ Info: Precompiling VectorizationBase [3d5dd08c-fd9d-11e8-17fa-ed2836048c2f]

julia> detect_unbound_args(VectorizationBase)
[1] gep(ptr::Ptr{T}, i::Tuple{Vararg{VecElement{I},W}}) where {W, T, I<:Integer} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/vectorizable.jl:202
[2] vbroadcast(::Type{Tuple{Vararg{VecElement{T},W}}}, ptr::Ptr) where {W, T} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:140
[3] vbroadcast(::Type{Tuple{Vararg{VecElement{T},W}}}, v::Tuple{Vararg{VecElement{T},W}}) where {W, T} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:142
[4] vbroadcast(::Type{Tuple{Vararg{VecElement{T1},W}}}, s::T2) where {W, T1<:Integer, T2<:Integer} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:139
[5] vzero(::Type{Tuple{Vararg{VecElement{T},W}}}) where {W, T} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:117
[6] vbroadcast(::Type{Tuple{Vararg{VecElement{T1},W}}}, s) where {W, T1} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:138
[7] vone(::Type{Tuple{Vararg{VecElement{T},W}}}) where {W, T} in VectorizationBase at /home/chriselrod/.julia/dev/VectorizationBase/src/VectorizationBase.jl:146

Lines 138-146, as an example:

@inline vbroadcast(::Type{Vec{W,T1}}, s) where {W,T1} = vbroadcast(Vec{W,T1}, convert(T1,s))
@inline vbroadcast(::Type{Vec{W,T1}}, s::T2) where {W,T1<:Integer,T2<:Integer} = vbroadcast(Vec{W,T1}, s % T1)
@inline vbroadcast(::Type{Vec{W,T}}, ptr::Ptr) where {W,T} = vbroadcast(Vec{W,T}, Base.unsafe_convert(Ptr{T},ptr))
@inline vbroadcast(::Type{SVec{W,T}}, s) where {W,T} = SVec(vbroadcast(Vec{W,T}, s))
@inline vbroadcast(::Type{Vec{W,T}}, v::Vec{W,T}) where {W,T} = v
@inline vbroadcast(::Type{SVec{W,T}}, v::SVec{W,T}) where {W,T} = v
@inline vbroadcast(::Type{SVec{W,T}}, v::Vec{W,T}) where {W,T} = SVec(v)

@inline vone(::Type{Vec{W,T}}) where {W,T} = vbroadcast(Vec{W,T}, one(T))

I really wish this were a parser error. Once upon a time it was rendering this issue harmless, but now it is rather nasty.

2 Likes

Oh I hadn’t noticed false positives yet, I only recently found this tool. I guess they count as bugs in Test?

I think the “false positives” are due to Vararg{T} matching zero arguments, resulting in T being unbound.

To capture an element type in the call signature, one can use something like:

f(::Tuple{T, Vararg{T}}) where {T}

(The empty tuple must then be handled by a separate method that does not depend on T.)

3 Likes

Interesting!

julia> const _Vec{W,T} = Tuple{Core.VecElement{T},Vararg{Core.VecElement{T},W}}
Tuple{VecElement{T},Vararg{VecElement{T},W}} where T where W

julia> using VectorizationBase: Vec

julia> Vec{8,Float64} === _Vec{7,Float64}
true

Also interesting that the problem seems to be solved by wrapping the tuple in a struct (which I do anyway so that I can overload methods):

julia> NTuple{0,Float64} === NTuple{0,Int}
true

julia> SVec{0,Float64} === SVec{0,Int}
false

julia> dump(SVec{2,Float64}(1.0)) # Just a tuple-wrapper
SVec{2,Float64}
  data: Tuple{VecElement{Float64},VecElement{Float64}}
    1: VecElement{Float64}
      value: Float64 1.0
    2: VecElement{Float64}
      value: Float64 1.0

Meaning that I should be able to continue to provide SVec as the primary API and Vec as the secondary, while dealing with the awkward _Vec internally.

EDIT:
Now…

julia -O0 -E "using VectorizationBase, Test; detect_unbound_args(VectorizationBase)"
Method[]

Great, looks like I can start testing for this!