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 #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.)

[joaquimg]

If we implement our own OrderedDict, we could do it so it does not allocate if we have very small (< 2 terms?) affine expressions. Side benefit is that we could (?) save a hash here:

JuMP.jl/src/aff_expr.jl

Line 25 in b734e12

if index <= 0 # Key does not exist. We pay the penalty of a second lookup.

[odow]

I'm very hesitant to roll our own OrderedDict.

I'd be more in favour of swapping to something like https://github.com/andyferris/Dictionaries.jl if it was faster.

[odow]

I looked at changing to Dictionaries, but it is quite disruptive because:

• You can't do dict[k] = v unless k exists. You need to do insert!(dict, k, v)
• Iteration loops over values, so no for (k, v) in dict, you need for (k, v) in pairs(dict)
• We have explicitly documented OrderedDict, so this could be considered breaking

JuMP.jl/src/aff_expr.jl

Lines 105 to 138 in b734e12

	"""
	mutable struct GenericAffExpr{CoefType,VarType} <: AbstractJuMPScalar
	constant::CoefType
	terms::OrderedDict{VarType,CoefType}
	end
	An expression type representing an affine expression of the form:
	``\\sum a_i x_i + c``.
	## Fields
	* `.constant`: the constant `c` in the expression.
	* `.terms`: an `OrderedDict`, with keys of `VarType` and values of `CoefType`
	describing the sparse vector `a`.
	## Example
	```jldoctest
	julia> model = Model();
	julia> @variable(model, x[1:2]);
	julia> expr = x[2] + 3.0 * x[1] + 4.0
	x[2] + 3 x[1] + 4
	julia> expr.constant
	4.0
	julia> expr.terms
	OrderedCollections.OrderedDict{VariableRef, Float64} with 2 entries:
	x[2] => 1.0
	x[1] => 3.0
	```
	"""