Hello all. I’ve finally had a chance to sit down and look carefully at some of the code in JuMP 0.19. In my work I very frequently have to do problems with \sim 10^6 variables. Obviously implementing these involves a lot of linear algebra, and I frequently find that, while I’m very grateful to have the specialized code that already exists within JuMP, it doesn’t quite cut it for problems of this scale. So, I wanted to open this thread to get some feedback from the JuMP devs on what current thinking and future plans are, and to find out where I might be able to be of assistance.
It seems to me that the fundamental problem here is that all of the
AbstractJuMPScalar objects are mutable objects which typically wind up using heap allocated memory. The experimenting I’ve done so far would suggest that it would probably be sufficient if we could build ways to allocate these all at once during linear algebra operations. As a simple example of what I’m talking about, see
julia> @benchmark begin A = Int for i ∈ 1:100 push!(A, 1) end end BenchmarkTools.Trial: memory estimate: 2.27 KiB allocs estimate: 7 -------------- minimum time: 683.370 ns (0.00% GC) median time: 713.286 ns (0.00% GC) mean time: 799.731 ns (8.64% GC) maximum time: 304.204 μs (99.63% GC) -------------- samples: 10000 evals/sample: 154 julia> @benchmark ones(Int, 100) BenchmarkTools.Trial: memory estimate: 896 bytes allocs estimate: 1 -------------- minimum time: 75.177 ns (0.00% GC) median time: 80.265 ns (0.00% GC) mean time: 99.438 ns (16.71% GC) maximum time: 49.149 μs (99.41% GC) -------------- samples: 10000 evals/sample: 972
The simplest example of this is the inner product here. What this does is create a
AbstractJuMPScalar “zero” and then append to it one term at a time. Instead, it would be more efficient to allocate it all at once. Essentially the same thing is happening in matrix multiplication here. I think implementing a more efficient version should be relatively straightforward, but I would be interested to hear if there are any pitfalls that make this much more complicated than I think it is.
Another issue is keeping around lots useless
AffExpr([x], [0.0], 0.0). You can wind up in some situations where there’s simply a huge number of these lying around, and you are spending a huge amount of computation time adding them to some expression. I remember @miles.lubin mentioning that he was considering turning
Dicts rather than
Vectors, but I haven’t seen an issue in the JuMP repo. Are there any concrete plans for this? If effort is put into improving the linear algebra it would probably be better to do both of these things at the same time.
Anyway, thanks all, looking forward to JuMP being in a state where it really flies on big problems, and I hope I can be helpful in getting it there. If I’m just way behind and much of this is being worked on already, all the better!