Fiddling with the coloring

[gdalle]

Continuing the conversation in #275 on coloring improvements, here is something else you can try to see if it makes a difference in sparse autodiff efficiency:

using StableRNGs
# try the best of several orders
coloring_algorithm = GreedyColoringAlgorithm((
    NaturalOrder(),
    LargestFirst(),
    SmallestLast(),
    IncidenceDegree(),
    DynamicLargestFirst(),
    RandomOrder(StableRNG(0), 0)
))

Efficiency can be judged by

ncolors(hess_prep)

[franckgaga]

Thanks for the follow up @gdalle!

I tried all of them on the pendulum case study and SmallestLast() did reduces the number of colors in some cases, e.g. with the custom nonlinear constraints on power delivery, which is great since it's the hardest/slowest problem in my benchmark suite for the nonlinear cases. From 40 colors to 2 colors in the Hessian of the Langragian function. I might change the default Hessian backend when hessian=true. I would personally not consider this as a breaking change since it's just a performance tune-up.

[franckgaga]

Benchmark-wise, the custom nonlinear constraint case study is now 2.25 times faster.

[gdalle]

Note that you don't need to try all of them on a new problem, if you list them all as a tuple inside the coloring algorithm we'll try them all for you (at a cost that is presumably negligible)

[franckgaga]

Oh, so the new default value could be "try them all", since the cost is only paid at preparation ?

[gdalle]

Probably, yes. You can also try the new OptimalColoringAlgorithm when your instances are small enough (doesn't work for the Hessian yet)

[franckgaga]

BTW will you release a new version of DI.jl soon ?

Because the option postprocessing=true seems to help in reducing the number of allocations, so I might default to this and bump DI.jl compat entry.

[gdalle]

Yeah I was waiting on the Symbolics CompatHelper PR to pass CI. For some reason CI has been having a lot of network connection errors lately, I have to restart nearly every run manually at least once for DI's tests, which slows down my process a bit. It will be out this weekend though

[gdalle]

Why does your sparse Hessian allocate at all though?

[franckgaga]

Why does your sparse Hessian allocate at all though?

Good question! I'm not sure why, I will investigate.

[franckgaga]

Yeah I was waiting on the Symbolics CompatHelper PR to pass CI. For some reason CI has been having a lot of network connection errors lately, I have to restart nearly every run manually at least once for DI's tests, which slows down my process a bit. It will be out this weekend though

Yeah I experienced similar issues! Although I have less CI jobs in my repo, so it's presumably less frequent than DI.jl repo.

[franckgaga]

Why does your sparse Hessian allocate at all though?

Good question! I'm not sure why, I will investigate.

So I wanted to investigate on this. It's probably related to the fact that some colors are now "0". To verify this I tried row_colors and column_colors on hessian preparation objects but there is no method defined for this. The error is:

ERROR: MethodError: no method matching row_colors(::DifferentiationInterfaceSparseMatrixColoringsExt.SMCSparseHessianPrep{…})
The function `row_colors` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  row_colors(::DifferentiationInterface.SparseJacobianPrep)
   @ DifferentiationInterfaceSparseMatrixColoringsExt ~/.julia/packages/DifferentiationInterface/eIcZD/ext/DifferentiationInterfaceSparseMatrixColoringsExt/DifferentiationInterfaceSparseMatrixColoringsExt.jl:25
  row_colors(::AbstractColoringResult{s, :row}) where s
   @ SparseMatrixColorings ~/.julia/packages/SparseMatrixColorings/nypBU/src/result.jl:120
  row_colors(::SparseMatrixColorings.BicoloringResult)
   @ SparseMatrixColorings ~/.julia/packages/SparseMatrixColorings/nypBU/src/result.jl:682

Stacktrace:
 [1] macro expansion
   @ ./show.jl:1270 [inlined]
 [2] get_nonlinobj_op(mpc::NonLinMPC{…}, optim::Model)
   @ ModelPredictiveControl ~/.julia/dev/ModelPredictiveControl/src/controller/nonlinmpc.jl:662
 [3] init_optimization!(mpc::NonLinMPC{…}, model::NonLinModel{…}, optim::Model)
   @ ModelPredictiveControl ~/.julia/dev/ModelPredictiveControl/src/controller/nonlinmpc.jl:573
 [4] (NonLinMPC{…})(estim::UnscentedKalmanFilter{…}, Hp::Int64, Hc::Int64, nb::Vector{…}, weights::ModelPredictiveControl.ControllerWeights{…}, JE::ModelPredictiveControl.var"#NonLinMPC##12#NonLinMPC##13", gc!::typeof(gc!), nc::Int64, p::Int64, transcription::MultipleShooting, optim::Model, gradient::AutoForwardDiff{…}, jacobian::AutoSparse{…}, hessian::AutoSparse{…}, oracle::Bool)

[...]

Is it expected?

[gdalle]

A Hessian has no row colors, because they're equivalent to columns colors, so by symmetry only column colors need to be defined. It's an arbitrary API choice, I think it is documented in the ColoringProblem docstring.
I don't see how zero colors would cause allocations though

[franckgaga]

Okay, thanks. Weirdly there is no zero color after post-processing. The the column colors are identical with or without post-processing.

So the allocations change only because prepare_hessian produce different allocation sizes with and w/o postprocessing=true:

  0.027149 seconds (61.20 k allocations: 10.040 MiB) # without postprocessing=true
Simulation results of NonLinMPC with 1 time steps.

  0.027258 seconds (61.20 k allocations: 9.513 MiB) # with postprocessing=true
Simulation results of NonLinMPC with 1 time steps.

So does not worth changing the default for this option.

[gdalle]

Ah yes, the preprocessing does more work and thus allocates more, but it hardly matters since it's a one-shot cost. In this specific case it doesn't seem to bring any benefits but it doesn't hurt to leave it on by default