[MM] Add listFlatten and listFlattenReverse in C for more performance

[Adrian Pop]

Currently List.flatten is implmeneted as:

listAppend(lst for lst in listReverse(inList))

which has rather bad performance (time and memory wise).

Implement this in C.

[Martin Sjölund]

Is it really that bad? You need to create the full list anyway, and it's performing only the listReverse more than the necessary number?

[Adrian Pop]

If you have 20 lists it will create 19 lists in the process via each listAppend.
If you do it in C you will create one.

[Martin Sjölund]

No, it will only create 1 list:

        while(1) {
          tmp1 = 1;
          if (!listEmpty(_lst_loopVar)) {
            _lst = MMC_CAR(_lst_loopVar);
            _lst_loopVar = MMC_CDR(_lst_loopVar);
            tmp1--;
          }
          if (tmp1 == 0) {
            __omcQ_24tmpVar54 = _lst;
            __omcQ_24tmpVar55 = listAppend(__omcQ_24tmpVar54, __omcQ_24tmpVar55);
          } else if (tmp1 == 1) {
            break;
          } else {
            MMC_THROW_INTERNAL();
          }
        }

listAppend only allocates memory for the first argument; the second argument is kept verbatim.

[Adrian Pop]

Then we thought wrong, I thought it would be like one listAppend for each 2 elements in the list of lists, yes the second one is kept intact but on the next iteration it would be copied also.

[Adrian Pop]

No, is actually like I said, you lose a lot of memory on this. In C you would allocate once based on the length of the lists and then just copy the elements of all the lists except the last one.

[Martin Sjölund]

It's going to be the same with just listAppend :)

listAppend({a},listAppend({b},{c}));

Would allocate a cell for b to create tmp=b::{c} (the original c).
And then allocate a cell for a to create tmp2=c::tmp.

The difference is the overhead of allocations in libgc. But I don't think this is a huge difference in memory cost. You get some locality though (and you won't collect any part of the list until none of it is used).

[Martin Sjölund]

Of course, it will not allocate each element since listAppend already does the listLength thing internally (compared to manually creating the list using :: in MetaModelica).

[Francesco Casella]

Ticket retargeted after milestone closed