SymbolicJacobian.generateSparsePattern scales as O(N^2)

[Francesco Casella]

Please check ​ScalableTestSuite.Electrical.DistributionSystemAC.ScaledExperiments.DistributionSystemLinearIndividual_N_56_M_56. The code generation fails with

Warning: Out of memory! Faking a stack overflow.
[/var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/Compiler/BackEnd/BackendDAEUtil.mo:7076:3-7076:155:writable] Error: Internal error Stack overflow in BackendDAEUtil.getSolvedSystem...
[bt] #1 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaRuntimeC.so(mmc_setStacktraceMessages_threadData)
[bt] #2 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaRuntimeC.so(mmc_do_stackoverflow)
[bt] #3 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaRuntimeC.so(GC.set.max.heap.size)
[bt] #4 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaCompiler.so(SymbolicJacobian.generateSparsePattern)
[bt] #5 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaCompiler.so(SymbolicJacobian.detectSparsePatternODE)
[bt] #6 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaCompiler.so(BackendDAEUtil.postOptimizeDAE)
[bt] #7 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaCompiler.so(BackendDAEUtil.getSolvedSystem)
[bt] #8 /var/lib/hudson/slave/workspace/OpenModelica_TEST_LIBS/OpenModelica/OMCompiler/build/bin/../lib/x86_64-linux-gnu/omc/libOpenModelicaCompiler.so(SimCodeMain.translateModel)

From what I understand the issue is with SymbolicJacobian.generateSparsePattern, which is the last back-end function called before the out-of-memory exception is thrown and catched in disguise of a stack overflow.

The ​M_28_N_28 and ​M_40_N_40 logs report:

symbolicJacobian (simulation): time 6.066/47.78, allocations: 309.2 MB
symbolicJacobian (simulation): time 28.94/121.6, allocations: 0.9772 GB

showing that execution time and memory allocations grow much faster than I'd expect, since the number of non-zero elements in the Jacobian of this system is O(N). I guess there is some sub-optimal handling of lists somewhere that scales as O(N²).

@wbraun, I understand this is recent work of yours, would you mind having a look?

@hkiel, would you be interested in trying to fix this?

Thanks!

[Francesco Casella]

Rescheduled to 1.14.0 after 1.13.0 releasee

[Francesco Casella]

Releasing 1.14.0 which is stable and has many improvements w.r.t. 1.13.2. This issue is rescheduled to 1.16.0

[Francesco Casella]

Retargeted to 1.17.0 after 1.16.0 release

[Francesco Casella]

Retargeted to 1.18.0 because of 1.17.0 timed release.

[Francesco Casella]

Ticket retargeted after milestone closed