Expression.simplify is way too slow

[Willi Braun]

For the following models the compile time increases heavy, if one increase the size.

  model BaseModelEquations
    parameter Integer n=100; // see Backend time for 100, 200, 400
    input Real[n] u1;
    input Real[n] u2;
    output Real[n] y1;
    output Real y2;
  equation
    y1=array(if u1[i] > 0 then u1[i] else u2[i] for i in 1:n);
    y2=sum(y1);
  end BaseModelEquations;

For n=100 : timeBackend = 0.266189871
For n=200 : timeBackend = 1.490894306
For n=400 : timeBackend = 10.56719995
For n=800 : timeBackend = 82.89054140

All the time is lost by trying to simplify expressions.
Also we try to do it 3 time, once by creating the BackendDAE structure,
once directly after that and once at the end of the Backend process.

We should do it only once and perhaps we should improve Expression.simplify further anyway.

[Martin Sjölund]

We could just change the +noSimplify flag to +d=slowSimplifications, and make it default off :)

[Lennart Ochel]

The scaling seems to be not that bad. Simplify has a linear scaling w.r.t. the number of equations (based on this example, based on 4 data points ;-))

[Martin Sjölund]

No, that is not linear scaling 0.26 * 8 = 2.08, but we got 82.9. It seems to be O(n³) or maybe O(n²log(n)).
For me (total time front-end+back-end+codegen):

n	simplify1 (s)	simplify (s)
100	0.344	0.85
200	0.74	4.26
400	2.04	30.24
800	5.32	218.73

[Willi Braun]

Yes, the real mess is simplify2 in combination with simplifyBinaryCoeff.

[Martin Sjölund]

This ticket was not closed for 1.9.1, which has now been released. It was batch modified for milestone 1.9.2 (but maybe an empty milestone was more appropriate; feel free to change it).

[Martin Sjölund]

Milestone changed to 1.9.3 since 1.9.2 was released.

[Martin Sjölund]

Moved to new milestone 1.9.4

[Francesco Casella]

See also #3491

[Vitalij Ruge]

Willi, has done some anaylses for changes in ​simplify2

N	M(countOperations)	BackendTime	TotalTime
100	199	0.042735523	0.576733485
200	399	0.088144779	0.825384327
400	799	0.250593965	1.431617297
800	1599	0.976192998	3.235029631
1600	3199	5.110137451	9.466115887
3200	6399	32.870996638	42.864459504

It seems to be O(N²⁾

M = [199, 399, 799, 1599, 3199, 6399];
t = [0.042735523, 0.088144779, 0.250593965, 0.976192998, 5.110137451, 32.870996638];
plot(M,sqrt(t))

[Martin Sjölund]

Milestone pushed to 1.9.5

[Martin Sjölund]

Milestone renamed

[Martin Sjölund]

Ticket retargeted after milestone closed

[Martin Sjölund]

Milestone moved to 1.12.0 due to 1.11.0 already being released.

[Francesco Casella]

The milestone of this ticket has been reassigned to "Future".

If you think the issue is still valid and relevant for you, please select milestone 1.13.0 for back-end, code generation and run-time issues, or 2.0.0 for front-end issues.

If you are aware that the problem is no longer present, please select the milestone corresponding to the version of OMC you used to check that, and set the status to "worksforme".

In both cases, a short informative comment would be welcome.