[FileFormats.MPS]: avoid creating list of variable names

[mlubin]

The MPS writer has quadratic-ish performance because it creates GC-tracked strings for every variable and constraint. This PR shows one way we could skip this: generate the generic names on demand.

I didn't implement it for constraints because they need fancier code to deal with the constraint type parameters efficiently.

Potential alternatives:

• Use fixed-length strings as provided by WeakRefStrings
• Use WeakRefStrings.StringArray

Before:

148.861351 seconds (472.59 M allocations: 38.948 GiB, 40.91% gc time, 2.87% compilation time)

After:

109.157014 seconds (552.84 M allocations: 40.555 GiB, 21.95% gc time, 3.86% compilation time)

If we extrapolate, the version that does this approach for constraints would be around 70 sec, so we'd get a 2x speed up on this one example and better asymptotic performance.

[odow]

I didn't think to test this. I just assumed that one list of strings would be better than needing to repeatedly query VariableName. Julia really doesn't like lots of Strings...

[mlubin]

Querying VariableName is a problem too, that still forces you to create one string per variable.

[odow]

that still forces you to create one string per variable.

Yeah, which explains the increase in allocations. But I guess they are short-lived. The GC just doesn't like long-lived GC objects.

[mlubin]

To clarify, the issue isn't creating one string per variable, the issue is having O(num_variable) strings in existence simultaneously.

[odow]

the issue is having O(num_variable) strings in existence simultaneously.

Yeah.

I didn't implement it for constraints

Is there a similar thing to do for the constraints? Perhaps just changing the generic_names?

[mlubin]

We need a type-stable function mapping a ConstraintIndex{F,S} to its generic name.

[mlubin]

I hacked at this a bit more, but the constraint side is harder than I expected. The problem is the string identifiers used in the constraint matrix transpose code: https://github.com/jump-dev/MathOptInterface.jl/blob/b64dbe150ce54282718dd8d70d7a52cdfed5965f/src/FileFormats/MPS/MPS.jl#L479-L481

I tried something like:

Dict{Tuple{Type,Type}, Vector{Vector{Tuple{Int64, Float64}}}}()

where we first breakdown by (F,S) then list the coefficients by column. This isn't great because requires a fair amount more memory usage and didn't seem to make things faster anyway.

We really just want to have all constraint types to share the same index space and just do a sparse matrix transpose to get the column-wise format, similar to the type of manipulations that solver interfaces do.

That's about as far as I can push for now.

[odow]

The flat linear constraint space was what I started to do in https://github.com/jump-dev/MathOptInterface.jl/pull/2422.

But now I know the big Vector{String}s are a bad idea, let me have another go. It's probably why I got only a modest improvement.

[mlubin]

Is the plan to land this instead of https://github.com/jump-dev/MathOptInterface.jl/pull/2422?

[odow]

Is the plan to land this instead of https://github.com/jump-dev/MathOptInterface.jl/pull/2422?

I think yes. For now, this PR is an improvement. We should only move forward with #2422 if it is demonstrably better than this. #2422 is also missing a lot of things like support for quadratics, SOS, indicator, and reading.

[mlubin]

Fair enough. Do we know what's going on with the nightly CI failure?

[odow]

No, there have been a few failures. Also in MutableArithmetics: https://github.com/jump-dev/MutableArithmetics.jl/actions/runs/7892806791/job/21540090078?pr=257. I'll take a look.

[odow]

Your first commit to MOI in a while!