MSL causes exponential time lookup

[modelica-trac-importer]

Reported by per.ostlund on 31 Mar 2011 10:58 UTC
The MSL is in my opinion written in a very inefficient way, since almost every class extends from a class in Modelica.Icons. This might not seem like such a big deal, but in fact it causes name lookup to have exponential complexity with regards to the nesting depth of the classes. This can be seen for example with a model such as this:

package Modelica
  package Icons
    package Example end Example;
  end Icons;

  package P1
    extends Modelica.Icons.Example;

    package P2
      extends Modelica.Icons.Example;

      package P3
        extends Modelica.Icons.Example;
        ...
      end P3;
    end P2;
  end P1;
end Modelica;

When flattening package PN we need to lookup the base-classes, in this example Modelica.Icons.Example. So we begin by looking for Modelica in PN, and when it's not found in the local scope of PN we continue to P(N-1), which also inherits from Modelica.Icons.Example. So we need to lookup Modelica.Icons.Example in P(N-1), and so on.

This means that when looking up a name in PN we need to lookup both the base class and the name. If T(n) is the time complexity to look up a name, where n is the nesting depth, then T(n) = 2*T(n-1), which means that T(n) = 2ⁿ.

This is easy to demonstrate too, by inputting the given example model with a large nesting depth (>20) into Dymola and watching it hang.

The reason why this is a problem is that the entire MSL is written like this, where every class extends from Modelica.Icons and using fully qualified paths for many things without actually marking them as fully qualified. I made an experiment with OpenModelica by assuming that every name that starts with Modelica is fully qualified and should be looked up from the top scope, and this makes the lookup in typical MSL models 3-4 times faster.

My suggestion is therefore that the MSL should be reorganized so that extends from Modelica.Icons.* are changed to .Modelica.Icons.*. This can easily be done automatically by for example a sed-script. Imports should also be used more, since there are many models that uses relative paths that in practice are absolute, for example models that use Modelica.SIunits directly instead of using an import. This would involve a bit more work, since it would probably have to be done by hand.

So the bottom line is that there are several ways in which the current MSL can be optimized with relatively small changes. It is perhaps also a good idea to consider these problems when discussing Modelica 4. I don't really have any suggestions, but perhaps there is some way of encouraging the use of absolute paths over relative paths.

---

Migrated-From: https://trac.modelica.org/Modelica/ticket/518

[modelica-trac-importer]

Modified by sjoelund.se on 31 Mar 2011 11:03 UTC

[modelica-trac-importer]

Comment by choeger on 31 Mar 2011 18:20 UTC
While I do not agree that lookup is exponential in general (looking up two names does not take two times the time of looking up one name!), I totally agree, that lookup is too complicated currently. I will try to "fix" this with my new modules proposal.

[modelica-trac-importer]

Comment by sjoelund.se on 31 Mar 2011 18:30 UTC
Well, we already have the encapsulated keyword which would solve all of these issues. The problem is that it is not used. Maybe this is probably due to a lack of tool support - it's easier to just insert Modelica.Icons.Library than doing lookup to see if Modelica.Icons.Library is available from the current scope (and also inserting import Modelica). In total there are <50 uses of encapsulated in the MSL.

And no, in general, lookup is fine. The problem is that the nested classes use inefficient code, and there are a lot of these nested classes.

[modelica-trac-importer]

Comment by dietmarw on 6 Apr 2011 08:24 UTC
I did some tests and also got feedback from other toolsvendors and must say that the usage of absolute Modelica path has almost no influence whatsover on the time to load the MSL. So I rather say that something with the way OM handles name lookups has to be fixed than changing the whole MSL.

Based on this I'm going to close this as won't fix.