Code generated from while loop is slower than recursion

[adrpo]

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.

[perost]

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;

[hkiel]

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.

[perost]

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}.

[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. 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).

[perost]

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?

[sjoelund.se]

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.

[sjoelund.se]

Closing this discussion