collectInitialBindings scales as O(N^2)

[casella]

Check the log of ​ScalableTestSuite.Electrical.DistributionSystemDC.ScaledExperiments.DistributionSystemModelica_N_XX_M_XX

N	M	time
80	80	0.22
112	112	1.35

The scaling is close to O(N³) and makes this trivial function of the back-end the bottleneck for much larger models which are not included in the ScalableTestSuite.

Please make sure this method is implemented in an efficient way (see #4362).

[perost]

I tried to improve Initialization.collectInitialBindings a bit, and found that BackendEquation.addEquation was essentially linear since it iterated over the array in an attempt to find an empty slot. I fixed that, but it made no difference.

Then I noticed that the execstat for collectInitialBindings actually measure both collectInitialVarsEqnsSystem and collectInitialBindings, and the time that the collectInitialBindings function takes is actually relatively insignificant.

I improved collectInitialVarsEqnsSystem a bit by getting rid of some unnecessary tuple allocations, but that didn't do much for the scaling. collectInitialVarsEqnsSystem does a lot of traversing, and calls collectInitialVars which is rather big. collectInitialVars also creates a lot of variables that aren't used, like $PRE.cr, so it could be improved by doing the check before creating the variables. But that wouldn't affect the scaling.

[lochel]

I've improved the memory management of the equation arrays. I think it should be much better now.

[casella]

The ScalableTestSuite case now gives

N	M	time
80	80	0.25
112	112	0.66

which is only slightly superlinear. Sounds promising. I'll check out with the bigger model and report.

[casella]

The results with the bigger models are still not satisfying. A power system models with 150k equations takes 7 seconds, but a larger one with 4 times as much equations takes 150 seconds (20 times as much), which is about O(N²).

The analysis of the time spent by the method on ScalableTestSuite.Elementary.SimpleODE.ScaledExperiments.CascadedFirstOrder_N_XXX
also hints to O(N²) complexity

N	time
6400	0.44
12800	1.45
25600	6.33

[casella]

Update: with today's development version, the collectInitialBindings run on the models ScalableTestSuite.Elementary.SimpleODE.ScaledExperiments.CascadedFirstOrder_N_XXX take the following times in seconds:

N	time
6400	0.033
12800	0.074
25600	0.295

Results are much improved w.r.t. the status reported in comment:4, though from this example the asymptotic complexity is not really clear.

I looked at other large models in the library, and the situation with the scaling is still not clear. If you look at the times of ScalableTestSuite.Electrical.DistributionSystemDC.ScaledExperiments.DistributionSystemModelica_N_XXX_M_XXX, which are the largest so far in the library, you get

N	M	time
56	56	0.082
80	80	0.288
112	112	0.481

which hints at O(N). However, ScalableTestSuite.Electrical.DistributionSystemAC.ScaledExperiments.DistributionSystemLinear_N_XX_M_XX, the second largest, gives:

N	M	time
28	28	0.19
40	40	0.72
56	56	7.70

which shows asymptotic convergence ratio of O(N³). It would be interesting to investigate the structural differences of these two last two models and fix the problem with the second one.

[sjoelund.se]

Fixed with 9e2d1a7c5