SimCode scales as O(N^2) in models with many when clauses and events

[casella]

Consider these two models from the ScalableTestSuite

model ManyEvents "Model with many events in when clauses"
  parameter Integer N;
  Real x[N](each start = 0, each fixed = true);
  Boolean e[N](each start = false, each fixed = true);
equation
  for i in 1:N loop
	der(x[i]) = 1/i;
	when x[i] > 1 then
	  e[i] = true;
	end when;
  end for;
end ManyEvents;

model ManyEventsManyConditions "Model with many events in when clauses and a when clause with many triggering conditions"
  parameter Integer N;
  Real x[N](each start = 0, each fixed = true);
  Boolean e[N](each start = false, each fixed = true);
  Integer v(start = 0, fixed = true);
equation
  for i in 1:N loop
	der(x[i]) = 1/i;
	when x[i] > 1 then
	  e[i] = true;
	end when;
  end for;
  when e then
	v = pre(v) + 1;
  end when;
end ManyEventsManyConditions;

It is apparent that the second one has one additional scalar equation, whose when clause is triggered by a vector e with N components.

This is the performance of SimCode: create system equations on my pc for the first model

N	Time [s]
1000	4.3
2000	18.0
4000	87.6

which scales as O(N^2.5). For the second model, instead, I get:

N	Time [s]
1000	0.02
2000	0.05
4000	0.14

which seems quite weird, as a model with one additional equation takes two order of magnitudes less time.

This actually happens at the expense of the time spent by encapsulateWhenConditions, see #4005.

Is there a way to avoid the blow up with N of the combined SimCode and encapsulateWhenConditions execution time?

[casella]

Status update:

ManyEventsManyConditions is now fine. After fixing #4005, neither the encapsulateWhenConditions function nor SimCode do blow up.

Regarding ManyEvents, SimCode now takes O(N²) time on libraries.openmodelica.org:

N	Time [s]
1000	1.4
2000	8.1
4000	35.4
8000	137.6

Still something badly wrong in there, probably a list not handled correctly.

[casella]

Status update: regarding ManyEvents, the situation with SimCode execution times is unchanged.

Any chance to fix this?

[casella]

Milestone moved to 1.13.0 due to 1.12.0 already being released.

[hkiel]

For ManyEvents, SimCode now seems to be linear:

N	Time [s]
4000	0.9565
8000	2

Shall we close this ticket?

[casella]

Indeed. I'm not sure when this was actually fixed, I missed the change as I was recently focusing more on the new front end performance.

Thanks for pointing this out!

[wbraun]

Replying to hkiel:

For ManyEvents, SimCode now seems to be linear:

N	Time [s]
4000	0.9565
8000	2

Shall we close this ticket?

Which run did you observed?
Since in the last ​ODE ScalableTestsuite it seems to be still an issue:

N	Time [s]
2000	5.39
4000	27.95
8000	123.08

[hkiel]

@wbraun I'm referring to ​https://test.openmodelica.org/libraries/ScalableTestSuite_Experimental/BuildModelRecursive.html 2018-03-20 with --daeMode=new

[hkiel]

This issue is not fixed. It is only hidden in daeMode.

[wbraun]

Ah, so it's fixed in the DAEmode, but not in ODE.
I think the issue is actually that we generate in SimCode phase all equation at least two times, see the function
​createEquationsForSystems.

[casella]

Of course it would be good that this issue is fixed for ODE mode also.

On the other hand, I guess that when the size of the problem is large enough for this issue to be relevant, DAE mode may be necessary anyway, and that works fine, so I would consider this "almost" fixed.

It is instead absolutely essential to fix #3905, otherwise large systems with events are not really feasible in OMC.

[casella]

Rescheduled to 1.14.0 after 1.13.0 releasee

[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

[casella]

Retargeted to 1.17.0 after 1.16.0 release

[casella]

Retargeted to 1.18.0 because of 1.17.0 timed release.

[casella]

Ticket retargeted after milestone closed