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

blegat · 2019-07-11T09:06:18Z

blegat · 2019-07-25T14:07:06Z

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 · 2021-06-21T22:31:24Z

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 · 2021-07-27T03:31:07Z

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

blegat mentioned this issue Jul 11, 2019

Add variable bridges #759

Merged

4 tasks

blegat added the Type: Enhancement label Jul 11, 2019

blegat mentioned this issue Aug 23, 2019

Don't allow DataType as type of argument jump-dev/Dualization.jl#54

Closed

odow added Type: Performance and removed Type: Enhancement labels Dec 15, 2020

odow added the breaking label Jun 21, 2021

odow added this to the v0.10 milestone Jun 21, 2021

odow mentioned this issue Jul 28, 2021

[breaking] s/DataType/Type #1501

Merged

odow closed this as completed in #1501 Jul 28, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

blegat commented Jul 11, 2019

blegat commented Jul 25, 2019 •

edited

Loading

odow commented Jun 21, 2021

odow commented Jul 27, 2021

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

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

Comments

blegat commented Jul 11, 2019

blegat commented Jul 25, 2019 • edited Loading

odow commented Jun 21, 2021

odow commented Jul 27, 2021

blegat commented Jul 25, 2019 •

edited

Loading