Repository navigation
Benchmarking against JuMP: faster on Jacobians, slower on Hessians #118
Description
Here are the results of a benchmark between SCT and JuMP sparsity detection, on the suite of OptimizationProblems. The benchmark code is at https://github.com/gdalle/SparsityDetectionComparison
Provided that @amontoison validates the benchmark as fair, we are:
- uniformly faster than JuMP for Jacobians
- often much slower (up to almost 100x) for Hessians
Note that these benchmarks are done without any optimization, for instance on the set types in the detector. And our Hessian code is still pretty slow, but that's expected and probably fixable. Stay tuned!
Activity
Vaibhavdixit02 commentedon Jun 5, 2024
Can you say a bit more about this?
gdalle commentedon Jun 5, 2024
Damn, Vaibhav is watching the repo like a hawk.
I'll let @adrhill fill in the gaps, but essentially, the problem comes from allocations inside Hessian tracing, which are much more expensive than inside Jacobian tracing.
Currently, the Hessian patterns are encoded as sets of tuples, because it fits well into the theoretical part of our paper. But we have other storage ideas, including some that would sacrifice some accuracy for huge speedups. The main one is storing a single Hessian pattern for all scalar quantities involved in the algorithm. Resulting memory savings would be absolutely off-the-charts, and I wouldn't be surprised if this got us within reach of JuMP.
[-]Benchmarking against JuMP[/-][+]Benchmarking against JuMP: faster on Jacobians, slower on Hessians[/+]Vaibhavdixit02 commentedon Jun 5, 2024
😂 yeah you guys are pretty much helping solve problems that bugged me for a year so I try to keep up (I know my integration attempt might not make it seem like that but I have good reasons for the delay sorry 😭)
This would be tremendously useful in some cases where the pattern changes and it's recomputed (so it doesn't need to be very accurate)
This makes sense, thanks for the insight
gdalle commentedon Jun 5, 2024
That's precisely the approach we're taking in our paper with Adrian. Our gamble is to make sparsity pattern detection so fast that it's even worth it when you do it every time due to pattern changes.
adrhill commentedon Jun 5, 2024
Agreed!
As Guillaume already mentioned, we so far focussed on correctness over performance. In our current implementation, each scalar value (each tracer) carries an index set that indicates non-zero derivatives. To obtain accurate results over branching compute graphs, these sets are never mutated in place. Even within this accurate approach, we have very low-hanging fruit to pick, like smarter unions over (partially) empty index sets (#80).
A big performance gain could come from adding methods on the array-level, e.g. to LinearAlgebra (#115). Currently, operations like dense matrix-vector products of tracers dispatch down to scalar operations. Instead, we could be a lot smarter in the way we compute unions of index sets.
Finally, at the cost of accuracy, an index set that is "shared globally" over the entire computation would result in large memory savings and huge performance increases. Our move away from simple
AbstractSets has started in #119.gdalle commentedon Jun 6, 2024
Here is the same benchmark but where I added Symbolics. I wasn't able to run every problem in a reasonable amount of time, missing the last few. If the Pluto build of https://github.com/gdalle/SparsityDetectionComparison ever finishes, we'll have them all
adrhill commentedon Jun 6, 2024
Skimming the benchmarking notebook, it also uses the default
TracerSparsityDetectorhttps://github.com/gdalle/SparsityDetectionComparison/blob/34782bce3ac5082dd3132c3168a3750b2c7ca527/index.jl#L169
which defaults to
BitSetfor Gradient information andSet{Tuple{Int, Int}}for Hessian information:https://github.com/adrhill/SparseConnectivityTracer.jl/blob/178681523632cd92a7ea8168d0bc64ef43f4a28d/src/adtypes.jl#L39
If other available set types are more performant, we should change this default.
adrhill commentedon Jun 6, 2024
FYI @gdalle: Decent speed-ups (up to a factor of 2) on some set types in #119 (comment).
gdalle commentedon Jun 7, 2024
Nearly complete benchmark on https://gdalle.github.io/SparsityDetectionComparison/
I only removed the tetra_stuff instances because at least one of them caused CI to still be running after 4h (due to Symbolics).
amontoison commentedon Jun 7, 2024
Excellent work Guillaume! 🚀
gdalle commentedon Jun 7, 2024
I can't help but notice (after including the number of variables and constraints in the plot) that most of the optimization problems in the suite are rather small, even tiny