jump-dev / jump-dev/JuMP.jl

Performance of small constraints

Open
#1,654 8 comments 1 reaction 0 assignees View on GitHub
Type: Performance
Dominant language
Julia
Stars
2.5k
Forks
428
Avg merge
18h 10m
Merged PRs (30d)
28

Description

Creating small constraints like
```julia
@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
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.
```julia
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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.