[Containers] use OrderedDict as the data structure for SparseAxisArray

[odow]

Closes #3678 Closes #3680

The issue is still really that SparseAxisArray is not a regular n-dimensional Array. Each slice can have a different length with different axes. It doesn't make sense to support a lot of operations with it.

The only thing that we should support are vectors.

This PR has the problem that the current iteration order is the transpose of what it "should" be (row-major, instead of column-major).

This is needed because the second and subsequent dimensions can depend on the first and prior. So it isn't really meaningful to iterate "down" the first index holding all else constant.

I can see this being a constant source of future problems.

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (a21e616) 98.33% compared to head (57eb71c) 98.36%. Report is 1 commits behind head on master.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #3681 +/- ## ========================================== + Coverage 98.33% 98.36% +0.03% ========================================== Files 43 43 Lines 5696 5698 +2 ========================================== + Hits 5601 5605 +4 + Misses 95 93 -2 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[joaquimg]

Shouldnt the iteration ordering comment be part of docs?

[odow]

Yeah. I guess my first question is: should we do this?

If we do, we need more docs on the specifics of the order and slicing, and when things can go wrong.

Also: https://github.com/jump-dev/JuMP.jl/actions/runs/7944311147

[joaquimg]

The slicing issues you showed seem pretty dangerous.

The only downside would be the performance penalty? Did you benchmark it?

[odow]

The only downside would be the performance penalty? Did you benchmark it?

I didn't benchmark it, but I think the risk of incorrect usage outweighs the cost.

It's probably slower because creating an ordered dict is slower. But it shouldn't be too bad.

[joaquimg]

I agree correctness must come first.

Is there any other downside?

[odow]

I added a warning.

I guess the main downside is that existing iteration orders may change. But that could have happened anyway, because we used a Dict.

[odow]

Before merging, we should check if we can trigger issues like https://github.com/JuliaCollections/OrderedCollections.jl/issues/87

We should also audit open issues in OrderedCollections for other potential problems.

[odow]

I audited all the open issues. I think we're safe from the delete segfault because you cannot delete elements in a SparseAxisArray.

The most up for debate issue is: https://github.com/JuliaCollections/OrderedCollections.jl/issues/82

julia> Containers.@container(x[k in 1:2], k, container = SparseAxisArray)
JuMP.Containers.SparseAxisArray{Int64, 1, Tuple{Int64}} with 2 entries:
  [1]  =  1
  [2]  =  2

julia> Containers.@container(y[k in 2:-1:1], k, container = SparseAxisArray)
JuMP.Containers.SparseAxisArray{Int64, 1, Tuple{Int64}} with 2 entries:
  [2]  =  2
  [1]  =  1

julia> x == y
true

But this coincidentally just reproduces the behavior of the current JuMP:

julia> Containers.@container(x[k in 1:2], k, container = SparseAxisArray)
JuMP.Containers.SparseAxisArray{Int64, 1, Tuple{Int64}} with 2 entries:
  [1]  =  1
  [2]  =  2

julia> Containers.@container(y[k in 2:-1:1], k, container = SparseAxisArray)
JuMP.Containers.SparseAxisArray{Int64, 1, Tuple{Int64}} with 2 entries:
  [1]  =  1
  [2]  =  2

julia> x == y
true

[mlubin]

https://github.com/JuliaCollections/OrderedCollections.jl/issues/82 isn't too concerning to me.

[odow]

So good to merge then?