Opened 9 years ago
Closed 7 years ago
#3699 closed discussion (wontfix)
Code generated from while loop is slower than recursion
Reported by: | Adrian Pop | Owned by: | Martin Sjölund |
---|---|---|---|
Priority: | high | Milestone: | |
Component: | Code Generation | Version: | v1.9.4-beta.2 |
Keywords: | Cc: |
Description
The code changes in this revision 55cb649/OMCompiler generate faster code than using the previous code with the while loop. It should be investigated why this happens. See also #3697.
Change History (8)
comment:1 by , 9 years ago
Owner: | changed from | to
---|---|
Status: | new → assigned |
comment:2 by , 9 years ago
follow-up: 4 comment:3 by , 9 years ago
When you look at the original code you'll see that due to the recursion the following elements from the recursion are appended to the current one, so appending the current one and then iterating is the same, which is what I implemented.
e_1 = translateElement(e, vis); // tranlate item es_1 = translateEitemlist(es, vis); // translate other items recursively l = listAppend(e_1, es_1); // first this item, then others from recursion
while ... e_1 = translateElement(e, inVisibility); // translate item l = listAppend(l, e_1); // append it, then process the following
I see that using for loop would have been much smarter. However, your version leads to reversed order.
I'm currently investigating C-code from the .mo file, as that is much clearer to me to fully understand.
comment:4 by , 9 years ago
Replying to hkiel:
However, your version leads to reversed order.
No, my version also processes the elements in the reverse order, so the final order is the same.
In MetaModelica you should always try to avoid appending new elements to the end of a list, since it's very inefficient. If you have two lists, l1 = {1}
and l2 = {2, 3, 4}
, then listAppend(l1, l2)
is the same as 1 :: {2, 3, 4}
while listAppend(l2, l1)
is 2 :: 3 :: 4 :: {1}
.
follow-up: 6 comment:5 by , 9 years ago
You don't want to do for e in listReverse if you can avoid it. Better to listReverseInPlace at the end to avoid some allocations. In my PR for a similar issue, I used: https://github.com/OpenModelica/OMCompiler/pull/426/files#diff-b2d58edd315204dc1d74fa25cf9c0288
A listAppendReverse I guess would be nice there (it's just a for-loop doing cons; maybe listCons(a for a in as)
would also work).
comment:6 by , 9 years ago
Replying to sjoelund.se:
You don't want to do for e in listReverse if you can avoid it. Better to listReverseInPlace at the
end to avoid some allocations.
Then you'd have to listReverse the result from each call to translateElement, like you did in your code. So you still end up reversing at least as many elements as given to the function. Would that really be faster?
comment:7 by , 9 years ago
The point would be to try to listReverseInPlace (costs 0 allocations; allocations are relatively very expensive). listReverse costs n. My code did use a regular listReverse, but that one can be removed by doing a listAppend in reverse.
comment:8 by , 7 years ago
Milestone: | Future |
---|---|
Resolution: | → wontfix |
Status: | assigned → closed |
Type: | defect → discussion |
Closing this discussion
listAppend is done in the wrong order in the while loop, i.e. it adds the new elements to the end of the list. That might cause some performance issues I guess. Also, it would be cleaner to use a for-loop (untested code):