#4590 closed defect (fixed)
SimCode execution times scale as O(N^4) with large parameter arrays
Reported by: | casella | Owned by: | somebody |
---|---|---|---|
Priority: | high | Milestone: | 1.13.0 |
Component: | Backend | Version: | |
Keywords: | Cc: |
Description
SimCode execution times to create linear, non-linear and system jacobian parts scale very badly with size, when large parameter arrays are defined in models. See:
(https://libraries.openmodelica.org/branches/master/ScalableTestSuite/ScalableTestSuite.html ScalableTestSuite), ScalableTestSuite.Elementary.ParameterArrays.ScaledExperiments.Table_N_XX_M_XX:
NxM | Time (s) |
---|---|
2500 | 0.30 |
5000 | 0.89 |
10000 | 4.02 |
20000 | 15.12 |
40000 | 259.00 |
This makes absolutely no sense. The time spent creating the code for an array with N elements should be O(N).
Change History (6)
comment:1 Changed 7 years ago by sjoelund.se
comment:2 Changed 7 years ago by sjoelund.se
This seems to be due to the HashSet allocating space for 0 variables since the size of the system is 0. We should probably also allocate space for the parameters (which are not counted in the size of the system).
comment:3 Changed 7 years ago by sjoelund.se
Will be fixed by PR1961. Using AvlSet is much more convenient since you will not have this problem when you fail to estimate the final size of a hashtable... What pains you go to in order to have expected O(n) behavior instead of guaranteed O(n*log(n))
comment:4 Changed 7 years ago by sjoelund.se
800x50 with my changes takes a total of 6.1s for front-end, back-end and code generation with another 2.5s to compile the code (all using a single thread with parallel GC disabled).
comment:5 Changed 7 years ago by sjoelund.se
- Component changed from *unknown* to Backend
- Milestone changed from Future to 1.13.0
- Resolution set to fixed
- Status changed from new to closed
comment:6 Changed 7 years ago by casella
Also the performance of CombiTimeTable_N_XXX and TimeTable_N_XXX was greatly improved, see the Hudson report
A realistic use case that will benefit from this bugfix is when a relatively small model is fed by a table-based signal generator with a huge database.
For 100x100: Notification: Performance of createVars: known variable list: time 3.623/5.007, allocations: 14.68 MB / 0.8516 GB, free: 249.4 MB / 0.6373 GB
It seems to be that extractVarFromVar becomes slower and slower the more variables are processed...