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 Adrian Pop, 9 years ago

Owner: changed from Lennart Ochel to Martin Sjölund
Status: newassigned

comment:2 by Per Östlund, 9 years ago

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):

  input SCode.Visibility inVisibility;
  output list<SCode.Element> outElementLst = {};
protected
  list<SCode.Element> el;
algorithm
  for e in listReverse(inAbsynElementItemLst) loop
    _ := match e
      case Absyn.ELEMENTITEM()
        algorithm
          el := translateElement(e.element, inVisibility);
          outElementLst := listAppend(el, outElementLst);
        then
          ();
      else ();
    end match;
  end for;

comment:3 by Henning Kiel, 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.

in reply to:  3 comment:4 by Per Östlund, 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}.

comment:5 by Martin Sjölund, 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).

in reply to:  5 comment:6 by Per Östlund, 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 Martin Sjölund, 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 Martin Sjölund, 7 years ago

Milestone: Future
Resolution: wontfix
Status: assignedclosed
Type: defectdiscussion

Closing this discussion

Note: See TracTickets for help on using tickets.