Changes between Version 5 and Version 6 of WritingEfficientMetaModelica

Timestamp:

2014-10-15T12:18:37Z (10 years ago)

Author:

Martin Sjölund

Comment:

--

WritingEfficientMetaModelica

@@ -1 @@
-== Writing efficient MetaModelica code ==
+= Writing efficient MetaModelica code =
 
 In the bootstrapped compiler, together with the extended MetaModelica/Modelica things you can use there are some restrictions:
-1. avoid {{{matchcontinue}}} as much as possible and use {{{match}}} instead, combined with tail recursion if needed (functions where you expect to maybe iterate over more than 50 elements should be tail-recursive).
-1. If possible, rewrite {{{match}}}-expressions to use switch instead (+d=patternmAllInfo shows which expressions are optimised to switch). A switch needs to have one pattern that can be uniquely switched on a uniontype, Integer, or String type. If the last pattern is a default pattern, this pattern has to be the only one that is matched against (there may exist more, but they may only be patterns that cannot fail to match). If the last pattern is a default pattern, all uniontypes matched against in previous cases must have subpatterns that cannot fail to match. If all these restrictions are fulfilled, the match-expression avoids linear search of the patterns.
-1. Write tail recursive functions: if a function calls itself it should do that as last thing in the then part or in the last statement. You are required to bind all outputs in the same order as the function outputs or tail recursion does not work (so no wildcards ignoring one output). {{{matchcontinue}}} expressions can never be tail-recursive.
-1. Inlining functions could be used to great effect, but it currently interferes with separate compilation so in practice it will not work at the moment.
-1. Use builtin functions whenever possible: they have implementations that are better than you can achieve using MetaModelica code (for example: stringAppendList and stringDelimitList only use a single memory allocation, list reduce,map, and filter using the built-in operator avoid the extra listReverse)
-1. Avoid using the construct {{{case x equation true = fn(x); then (); case x equation false = fn(x); then ();}}}. The bootstrapped compiler will not merge the two cases into one and algorithms that ran in linear time using RML might run in quadratic time using the bootstrapped compiler if you do this. It also precludes optimisations such as tail recursion because you use {{{matchcontinue}}} instead of {{{match}}}. Use {{{case x guard fn(x) then ()}}} instead; it is possible to use this with {{{match}}}.
-1. Memory allocations are expensive. When optimizing the OMCC lexer generator it was possible to get speed similar to the ANTLR C version due to smarter algorithms avoiding memory allocations. That said, memory allocations are not incredibly expensive; use them when needed. But if you have the choice of sending arguments as a tuple or as 4 separate arguments, allocation of the tuple might be the lion's share of execution time depending on what the function does. Traversal routines can be rewritten for better performance if they do not create tuples all the time for example.
-1. Compiling efficiently depends a lot on the public interfaces of packages. If you do not intend for a function to be called from other packages, make it protected.
-1. Note that inlining calls across packages does not work due to the separate compilation scheme. Link-time optimizations in gcc/clang could remove function calls, but it probably will not.
-1. Note that tail recursion optimization is done by omc, not gcc. As such, -O0 and -O3 will generate the same function calls. But the stack usage is very different due to local optimizations within the function in C. If you use -O0 to debug something, you might trigger a stack overflow in a function that you thought was tail recursive but is actually not (-O3 just made the frames smaller so you could iterate over more elements). If this happens and you need -O0 to debug all variables, you need to first fix the function that triggers the stack overflow with -O0 or increase the stack size (simple on Linux; does not require re-compilation).
+== Use builtin functions and operators whenever possible ==
+Builtin functions have implementations that are better than you can achieve using MetaModelica code (for example: stringAppendList and stringDelimitList only use a single memory allocation).
+
+List reductions (like Modelica array reductions) can be used to avoid the extra listReverse at the end of functions written by the user. They are also easier to read. Example:
+{{{#!mo
+// List reduction, creates 1 list
+list(2*x*y for x guard x>0 in lst);
+// RML style, creates 6 lists including the listReverse operations
+List.map1(List.map1(List.filter(lst, isPositive), realMul, 2.0), realMul, y);
+}}}
+
+If you need to loop over a list, use a for- or while-loop rather than writing auxiliary tail-recursive functions (to save time writing and maintaining code):
+{{{#!mo
+for x in lst loop
+  // ...
+end for;
+}}}
+
+Use if-expressions or if-statements to conditionally do things in code that is very similar:
+{{{#!mo
+// RML-style
+case PAT1()
+  algorithm
+    f(x);
+    true = g(y);
+    h(z);
+    i(x);
+  then ();
+case PAT1()
+  algorithm
+    f(x);
+    false = g(y);
+    i(x);
+  then ();
+}}}
+{{{#!mo
+// OMC style
+case PAT1()
+  algorithm
+    f(x);
+    if g(y) then
+      h(z);
+    end if;
+    i(x);
+  then ();
+}}}
+
+== Avoid matchcontinue, use tail recursion ==
+`matchcontinue` is slow. Whenever possible, use `match` instead. This avoids calling `setjmp`.
+
+Avoid using the construct {{{case x equation true = fn(x); then (); case x equation false = fn(x); then ();}}} since this requires matchcontinue.
+The bootstrapped compiler will not merge the two cases into one and algorithms that ran in linear time using RML might run in quadratic time using the bootstrapped compiler if you do this.
+It also precludes optimisations such as tail recursion because you use `matchcontinue` instead of `match`. Use {{{case x guard fn(x) then ()}}} instead; it is possible to use this with `match`.
+
+Also, write tail recursive functions: if a function calls itself it should do that as last thing in the then part or in the last statement.
+You are required to bind all outputs in the same order as the function outputs or tail recursion does not work (no wildcards ignoring one output).
+`matchcontinue` expressions can never be tail-recursive.
+
+== Switch optimization ==
+If possible, rewrite `match`-expressions to use switch instead (+d=patternmAllInfo shows which expressions are optimised to switch). A switch needs to have one pattern that can be uniquely switched on a uniontype, Integer, or String type. If the last pattern is a default pattern, this pattern has to be the only one that is matched against (there may exist more, but they may only be patterns that cannot fail to match). If the last pattern is a default pattern, all uniontypes matched against in previous cases must have subpatterns that cannot fail to match. If all these restrictions are fulfilled, the match-expression avoids linear search of the patterns.
+
+== Inlining functions ==
+
+Inlining functions could be used to great effect, but it currently interferes with separate compilation so in practice it will not work at the moment.
+Inlining calls across packages does not work due to the separate compilation scheme.
+Link-time optimizations in gcc/clang could remove function calls, but it probably will not.
+
+== Avoid memory allocations ==
+
+Memory allocations are expensive.
+When optimizing the OMCC lexer generator it was possible to get speed similar to the ANTLR C version due to smarter algorithms avoiding memory allocations.
+That said, memory allocations are not incredibly expensive; use them when needed.
+But if you have the choice of sending arguments as a tuple or as 4 separate arguments, allocation of the tuple might be the lion's share of execution time depending on what the function does.
+
+Traversal routines can be rewritten for better performance if they do not create tuples all the time for example.
+
+== Think about build system performance ==
+
+Compiling efficiently depends a lot on the public interfaces of packages. If you do not intend for a function to be called from other packages, make it protected.
+
+== Tail recursion ==
+
+Note that tail recursion optimization is done by omc, not gcc. As such, -O0 and -O3 will generate the same function calls. But the stack usage is very different due to local optimizations within the function in C. If you use -O0 to debug something, you might trigger a stack overflow in a function that you thought was tail recursive but is actually not (-O3 just made the frames smaller so you could iterate over more elements). If this happens and you need -O0 to debug all variables, you need to first fix the function that triggers the stack overflow with -O0 or increase the stack size (simple on Linux; does not require re-compilation).