Extreme performance degradation from v0.18.5 -> v0.19

[angeris]

Heya JuMP team!

I've currently noticed a large performance regression (which has been cited in a few cases, notably #1403 and #1905). I was planning on releasing some code for a paper, which was originally written with v0.18.5, but, with the upgrade, decided to do the necessary edits for v0.19. The code is essentially (sadly :( ) unusable in its current form, due to the speed degradation.

Two MWEs showing a large difference (I will note that I'm using two slightly different environments, with Julia 1.0 and Julia 1.1)

Julia 1.0, JuMP v0.18.5. Time to complete: <2s. Roughly .0001s/constraint.

Julia 1.1, JuMP v0.19. ETA for completing this (as reported by ProgressMeter): 18 minutes. Roughly 1.3s/constraint.

The problem in question solved was much, much larger and would take several days to formulate at this pace. I'd also be happy to contribute to a fix, but I'd need to learn a bit more about profiling and performance in Julia (and definitely more about the current JuMP implementation) in order to help out!

Anyways, thank you so much for this project, it's been super useful :)

[odow]

Ouch! That degradation is pretty terrible. A few things:

• take a read of https://docs.julialang.org/en/v1/manual/performance-tips/index.html
  In particular, try to build a MWE that encapsulates everything in a function and doesn't use global variables
• Try timing L_all[i][:,j]' * nu[:,i] There have been some issues about multiplying sparse matrix transposes: Product of sparse matrix with transpose #1276, @constraint macro slow on expressions involving matrix transpose and ones #914
• Remove with_optimizer(Gurobi.Optimizer) and check that the times are the same
• Try timing a scalarized expression

  quad_cons(m, [ sum(L_all[i][k,j] * nu[k,i] for k in 1:N^2) for i=1:n_freq ], t[j])

  or even

  @constraint(m, sum(sum(L_all[i][k,j] * nu[k,i] for k in 1:N^2)^2 for i in 1:n_freq) <= t[j])

[angeris]

Ok sounds great! Thanks for the tips, @odow :)

I rewrote the (quasi-)MWE (found here) to be a little clearer and follow everything you mentioned. The timings were similar to the ones presented

guille$ julia jump-.19-sample.jl 
[ Info: Generating Matrices
[ Info: Generating model
[ Info: Timing multiply
  0.246705 seconds (697.73 k allocations: 34.940 MiB, 5.64% gc time)
  0.000104 seconds (44 allocations: 45.188 KiB)
[ Info: Normal expression
  1.800579 seconds (4.02 M allocations: 221.443 MiB, 11.00% gc time)
  0.962823 seconds (1.85 M allocations: 112.138 MiB, 11.77% gc time)
[ Info: Scalarized expression
  1.169229 seconds (2.10 M allocations: 162.935 MiB, 18.24% gc time)
  0.981009 seconds (1.91 M allocations: 153.620 MiB, 17.78% gc time)
[ Info: Fully expanded expression
  0.926208 seconds (1.88 M allocations: 102.542 MiB, 12.50% gc time)
  0.835683 seconds (1.83 M allocations: 99.909 MiB, 9.64% gc time)

So it seems that the matrix transposes, while perhaps a little slow, are generally okay. The problem I'm seeing here are the huge memory spikes and allocations when adding a constraint! I'm afraid I'm not 100% sure why this would be the case?

[odow]

I have a MWE. The issue is that the intermediate steps are collecting zero terms.

function benchmark(drop_terms::Bool = false)
    model = Model()
    @variable(model, x[1:100])
    f = (i) -> i == 1 ? 1.0 : 0.0
    y = JuMP.Val(false)
    for k in 1:100
        y = JuMP._destructive_add_with_reorder!(y, f(k), x[k])
    end
    # y has many 0.0 terms
    if drop_terms
        for (key, value) in y.terms
            if iszero(value)
                delete!(y.terms, key)
            end
        end
    end
    return JuMP._destructive_add_with_reorder!(JuMP.Val{false}(), y * y)
end

julia> @time benchmark(false)
0.093523 seconds (125.71 k allocations: 6.632 MiB)
x[1]²

julia> @time benchmark(true)
0.000100 seconds (799 allocations: 52.016 KiB)
x[1]²

Ref: #1934

[odow]

See:
https://github.com/JuliaOpt/JuMP.jl/blob/79f279addd424693c206643a7e3367e8a874f667/src/aff_expr.jl#L21-L22
Given your experience, I think the answer is "Yes". Or at least, if something like

function _add_or_set!(dict::OrderedDict{K,V}, k::K, v::V) where {K,V}
    if iszero(v)
        return dict
    end
    # TODO: This unnecessarily requires two lookups for k.
    dict[k] = get!(dict, k, zero(V)) + v
    return dict
end

[angeris]

Brilliant, thank you! That makes far more sense; I was wondering if it was a question of the matrices being large but sparse and somehow the zeros not being dropped immediately. I've been stuck in meetings all day so didn't really get a chance to try running the same code and only adding the expression if the entry is nonzero.

Anyways, thank you again @odow ! For context, these large, sparse programs come up all the time in physics and physical design problems, so this is super helpful :)

[odow]

I'm making a PR so we can discuss further.