ZeroCrossings.equals costs memory

[Henning Kiel]

Calling the function ZeroCrossings.equals costs some memory though it should only compare two zero crossings.

I looked at the code, but could not find out where.

[Henning Kiel]

I guess the memory consumption is necessary (done when converting the exp to string in CompareWithGenericSubscript.compareSubs())

Zero crossing list is created checking for uniqueness by comparison to all existing elements in the list, so O(n²). Maybe we should introduce a hash table for the uniqueness check to lower complexity to best case O(n). The memory consumption then should also go down drastically to O(n).

Model to check: ScalableTestSuite.Elementary.WhenEvents.ScaledExperiments.ManyEvents

[Francesco Casella]

Replying to hkiel:

I guess the memory consumption is necessary (done when converting the exp to string in CompareWithGenericSubscript.compareSubs())

Zero crossing list is created checking for uniqueness by comparison to all existing elements in the list, so O(n²). Maybe we should introduce a hash table for the uniqueness check to lower complexity to best case O(n). The memory consumption then should also go down drastically to O(n).

Absolutely! Large power grid models could easily feature 50.000 or more zero-crossing functions, O(N²) algorithms are really not an option in this case.

See also #3905

[Martin Sjölund]

Hashtables scale very poorly if you don't know the number of zero-crossings a-priori. And if you simply choose to create a huge table, you pay a big cost especially when n=0.

Is it mergeZeroCrossings or zcIndexRelation that is slow?

[Francesco Casella]

Replying to sjoelund.se:

Hashtables scale very poorly if you don't know the number of zero-crossings a-priori.

You just need to count conditions in if-expressions, if-statments and when-statements as you flatten them.

And if you simply choose to create a huge table, you pay a big cost especially when n=0.

Maybe we could use sorted lists/binary trees or similar?

[Martin Sjölund]

Replying to casella:

Maybe we could use sorted lists/binary trees or similar?

We have AVL trees, but the cost is O(n*log(n)).

[Francesco Casella]

Replying to sjoelund.se:

Replying to casella:

Maybe we could use sorted lists/binary trees or similar?

We have AVL trees, but the cost is O(n*log(n)).

Incomparably better than O(N²) anyway. Going from 100 to 100.000 events with O(N) gives a factor 1000, O(N log(N)) gives about 10.000, O(N²) gives a million.

[Henning Kiel]

Replying to sjoelund.se:

Hashtables scale very poorly if you don't know the number of zero-crossings a-priori. And if you simply choose to create a huge table, you pay a big cost especially when n=0.

Is it mergeZeroCrossings or zcIndexRelation that is slow?

It is zcIndexRelation which is slow. Did not check mergeZeroCrossings though.

[Martin Sjölund]

I'm trying to rewrite that code to use ZeroCrossingSet; it should be possible to do so

[Martin Sjölund]

Before (using optimized nightly):

Notification: Performance of postOpt findZeroCrossings (simulation): time 12.41/18.24, allocations: 2.68 GB / 5.342 GB, free: 240.4 MB / 0.9342 GB
Notification: Performance of simCode: created simulation system equations: time 25.44/44.06, allocations: 6.945 GB / 12.39 GB, free: 256.4 MB / 0.9342 GB

After (not optimized):

Notification: Performance of postOpt findZeroCrossings (simulation): time 0.5231/6.394, allocations: 157.4 MB / 2.811 GB, free: 244.3 MB / 0.9031 GB
Notification: Performance of simCode: createEquationsForSystems: time 20.71/27.48, allocations: 6.945 GB / 9.857 GB, free: 129 MB / 0.9031 GB

[Martin Sjölund]

The remaining issue for the model is that markZeroCrossingEquations is called for each independent system of equations and loops over each zero-crossing.

So for n systems each with v variables: collect all variables in all m zero-crossings and check if they are part of the system so we can mark equations. Gives O(n*m*log(v))

Should be O(m*log(m) + O(m*v*log(m))) = O(m*v*log(m)) where m*v is the size of the total system:

1. Collect all variables in all zero-crossings
2. For each system: Do a set intersection with the variables in zero-crossings and variables in the system: mark the equations involving those variables

[Martin Sjölund]

Seems my ​PR1962 did not succeed in the testsuite; I'm a bit unsure why it wouldn't pass...

[Francesco Casella]

Rescheduled to 1.14.0 after 1.13.0 releasee

[Francesco 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

[Francesco Casella]

Retargeted to 1.17.0 after 1.16.0 release

[Francesco Casella]

Retargeted to 1.18.0 because of 1.17.0 timed release.

[Francesco Casella]

Ticket retargeted after milestone closed