JuMP (0.18): summing up elements of solution vector allocates memory?

Specific Domains Optimization (Mathematical)
1

Dear folks,
I observe a strange behavior (note that the following snippets are embedded in a function): let x be some decision vector of size n. Then,

sum_x = 0.0
x_val = getvalue( model[:x] )
println("typeof x_val: ", typeof(x_val))
@time for i=1:n
          sum_x += x_val[i] #this sum allocates mem
      end

returns

typeof x_val: Array{Float64,1}
  0.015041 seconds (299.49 k allocations: 4.570 MiB, 69.16% gc time)

so memory is allocated, and I do not understand why. I also tried x_val = deepcopy( getvalue( model[:x] ) ) with the same result.

In contrast:

sum_x = 0.0
foo = rand(Float64, n)
println("typeof foo: ", typeof(foo))
@time for i=1:n
          sum_x += foo[i]  #this sum does not
      end

outputs

typeof foo: Array{Float64,1}
  0.000060 seconds

which does not allocate memory and is much faster.
Do you have any suggestions why this is the case, and how to work with (intermediate) JuMP results as fast as in the second example?

Thanks in advance!

2

You appear to benchmarking in global scope. That will not give you the results you want.

You should start by reading the performance tips in the manual: Performance Tips · The Julia Language

3

Thank you, but it is not in the global scope as far as I can assess it. Here is the whole example (a simple knapsack problem), which leads to the same output:

typeof x_val: Array{Float64,1}
  0.019753 seconds (299.49 k allocations: 4.570 MiB, 64.55% gc time)
typeof foo: Array{Float64,1}
  0.000060 seconds

Code:

using JuMP
using CPLEX
using Random
using LinearAlgebra

#MEMORY TEST
function memTest( model, n::Int )
  sum_x = 0.0
  x_val = getvalue( model[:x] )
  println("typeof x_val: ", typeof(x_val))
  @time for i=1:n
          sum_x += x_val[i] #this sum allocates mem
        end

  sum_x = 0.0
  foo = rand(Float64, n)
  println("typeof foo: ", typeof(foo))
  @time for i=1:n
            sum_x += foo[i]  #this sum does not
        end
end

#MAIN
function main()
  Random.seed!(1)
  n = 100000          #nvars
  C = 500000          #rhs
  v = rand(1:10, n)   #value
  w = rand(1:10, n)   #weights

  #BUILD AND SOLVE KNAPSACK
  model = Model( solver=CplexSolver() )
  @variable( model, x[1:n], Bin )
  @objective( model, Max, dot(v, x) )
  @constraint( model, dot(w, x) <= C )
  status = solve(model)
  memTest( model, n )
end

main()
4

Try running @code_warntype on your function. You will probably see that the type of x_val cannot be inferred, which is causing some overhead for accessing that value later in the function.

You can either use a type annotation or a function barrier to help with performance if that is indeed the case (see the Performance Tips for details on all of this).

5

The getvalue call might be type unstable. Check with @code_warntype and eventually use a function barrier (described in performance tips in the manual).

6

Do you mean

x_val = @code_warntype getvalue( model[:x] )

or

@code_warntype memTest( model, n )

?
Anyway - in both cases it outputs a long list which looks something like this (here, the beginning of the list of the first option):

Body::Array{Float64,1}
1 ── %1   = (Base.arraysize)(arr, 1)::Int64
│    %2   = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Array{Float64,1}, svec(Any, Int64), :(:ccall), 2, Array{Float64,1}, :(%1), :(%1)))::Array{Float64,1}
│    %3   = (Base.arraylen)(%2)::Int64
│    %4   = (%3 === 0)::Bool
└───        goto #3 if not %4
2 ──        return %2
3 ──        (Base.arraysize)(arr, 1)
│    %8   = (Base.arrayref)(true, arr, 1)::Variable
│    %9   = (Base.getfield)(%8, :m)::Model
│    %10  = (Base.getfield)(%9, :varData)::IdDict
│    %11  = (JuMP.haskey)(%10, arr)::Any
│    %12  = (Base.arraysize)(arr, 1)::Int64
│    %13  = (Base.slt_int)(%12, 0)::Bool
│    %14  = (Base.ifelse)(%13, 0, %12)::Int64
│    %15  = (Base.slt_int)(%14, 1)::Bool
└───        goto #5 if not %15
4 ──        goto #6
.
.
.

What does it mean? I receive values from getvalue() - isn’t there an option to just make a copy of these values and work with it “independently”?

7

The second one, which will show that getvalue(model[:x]) is returning a type which is probably inferred as ::Any. Again, this is explained in much more detail in the performance tips, so please check those out: Performance Tips · The Julia Language

There’s no need for a copy. The problem is that at compile-time, the type of that variable cannot be determined, so the compiler cannot generate optimally efficient code that uses it. Again, check out the performance tips, specifically function barriers and type annotations, either of which will work in this situation.

1 Like
8

It seems that you are right - with the second option the output is like:

Body::Nothing
1 ─── %1   = invoke Base.getindex(_2::Model, :x::Symbol)::Any
│     %2   = (Main.getvalue)(%1)::Any

which seems to me that getvalue() returns type ::Any.

I will check out ‘function barriers’ and ‘type annotations’ tomorrow, and give an update.
Thank you!

9

Thank you again @rdeits. Type annotations do the trick. I just added a function

function annotate( a::Array{Float64,1} )
 return a::Array{Float64,1}
end

called by x_val = annotate( getvalue( model[:x] ) ) and obtained:

typeof x_val: Array{Float64,1}
  0.000060 seconds
typeof foo: Array{Float64,1}
  0.000060 seconds

:slight_smile:

10

For what its worth, the new version of JuMP (0.19) is now type-stable for these sorts of getters.

1 Like