Backend scaling for simple array-equation

[Martin Sjölund]

Scales to the power of 3.5... Horrible

n=50 0.231s
n=100 2s
n=150 9s
n=200 27s
n=10000 115 days

class A
  function fn
    input Real t;
    input Integer n;
    output Real out[n];
  algorithm
    out := {i*t for i in 1:n};
  end fn;
  parameter Integer n = 4000;
  Real r[n];
equation
  r = fn(time, n);
end A;

[Francesco Casella]

Update: with 1.12.0beta2, the current performance using OMEdit is

n	Time backend (s)	Memory matching and sorting (MB)	Memory total(MB)
1000	1.4	97	400
2000	3.1	376	650
3000	5.7	819	850
4000	10.4	1451	2250

Matching and sorting takes the lion's share of memory allocation. Above n = 4000 the memory consumption blows up and the PC just hangs.

Good news: scaling in terms of time is now definitely better than O(N^3.5), and it is possible to get up to n = 4000

Bad news: the memory allocation by the matching and sorting algorithm grows as O(N²) and is really huge. Why should over 1GB be spent to analyze a system with 4000 equations?

[Henning Kiel]

I committed a fix for the huge memory consumption in ​PR1900 and ​PR1902

n	Time matching and sorting (s)	Memory matching and sorting (MB)	Memory total(MB)
2000	0.35	9.8	140
4000	1.56	19.8	276
8000	6.9	40.4	545
16000	27.1	82.7	1105

[Martin Sjölund]

So PR1900 simply avoids creating a new list for absInt to treat state variables as normal variables if there are no state variables in a row. And PR1902 avoids creating a temporary list to filter out some variables.

[Henning Kiel]

Yes, and these were the culprits of O(N²) memory consumption. I suspect there are more such places in OMCompiler.

Still, there is an O(n³) algorithm at work which dominates at n=32000
I could track it down to BackendDAEEXT.matching with a matchingID of 5 ("PF+")

Is this something we can influence? Or is this 3rd party code?

[Francesco Casella]

I'm now using OMEdit v1.13.0-dev-24-g095b0ef (64-bit) connected to v1.13.0-dev-143-ged4ccd8 (64-bit), and it seems that after the last PRs, the situation has actually gotten worse.

The time spent and memory allocated by matching and sorting is roughly the same. On the other hand, the total memory peak has almost doubled, so no the PC hangs also at N = 32000

[Martin Sjölund]

detectJacobianSparsePattern seems to scale as poorly as sorting and matching.

[Martin Sjölund]

So the problem is that the equation (and variable) is split into 4000 separate ones for the sorting+matching. It's a 100% filled adjacency matrix (4000x4000), and just sorting the result of the matching takes 1/3 of the time.

If we would redesign the sorting+matching to handle array variables efficiently (perhaps with some heuristic) to not expand variables unless it's beneficial to do so. In this case, f(time, n)[i] will not be helpful and then perhaps we should treat it as a scalar.

Note: If you use algorithm instead of equation, the model is even slower (3s to 37s for N=4000), but this is for created simulation system equations.

[Martin Sjölund]

We could also have some pre-sorting phase where we handle all trivial equations. This would be similar to the under/over-determined partial matching check I wrote previously. That seemed to have reasonable performance.