helper attributes. Helper attributes are basically similar to parameterless helper operations with a signi cant performance-related di erence: their result is cached. Therefore, multiple accesses do not result in multiple computations. The getTree helper operation was thus changed into a tree helper attribute. With a lower performance impact, the getNode helper operation was also changed into a node helper attribute.
that can be precomputed. A typical example is the navigation of missing opposite references.
use of the exists iterator in the body of a select iterator. We instead compute two Maps: one for each of the possible true and false values. These Maps are indexed by ports. Moreover, these Maps are computed in helper attributes, and are therefore cached and computed only once per context. Because EMFTVM uses a HashMap to implement Maps, the resulting code has a linear time complexity.
the initialization phase.
The optimizations were applied after repeated measurements with the ATL/EMFTVM pro ler. This pro ler can be enabled by checking the "Display Pro ling Data" box in the Eclipse Run Con guration dialog. Listing 6 in Appendix shows the output of running the ATL reference solution (before any optimization) against the \GeneratedI8O2Seed68.ttmodel". Typically, the maximum gains can be achieved by addressing the top lines of the pro ler output, in this case the getPartition and getTree helper operations. The top line of the pro ler output amounts to 21.45% of the total measured runtime of the transformation. It represents a quali ed portion of the getPartition helper operation: the \@0@0" quali er designates the rst closure within the rst closure of the getPartition helper body, which is invoked 41811968 times.
Listing 1 shows the getPartition helper operation. The rst closure within the rst closure is the body of the exists iterator within the select iterator (line 9). In this case, the fact that so much runtime is spent here is due to the high amount of invocations.
Instead of trying to optimize directly at this level, we rst trace back where the getPartition helper is invoked: it is invoked only from within the getTree helper operation. The getTree helper operation is also 5https://wiki.eclipse.org/ATL/Design_Patterns#Object_indexing responsible for a large portion of the transformation runtime: the main helper body is responsible for 8.50% of the measured runtime, and is invoked 718080 times (line 7 of Listing 6). There are two getTree helper operations: one with input parameters, and one without. The one with input parameters invokes itself recursively, and the one without input parameters only invokes the one with parameters.
1 helper context TT ! TruthTable def: 2 getTree () 3 : TupleType ( cell : TT ! Cell , zeroSubtree : OclAny , oneSubtree : OclAny ) = 4 thisModule . getTree ( self . rows , self . ports -> select (p | p. oclIsKindOf ( TT ! InputPort )));
operation into the tree helper attribute. Listing 7 shows the pro ler output after applying this optimization.
spent in the remaining getTree helper operation and the getPartition helper operation has also been drastically reduced. The total runtime has been reduced from 69.832018 seconds to 0.703755 seconds.
the getNode helper operation. getNode is also a parameterless helper operation, which can easily be converted to a helper attribute to reduce the amount of times its body is invoked. Commit dd9b9767 does just that, and
of Listing 7 have become 2560 invocations of the node helper attribute on line 10 of Listing 8. Not a signi cant improvement this time, but it has been achieved with very little e ort.
That leaves the findCell helper at the top of the list with 620415 invocations, responsible for 87.77% of the measured runtime. Listing 3 shows this findCell helper. Its purpose is to nd the corresponding tree node for a given TT cell. Ideally, it is invoked once per cell, but the representation of the in-memory tree structure makes that we cannot simply convert this operation into an attribute. We therefore resort to the object indexing pattern, which computes a Map of cells to their tree nodes.
6https://github.com/dwagelaar/ttc2019-tt2bdd/commit/c1208aebc2e3a89601411b66c83446f555dd9fe6 7https://github.com/dwagelaar/ttc2019-tt2bdd/commit/dd9b976fb79d95bb11748bb96d5e8326fa43feae Listing 4 shows the new nodesByCell helper attribute, with its companion collectAllNodes helper operation. nodesByCell uses the mappedBySingle built-in helper operation introduced by EMFTVM to convert a list of tree nodes into a map of cells to nodes. Whereas it is trivial to nd the accompanying cell for a given tree node, there is no direct way to nd the tree node for a given cell. mappedBySingle enables one to quickly reverse navigate a given EMF EReference. The collectAllNodes helper operation serves to atten the tree of nodes into a Sequence of nodes, such that it can be consumed by mappedBySingle.
Listing 9 shows the pro ler output after applying the object indexing pattern: total measured runtime has been reduced from 0.670487 seconds to 0.086927 seconds, which is signi cant. The remaining top entries in the pro ling output are getPartition and getTree (and contained closures thereof). We will focus on the top entry (line 3), which is the rst closure within the rst closure of getPartition. Listing 1 shows the getPartition helper operation, our rst example, of which line 9 represents the rst closure within the rst closure. Along with line 5 of the pro ler output { the rst closure within the second closure (Listing 1 line 17) { this closure stands out through its high amount of invocations (14848), and resulting percentage of the total measured runtime (12.37%).
pre ltered by their value (true or false). Listing 5 shows the improved version of the getPartition helper. The double nesting of closures has been eliminated, and instead two Maps are created for each row, containing the true cells mapped by their port and the false cells by their port.
3
The state of the art EMFTVM was able to run an old ATL transformation. Although, it cannot automatically optimize it, its built-in pro ler makes it possible to quickly spot performance bottlenecks and x them by making relatively simple changes such as turning parameterless helper operations into helper attributes, or applying welldocumented patterns such as the object indexing pattern. This paper has also illustrated how to interpret the pro ler output, and how to use it in order to apply performance optimizations. [GDH19]
tion Tool Contest, a part of the Software Technologies: Applications and Foundations (STAF 2019) federation of conferences, CEUR Workshop Proceedings. CEUR-WS.org, July 2019.
//www.eclipse.org/atl/atlTransformations/#TT2BDD, February 2006. Last accessed on 2019-0514. Archived on http://archive.is/HdoHM. [WTCJ11] Dennis Wagelaar, Massimo Tisi, Jordi Cabot, and Frederic Jouault. Towards a General Composition
ence on Model Driven Engineering Languages and Systems, MODELS'11, pages 623{637, Berlin,
Listing 6: ATL/EMFTVM Pro ler output 1
Listing 7: ATL/EMFTVM Pro ler output 2
Listing 8: ATL/EMFTVM Pro ler output 3 1 Duration ( sec .) Duration (%) Invocations Operation 2 0 ,009697 12 ,37 14848 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@0@0 3 0 ,009125 11 ,64 255 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple 4 0 ,008714 11 ,12 14848 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@1@0 5 0 ,004266 5 ,44 2048 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@0 6 0 ,004040 5 ,15 2048 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@1 7 0 ,003325 4 ,24 2048 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0@0 8 0 ,003175 4 ,05 255 rule Cell2Subtree@applier 9 0 ,003014 3 ,84 2560 rule Cell2Assignment@matcher 10 0 ,002862 3 ,65 256 rule Row2Leaf@applier 11 0 ,002754 3 ,51 2560 rule Row2Leaf@applier@0 12 0 ,002372 3 ,03 2560 TT ! Cell :: node : Tuple 13 0 ,002005 2 ,56 9216 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0@0@0 14 0 ,001887 2 ,41 255 static EMFTVM ! ExecEnv :: collectAllNodes ( tree : Tuple ) : Sequence 15 0 ,001874 2 ,39 2560 rule Cell2Subtree@matcher 16 0 ,001747 2 ,23 512 rule Cell2Assignment@applier 17 0 ,001722 2 ,20 255 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple 18 0 ,001419 1 ,81 1793 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@1 19 0 ,001202 1 ,53 1793 TT ! TruthTable :: tree : Tuple@0 20 0 ,000994 1 ,27 255 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0 21 0 ,000444 0 ,57 1 TT ! TruthTable :: nodesByCell : Map 22 0 ,000103 0 ,13 255 TT ! TruthTable :: nodesByCell : Map@0 23 0 ,000056 0 ,07 1 rule TruthTable2BDD@applier 24 0 ,000024 0 ,03 1 TT ! TruthTable :: tree : Tuple 25 0 ,000014 0 ,02 8 rule InputPort2InputPort@applier 26 0 ,000003 0 ,00 2 rule OutputPort2OutputPort@applier 27 0 ,000000 0 ,00 1 static EMFTVM ! ExecEnv :: init () : Object 28 0 ,000000 0 ,00 1 static EMFTVM ! ExecEnv :: main () : Object 29 Timing data : 30 Loading finished at 0 ,007728 seconds ( duration : 0 ,007728 seconds ) 31 Matching finished at 0 ,072620 seconds ( duration : 0 ,064892 seconds ) 32 Applying finished at 0 ,086084 seconds ( duration : 0 ,013464 seconds ) 33 Post - applying finished at 0 ,086153 seconds ( duration : 0 ,000068 seconds ) 34 Recursive stage finished at 0 ,086164 seconds ( duration : 0 ,000011 seconds ) 35 Execution finished at 0 ,086927 seconds ( duration : 0 ,000775 seconds )
Listing 9: ATL/EMFTVM Pro ler output 4 1 Duration ( sec .) Duration (%) Invocations Operation 2 0 ,011395 17 ,15 255 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple 3 0 ,003796 5 ,71 2048 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0@0 4 0 ,003340 5 ,03 255 rule Cell2Subtree@applier 5 0 ,003258 4 ,90 2560 rule Cell2Assignment@matcher 6 0 ,002754 4 ,15 256 TT ! Row :: trueCellsByPort : Map 7 0 ,002460 3 ,70 2048 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@1 8 0 ,002439 3 ,67 256 rule Row2Leaf@applier 9 0 ,002417 3 ,64 2560 rule Row2Leaf@applier@0 10 0 ,002390 3 ,60 9216 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0@0@0 11 0 ,002278 3 ,43 2560 TT ! Cell :: node : Tuple 12 0 ,002226 3 ,35 2048 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple@0 13 0 ,002001 3 ,01 255 static EMFTVM ! ExecEnv :: collectAllNodes ( tree : Tuple ) : Sequence 14 0 ,001973 2 ,97 256 TT ! Row :: falseCellsByPort : Map 15 0 ,001840 2 ,77 255 static EMFTVM ! ExecEnv :: getPartition ( rows : Sequence , port : TT ! Port ) : Tuple 16 0 ,001804 2 ,71 2560 rule Cell2Subtree@matcher 17 0 ,001580 2 ,38 512 rule Cell2Assignment@applier 18 0 ,001364 2 ,05 1793 TT ! TruthTable :: tree : Tuple@0 19 0 ,001340 2 ,02 1793 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@1 20 0 ,001212 1 ,82 2560 TT ! Row :: trueCellsByPort : Map@0 21 0 ,001167 1 ,76 255 static EMFTVM ! ExecEnv :: getTree ( rows : Sequence , usablePorts : Sequence ) : Tuple@0 22 0 ,001120 1 ,69 2560 TT ! Row :: falseCellsByPort : Map@0 23 0 ,000572 0 ,86 1285 TT ! Row :: trueCellsByPort : Map@1 24 0 ,000502 0 ,76 1275 TT ! Row :: falseCellsByPort : Map@1 25 0 ,000422 0 ,63 1 TT ! TruthTable :: nodesByCell : Map 26 0 ,000098 0 ,15 255 TT ! TruthTable :: nodesByCell : Map@0 27 0 ,000056 0 ,08 1 rule TruthTable2BDD@applier 28 0 ,000028 0 ,04 1 TT ! TruthTable :: tree : Tuple 29 0 ,000012 0 ,02 8 rule InputPort2InputPort@applier 30 0 ,000004 0 ,01 2 rule OutputPort2OutputPort@applier 31 0 ,000000 0 ,00 1 static EMFTVM ! ExecEnv :: init () : Object 32 0 ,000000 0 ,00 1 static EMFTVM ! ExecEnv :: main () : Object 33 Timing data : 34 Loading finished at 0 ,008821 seconds ( duration : 0 ,008821 seconds ) 35 Matching finished at 0 ,063594 seconds ( duration : 0 ,054773 seconds ) 36 Applying finished at 0 ,075310 seconds ( duration : 0 ,011716 seconds ) 37 Post - applying finished at 0 ,075353 seconds ( duration : 0 ,000043 seconds ) 38 Recursive stage finished at 0 ,075369 seconds ( duration : 0 ,000016 seconds ) 39 Execution finished at 0 ,076570 seconds ( duration : 0 ,001217 seconds )