Performance of small constraints

[blegat]

Creating small constraints like

@variable(model, x)
@variable(model, y)
@constraint(model, x >= y)

is rather costly compared to JuMP v0.18. The reason is that creating a OrderedDict of two elements is a lot slower than creating a Vector of two elements:

julia> using DataStructures

julia> od() = OrderedDict{Int, Int}()
od (generic function with 1 method)

julia> d() = Dict{Int, Int}()
d (generic function with 1 method)

julia> v() = Int[]
v (generic function with 1 method)

julia> using BenchmarkTools

julia> @btime od()
  73.591 ns (4 allocations: 352 bytes)
OrderedDict{Int64,Int64} with 0 entries

julia> @btime d()
  91.941 ns (4 allocations: 608 bytes)
Dict{Int64,Int64} with 0 entries

julia> @btime v()
  19.997 ns (1 allocation: 80 bytes)
0-element Array{Int64,1}

julia> od2() = OrderedDict{Int, Int}(1 => 2, 2 => 3)
od2 (generic function with 1 method)

julia> d2() = Dict{Int, Int}(1 => 2, 2 => 3)
d2 (generic function with 1 method)

julia> v2() = Int[2, 3]
v2 (generic function with 1 method)

julia> @btime od2()
  188.935 ns (9 allocations: 656 bytes)
OrderedDict{Int64,Int64} with 2 entries:
  1 => 2
  2 => 3

julia> @btime d2()
  116.193 ns (6 allocations: 672 bytes)
Dict{Int64,Int64} with 2 entries:
  2 => 3
  1 => 2

julia> @btime v2()
  20.386 ns (1 allocation: 96 bytes)
2-element Array{Int64,1}:
 2
 3

Maybe we could create a custom dict optimized for a small number of elements that would not create the internal dictionary if there is 2 elements or less.

struct CrazyDict{K, V}
    data::Union{Nothing, OrderedDict{K, V}}
    key1::Union{Nothing, K}
    value1::Union{Nothing, V}
    key2::Union{Nothing, K}
    value2::Union{Nothing, V}
end

That would avoid creating a dictionary for small number of elements.

[ccoffrin]

The following test may help in testing performance. It includes large non-convex QCQP feasibility problems from the power system domain, which can be solved with Ipopt. At the time of writing this model build times are similar in time to the solve time, about 2 seconds and 1 second respectively.

@mlubin did a quick review. He found type annoations and the @expression macro could provide a 20% performance boost, but thought that overall model build time is most likely related to this issue.

powermodels-speed-test.zip

[odow]

Closing this for a few reasons:

• No one has reported similar concerns in > 2 years
• Introducing CrazyDict is going to lead to more complexity
• There are strong reasons to use OrderedDict (reproducibility of expressions) which outweighs the performance concerns.

I think in this case we're going to be unavoidably slower than 0.18, but that's a trade-off we made for using OrderedDict instead of pushing terms into a vector and then processing them later.

[odow]

This came up again in https://github.com/jump-dev/JuMP.jl/issues/3729.

We should investigate other approaches for having a "small dict" as the backing data structure in AffExpr for the common case of an affine expression with one or two elements. (See MOI.Utilities.CleverDict for a related example.)