id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc
5107	SymbolicJacobian.generateSparsePattern scales as O(N^2)	Francesco Casella	Willi Braun	"Please check [https://libraries.openmodelica.org/branches/master/ScalableTestSuite_noopt/files/ScalableTestSuite_noopt_ScalableTestSuite.Electrical.DistributionSystemAC.ScaledExperiments.DistributionSystemLinearIndividual_N_56_M_56.err 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 [https://libraries.openmodelica.org/branches/newInst/ScalableTestSuite_noopt/files/ScalableTestSuite_noopt_ScalableTestSuite.Electrical.DistributionSystemAC.ScaledExperiments.DistributionSystemLinearIndividual_N_28_M_28.err M_28_N_28] and [https://libraries.openmodelica.org/branches/newInst/ScalableTestSuite_noopt/files/ScalableTestSuite_noopt_ScalableTestSuite.Electrical.DistributionSystemAC.ScaledExperiments.DistributionSystemLinearIndividual_N_40_M_40.err 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^2^).

@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!"	defect	new	high		Backend				Henning Kiel