Use Type{<:...} instead of DataType

[blegat]

See #759 (comment)

[blegat]

Just did some benchmarks:

julia> versioninfo()
Julia Version 1.1.1
Commit 55e36cc308 (2019-05-16 04:10 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

Here is the setup, note that it creates a Vector{DataType} if we don't specify any element type:

using MathOptInterface
const MOI = MathOptInterface
using BenchmarkTools
using Test

S1 = MOI.Integer
S2 = MOI.Zeros
S3 = MOI.Nonnegatives

sets1 = DataType[S1, S2, S3] # Equivalent to [S1, S2, S3]
sets2 = Type{<:MOI.AbstractSet}[S1, S2, S3]

If Julia has to dispatch between a method for Any and a method for MOI.AbstractSet, there is a huge benefit for sets2 but I don't thing it happens in MOI source code

f(::Type) = 0
f(::Type{<:MOI.AbstractSet}) = 1

function sumf1(v)
    ret = 0
    for vi in v
        ret += f(vi)
    end
    return ret
end
function sumf2(v)
    ret = 0
    for vi in v
        ret += f(vi)::Int
    end
    return ret
end

@test sumf1(sets1) == sumf1(sets2)
@test sumf1(sets1) == sumf2(sets1)
@test sumf2(sets1) == sumf2(sets2)
@test sumf1(sets2) == sumf2(sets2)

println("f DataType")
@inferred sumf1(sets1)
display(@benchmark $sumf1($sets1))
println("f AbstractSet")
@inferred sumf1(sets2)
display(@benchmark $sumf1($sets2))
println("f DataType")
@inferred sumf2(sets1)
display(@benchmark $sumf2($sets1))
println("f AbstractSet")
@inferred sumf2(sets2)
display(@benchmark $sumf2($sets2))

# output

f DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     326.845 ns (0.00% GC)
  median time:      335.996 ns (0.00% GC)
  mean time:        375.970 ns (0.00% GC)
  maximum time:     1.085 μs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     226
f AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     2.366 ns (0.00% GC)
  median time:      2.644 ns (0.00% GC)
  mean time:        2.705 ns (0.00% GC)
  maximum time:     15.635 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1000
f DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     323.841 ns (0.00% GC)
  median time:      331.545 ns (0.00% GC)
  mean time:        380.069 ns (0.00% GC)
  maximum time:     1.998 μs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     233
f AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     2.533 ns (0.00% GC)
  median time:      3.022 ns (0.00% GC)
  mean time:        3.286 ns (0.00% GC)
  maximum time:     16.207 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1000

There is still a different, but not as big as in the previous case where we have methods forAny and concrete subtypes of MOI.AbstractSet. Again, I don't think we have examples like this:

g(::Type) = 0
g(::Type{MOI.Integer}) = 1
g(::Type{MOI.Zeros}) = 2
g(::Type{MOI.Nonnegatives}) = 3

function sumg1(v)
    ret = 0
    for vi in v
        ret += g(vi)
    end
    return ret
end
function sumg2(v)
    ret = 0
    for vi in v
        ret += g(vi)::Int
    end
    return ret
end

@test sumg1(sets1) == sumg1(sets2)
@test sumg1(sets1) == sumg2(sets1)
@test sumg2(sets1) == sumg2(sets2)
@test sumg1(sets2) == sumg2(sets2)

println("g DataType")
@test_broken @inferred sumg1(sets1) # Inference broken !
display(@benchmark $sumg1($sets1))
println("g AbstractSet")
@inferred sumg1(sets2)
display(@benchmark $sumg1($sets2))
println("g DataType")
@inferred sumg2(sets1)
display(@benchmark $sumg2($sets1))
println("g AbstractSet")
@inferred sumg2(sets2)
display(@benchmark $sumg2($sets2))

# output

g DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     222.591 ns (0.00% GC)
  median time:      234.718 ns (0.00% GC)
  mean time:        260.198 ns (0.00% GC)
  maximum time:     947.699 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     482
g AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.675 ns (0.00% GC)
  median time:      65.081 ns (0.00% GC)
  mean time:        71.651 ns (0.00% GC)
  maximum time:     226.083 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     968
g DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     167.299 ns (0.00% GC)
  median time:      172.438 ns (0.00% GC)
  mean time:        192.121 ns (0.00% GC)
  maximum time:     553.809 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     755
g AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.634 ns (0.00% GC)
  median time:      64.846 ns (0.00% GC)
  mean time:        72.239 ns (0.00% GC)
  maximum time:     232.553 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     974

If we don't have any method defined for Any, there does not seem to be any difference.

h(::Type{MOI.Integer}) = 1
h(::Type{MOI.Zeros}) = 2
h(::Type{MOI.Nonnegatives}) = 3

function sumh1(v)
    ret = 0
    for vi in v
        ret += h(vi)
    end
    return ret
end
function sumh2(v)
    ret = 0
    for vi in v
        ret += h(vi)::Int
    end
    return ret
end

@test sumh1(sets1) == sumh1(sets2)
@test sumh1(sets1) == sumh2(sets1)
@test sumh2(sets1) == sumh2(sets2)
@test sumh1(sets2) == sumh2(sets2)

println("h DataType")
@inferred sumh1(sets1)
display(@benchmark $sumh1($sets1))
println("h AbstractSet")
@inferred sumh1(sets2)
display(@benchmark $sumh1($sets2))
println("h DataType")
@inferred sumh2(sets1)
display(@benchmark $sumh2($sets1))
println("h AbstractSet")
@inferred sumh2(sets2)
display(@benchmark $sumh2($sets2))

# output

h DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.617 ns (0.00% GC)
  median time:      64.828 ns (0.00% GC)
  mean time:        72.969 ns (0.00% GC)
  maximum time:     216.994 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     974
h AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.600 ns (0.00% GC)
  median time:      64.827 ns (0.00% GC)
  mean time:        71.121 ns (0.00% GC)
  maximum time:     227.511 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     976
h DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.626 ns (0.00% GC)
  median time:      64.825 ns (0.00% GC)
  mean time:        73.132 ns (0.00% GC)
  maximum time:     246.150 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     975
h AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     64.628 ns (0.00% GC)
  median time:      64.825 ns (0.00% GC)
  mean time:        73.098 ns (0.00% GC)
  maximum time:     424.294 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     976

If we only have one method and it's for MOI.AbstractSet, we actually have the same result that if there was a method for Any.

i(::Type{<:MOI.AbstractSet}) = 1

function sumi1(v)
    ret = 0
    for vi in v
        ret += i(vi)
    end
    return ret
end
function sumi2(v)
    ret = 0
    for vi in v
        ret += i(vi)::Int
    end
    return ret
end

@test sumi1(sets1) == sumi1(sets2)
@test sumi1(sets1) == sumi2(sets1)
@test sumi2(sets1) == sumi2(sets2)
@test sumi1(sets2) == sumi2(sets2)

println("i DataType")
@inferred sumi1(sets1)
display(@benchmark $sumi1($sets1))
println("i AbstractSet")
@inferred sumi1(sets2)
display(@benchmark $sumi1($sets2))
println("i DataType")
@inferred sumi2(sets1)
display(@benchmark $sumi2($sets1))
println("i AbstractSet")
@inferred sumi2(sets2)
display(@benchmark $sumi2($sets2))

# output

i DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     134.436 ns (0.00% GC)
  median time:      136.919 ns (0.00% GC)
  mean time:        158.181 ns (0.00% GC)
  maximum time:     473.491 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     870
i AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     2.992 ns (0.00% GC)
  median time:      3.031 ns (0.00% GC)
  mean time:        3.176 ns (0.00% GC)
  maximum time:     43.752 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1000
i DataType
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     127.704 ns (0.00% GC)
  median time:      160.157 ns (0.00% GC)
  mean time:        161.583 ns (0.00% GC)
  maximum time:     443.091 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     893
i AbstractSet
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     2.785 ns (0.00% GC)
  median time:      3.029 ns (0.00% GC)
  mean time:        3.133 ns (0.00% GC)
  maximum time:     16.193 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1000

In conclusion, I think we should impose Type{<:AbstractSet} even if the eltype is DataType if nothing is specified.

Also, @JeffBezanson just said in his "What's Bad Bbout Julia" talk that we should not have a method whose signature explicitly require DataType, this might be related.

[odow]

This benchmark isn't measuring the right thing, because Julia doesn't specialize f(::Type).

But there's an argument for making

MathOptInterface.jl/src/Utilities/model.jl

Line 676 in 9780960

list = MOI.get(model.constraints, attr)::Vector{Tuple{DataType,DataType}}

be ::Vector{Any} or Vector{Tuple{<:AbstractFunction,<:AbstractSet}} instead of Vector{Tuple{DataType,DataType}}.

Thoughts @blegat?

[odow]

The quotes from Jeff is "this sort of stuff drives the compiler crazy" and "if you're doing that, please stop."