Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance of small constraints #1654

Open
blegat opened this issue Dec 1, 2018 · 1 comment
Open

Performance of small constraints #1654

blegat opened this issue Dec 1, 2018 · 1 comment
Labels
Milestone

Comments

@blegat
Copy link
Member

@blegat blegat commented Dec 1, 2018

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.

@odow odow added the performance label Dec 8, 2018
@mlubin mlubin added this to the 1.0 milestone Feb 24, 2019
@ccoffrin

This comment has been minimized.

Copy link
Contributor

@ccoffrin ccoffrin commented Jun 1, 2019

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.