Setting names is very slow, does a lot of work, some of it redundant

[IainNZ]

In particular, the code here:
jump-dev/JuMP.jl#1402 (comment)
stress tests the setname logic and shows it allocates quite a bit, and takes a lot of time.

[mlubin]

https://github.com/JuliaOpt/MathOptInterface.jl/blob/c164eabcff67e6d96341e69eb053e6fc01b5e3a3/src/Utilities/model.jl#L188-L191

The code here does a hash and lookup on the name 3 times if I'm counting correctly between the cangets and the get.

Also is this string always constructed or only if the error case hits?
https://github.com/JuliaOpt/MathOptInterface.jl/blob/c164eabcff67e6d96341e69eb053e6fc01b5e3a3/src/Utilities/model.jl#L162

[IainNZ]

More tests - commenting out the checks actually doesn't affect run time much - rather, the two lines of storing stuff does.

[mlubin]

We're also missing hash implementations for the index types. That made a big difference in my previous benchmarks.

[IainNZ]

struct VariableIndex
    value::Int64
end
Base.hash(index::VariableIndex, h::UInt) = hash(index.value, h)

const NAMES = String[string("vars", "[", i, "]") for i in 1:10^6]

function run_moi_str_test()
    model = VariableIndex[]
    varnames = Dict{VariableIndex, String}()
    namesvar = Dict{String, VariableIndex}()
    for i in 1:10^6
        vi = VariableIndex(i)
        push!(model, vi)
        name = string("vars", "[", i, "]")
        varnames[vi] = name
        namesvar[name] = vi
    end
end

• As is, this is about 1.95 seconds, 8e6 allocations.
  • Julia 0.7 is a bit faster, ~1.9 seconds.
• Replacing name = string(i) gives 0.7 seconds, 2e6 allocations.
  • Julia 0.7 is a bit faster, ~0.65 seconds.
• Without the custom hash there are more allocations, but not in a way that seems to affect runtime.
• Replacing name = NAMES[i] gives ~0.8 seconds, 132 allocations (resizing data structures?)
• 75% of time comes from name-as-key, 25% from vi-as-key.

[tkoolen]

Does varnames have to be a Dict? Why not use a Vector{String} indexed by VariableIndex? Typically, the VariableIndexes for a model will be contiguous, right? Or if you want to keep the AbstractDict semantics, you could use something like https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/9c96a4420f46e74ce3fa009a7453455bc68ab8b6/src/custom_collections.jl#L105-L131.

[blegat]

When you delete variables, there will be holes, how do you handle that ?

[tkoolen]

I suppose either a Vector{Union{String, Nothing}} or a CardinalDict from https://github.com/JeffreySarnoff/CardinalDicts.jl?

[blegat]

We will need to benchmark

name = vec[index]
if name === nothing
    throw(MOI.InvalidIndex(index))
end
return name::String

against

if haskey(cardinal_dict, index)
     throw(MOI.InvalidIndex(index))
end
return cardinal_dict[index]

[odow]

Closing because all the bottleneck is setting the name in the dict here:

MathOptInterface.jl/src/Utilities/model.jl

Lines 353 to 355 in f49fde0

	function MOI.set(model::AbstractModel, ::MOI.VariableName, vi::VI, name::String)
	model.var_to_name[vi] = name
	return model.name_to_var = nothing # Invalidate the name map.

function run_test()
    model = JuMP.Model()
    JuMP.@variable(model, vars[1:10^6])
    return model
end
run_test()
Profile.init(n=Int(1e8), delay=0.00000001)
@pprof run_test()

But even adding a million variables only takes 0.5 seconds.

julia> @time run_test();
  0.583714 seconds (6.00 M allocations: 344.590 MiB)

There are bigger fish to fry.