Quadratic complexity for lists in SimCodeUtil.replaceLiteralExp

[Per Östlund]

The current implementation is SimCodeUtil.replaceLiteralExp is very slow for something like this:

function test
  output list<Integer> l;
algorithm
  l := fill(1, 1000);
end test;

model M
algorithm
  test();
end M;

replaceLiteralExp takes about 3 sec to process this model, and increases quadratically with the size of the list. It's because the list generated by fill will first be converted to a cons-expression in replaceLiteralExp, and then traverseExp will be used to call replaceLiteralExp on that expression. So replaceLiteralExp will first be called on the head of the cons-expression, and then on the rest. Then it will be called on the head of the rest, and so on. And each expression will be hashed, which means that we'll first hash a 999 long list, then 998 long, etc, which takes a long time.

I tried to fix this issue by doing the traversal first and then converting to a cons-expression (see attached diff), but this breaks the bootstrapping tests in a way that I don't know how to fix.

[Martin Sjölund]

I will add a special case for lists of length >25.

[Martin Sjölund]

Fixed in r22353.