-The OMG QVT FAS1 was the result of, perhaps premature, enthusiasm to standardize the fledging model transformation community. The Eclipse implementation of the QVTo language prospers but the initial implementations of the declarative QVTr language had poor performance and have faded away. Perhaps it is time to consign QVTc and QVTr to the dustbin of misguided initiatives. Alternatively, in this paper we show how metamodel-driven analysis and a disciplined Model of Computation support fulfilment of the original aspirations. Index Terms-Graph Optimization; QVT; QVTc; QVTr; Micro-Mapping; Model of Computation
II. PROGRESSIVE TRANSFORMATION ARCHITECTURE
The Eclipse QVTd architecture ‘solves’ the problem of
implementing a triple language specification by introducing
Yet Another Three QVT Languages[
2) QVTc2QVTu: creates a Unidirectional transformation without the bloat for the unwanted directions.
3) QVTu2QVTm: creates a Minimal transformation free from the complexities of mapping refinement and composition.
4) QVTm2QVTs: converts to a graphical form suitable for static Scheduling analyses.
5) QVTs2QVTs: rewrites as Micro-Mappings to avoid livelock / deadlock hazards and establishes an efficient Schedule.
6) QVTs2QVTi: serializes to an Imperative form for direct execution by the QVTi interpreter that extends the OCL Virtual Machine. Alternatively an extension of the OCL code generator produces Java code with one outer class per transformation and a function or inner class per compound Micro-Mapping. The generated Java code bypasses many of the overheads of interpreted execution or dynamic EMF.
In this paper we concentrate on the local schedule analyses and optimizations that result in the creation of MicroMappings at the start of the QVTs2QVTs transformation.
An imperative transformation author provides the control strategy that the transformation tooling must use in order to execute the transformation. The performance is governed by the quality of the programmed control strategy and the ability of the transformation tool to implement what it has been instructed to do. The accuracy is totally dependent on unchecked assertions that required function inputs are ready.
In contrast, a declarative transformation just expresses a truth that relates the output models to the input models. The truth can be demonstrated after the transformation completes, but how the constraints that express the truth are executed may not be obvious. A declarative transformation therefore requires less programming2, but declarative transformation tooling must discover an appropriate control strategy to establish the required truth. This provides an opportunity to provide inherently accurate solutions that are faster than those for imperative transformation languages. But it also requires substantial compilation effort to avoid poor quality solutions.
The result of a transformation is one or more intermediate or output models each of which may be rendered as a UML Instance Diagram with Class-typed nodes for the model elements and Property-typed edges for their relationships. A diagram may be drawn one node or edge at a time, nodes before edges. A declarative transformation may therefore execute one commit action at a time, where a commit action either creates a node or assigns an edge. The type of object created, or the value assigned by the commit-action is computed from zero or more objects or values that must be ready for use. We therefore wrap the commit-action up inside a primitive Micro-Mapping to include the input parameters, predicates and computations that influence the commit-action. A primitive Micro-Mapping is therefore similar to the mapping or rule or relation of declarative transformation languages, but is constrained to a single commit-action. The correct sequence of primitive Micro-Mapping invocations can be found by a naive polling scheduler executing each primitive Micro-Mapping once after checking that all the objects and values that the Micro-Mapping depends upon are ready and compatible.
Retry loop f – until finished
Invocation loop f – all Micro-Mappings
Object loops f – all object/parameter pairs
Compatibility guard Repetition guard Validity guard Execute Micro-Mapping
Create repetition memento g g
g
This is hideously inefficient. The many executions, wrapped in at least three loops, with guards and mementos contrast poorly to the simple linear ‘loop’ nests of imperative programs. Fortunately there are many static analyses that we can perform on a declarative transformation in conjunction with its metamodels to tame the naive polling scheduler.
2Declarative transformation authors must learn to express the truth of what must happen rather than the mechanism by which it is done.
1) Retries: Most retries can be avoided by executing MicroMappings in a sensible order exploiting producer/consumer relationships between mappings. Where retries are necessary, they can be a result of useful progress rather than naive polling.
2) Invocations: Dead Micro-Mappings can be eliminated, but most Micro-Mappings will normally be required. The invocation loop cannot be eliminated, rather it should be effectively sequenced.
3) Objects: Considering all permutations of all objects with respect to all parameters is unnecessary; the metamodel provides a strong type system that should allow only type compatible permutations to be considered. In particular a Micro-Mapping that produces some type can be followed by a Micro-Mapping that consumes that type.
Once Micro-Mappings are scheduled in a deterministic order, many of the guards can be optimized away and many of the invocation mementos eliminated since only a single invocation is possible.
The above optimizations are global. In this paper we concentrate on the utility of Micro-Mappings and local optimizations that facilitate the overall global optimizations. Global optimization will be described in another paper.
Permuting candidate objects and parameters can lead to very poor performance, typically a two parameter quadratic search, but worse for more parameters. In this paper we will see how Micro-Mapping analysis in conjunction with the metamodel relationships enables most Micro-Mappings to be reduced to a single parameter avoiding the very poor performance.
Declarative transformation languages do not require each commit-action to be separately programmed, rather mappings (or rules or relations) aggregate one or more commit-actions as an output object pattern related to an input object pattern. These patterns impose dependencies on the availability of source objects, and guard conditions upon their suitability. In the following example we will see how the failure to distinguish between primitive and compound Micro-Mappings causes trouble for some transformation languages and conversely how recognizing the distinction enables Eclipse QVTd to give good performance.
We will consider a very simple example that has some interesting difficulties. We will transform a model comprising a DoublyLinkedList that owns a ring of Elements into another DoublyLinkedList that owns a copied ring of Elements with the order of elements in the ring reversed. The metamodel is shown in Figure 2. Since we use models rather than Java Objects, the complexities of maintaining bidirectional linkages are subsumed by the metamodel bidirectional relationships.
The transformation is sufficiently simple to show the full unidirectional implementation in ATL in Figure 3. The transformation requires two rules. list2list declares the mapping from the forwardList input to the reverseList output, populating its name and headElement. element2element populates a reverseElement from a forwardElement. The target to source assignment performs the reversal.
The exposition is particularly easy in ATL where the implicit resolution of the new-headElement from the oldheadElement is done automatically. The commented lines show where an implicit resolution is performed.
Careful study of the transformation reveals that full execution of list2list requires that element2element has previously created the new headElement and that full execution of element2element requires that list2list has previously created the new reverseList. Further study reveals that full execution of element2element requires that another execution of element2element has created its new source which recurses to require that yet another execution of element2element has created the new source’s source. The recursion terminates with full execution of element2element requiring that element2element has already created its reverseElement. These dependencies are obscure, cyclic and seemingly insoluble.
Figure 4 provides the bidirectional QVTr equivalent of ATL’s unidirectional list2list rule. The asymmetric to/from patterns are replaced by symmetric forward/reverse patterns. forwardList.headElement and reverseList.headElement are explicitly co-ordinated by a when clause rather than syntax sugar.
Once a forward execution direction has been selected, the Eclipse QVTr/QVTc tooling provides the UML-like QVTs rendering of the mappings shown in Figures 5 and 6.
Fig. 6. element2element Mapping in QVTs.
Rectangles represent Class instances with an instance name above a Class name. Rounded rectangles similarly represent shared DataType values.
Edges show directed Properties with name and cardinality. The left hand edge depicts the navigation constraint forwardHead = forwardList.headElement. Arrows show something-to-one navigation paths.
Colors show the validity of each part of the mapping.
BLACK - model elements that are constant BLUE - model elements that form part of the input model CYAN - model elements required before execution GREEN - model elements created by execution
The diagrams are created automatically; only the layout has been enhanced manually. On the left hand side BLUE elements show the input sub-pattern. On the right hand side there is a corresponding output sub-pattern. QVTc and QVTr differ from other transformation languages through the use of explicit model elements to trace the execution of each mapping. There is therefore a column of trace elements directly connected to each other and to the side patterns. Since in OCL, which QVT extends, all unidirectional navigations are bidirectionally navigable, the trace elements are navigable from the sides and so left, trace and right are unified in an overall pattern. In other transformation languages the trace is an implementation detail requiring irregular language constructs to exploit it.
V. THE MICRO-MAPPING MODEL OF COMPUTATION
Diagrams or rather graphs of nodes and edges provide a
useful way to understand systems and also computations. But
as demonstrated by the Ptolemy group, diagrams only become
really useful once there is a Model of Computation [
A Mapping provides a pattern of constraints that are all satisfied once the Mapping has been executed. It therefore defines the overall truth. In QVTs, colors are used to support intermediate partial truths. The BLACK color identifies compile-time truth. The BLUE is true after input models are loaded. The GREEN is true as a consequence of the truth of BLACK, BLUE and CYAN elements. Partial truths evolve as successively more BLACK then BLUE then CYAN then GREEN elements are resolved.
A Mapping involving more than one GREEN element may not be executable since the multiple GREEN-after-CYAN constraints in one Mapping may deadlock with respect to an inverse ordering in another Mapping.
Primitive Micro-Mappings avoid the deadlock hazard by partitioning the Mapping into multiple primitive MicroMappings each with a single GREEN element. This gives a very simple execution semantic; nothing happens until all CYAN elements are available, then execution proceeds uneventfully. When partitioning a Mapping into primitive MicroMappings, the chosen GREEN element may depend on other GREEN elements. These other GREEN elements are recolored CYAN since they are prerequisites of the chosen GREEN element. This is rather easy graphically.
Partitioning a Mapping such as Figure 5 leads to nine primitive Micro-Mappings to eliminate the deadlock hazards. Primitive Micro-Mappings that share the same dependencies may be merged to form a compound Micro-Mapping without losing the string properties of a primitive Micro-Mapping.
Each node is typed by a metamodel Class and has an instance name distinguishing its role in the overall pattern.
Each edge is typed by a metamodel Property that defines its name, direction and cardinality, which must be somethingto-one. Consequently whenever a source object exists, a target object must form part of the final truth. Wherever the metamodel defines a something-to-one opposite relationship, the opposite edge is added to the Micro-Mapping. Thus at the bottom right of Figure 6 both forwardElement.target and forwardTarget.source are drawn.
The available outputs from the Micro-Mapping are all the GREEN elements (both nodes and edges). A Micro-Mapping has no local knowledge of which GREEN nodes or edges appear in CYAN in another Micro-Mapping.
The potential inputs to the Micro-Mapping are all the BLUE and CYAN elements. A naive implementation may therefore need to invoke the Micro-Mapping for all possible permutations of objects and input nodes. Most invocations will fail through type or connectivity mismatch of a node or edge.
Partial truths involving non-GREEN elements may be falsified when further satisfactory elements are not found. A partial truth involving any GREEN element involves a commit-action; this may not be falsified.
The heads are the smallest set of input (BLUE or CYAN) nodes from which all input nodes can be reached by following directed edges. The heads therefore correspond to the necessary inputs of the Micro-Mapping; all other input elements can be computed from them. In Figure 6 forwardElement is the single head. It is drawn with a thick border to emphasize its importance. We observe that 90% of Micro-Mappings require only a single head and so are amenable to invocation within a loop over compatible input objects. This contrasts with a more naive pattern match that might have attempted a three dimensional search to locate all the compatible forwardList, forwardElement and forwardTarget objects. Use of the metamodel connectivity and cardinality constraints automatically identifies the efficient common sense solution.
This example involves no guards or complicated OCL expressions. For more general purposes, the Micro-Mapping diagram notation is extended with ellipses for iteration or operation calls and computation edges to pass OCL expression results. This ensures that the Micro-Mapping captures all of the declarative mapping. ‘Common subexpression elimination’ occurs for free. OCL operations such as oclIsKindOf, oclAsType and includes are converted directly to edges.
The foregoing description stresses the utility of to-one cardinalities. We can generalize this to support to-zero cardinalities by specifying that a node is optional. A null Node may be used to denote the absence of an object. We can also generalize to support to-many cardinalities treating a Collection of objects as a single collected object provided the collection is not dismantled by an OCL computation.
The graphical Micro-Mapping provides a representation that is much easier to analyze than diverse textual syntaxes. The Model of Computation provides the power to reason about the functionality. GREEN elements identify commit-actions that are performed once the CYAN parts are available to support execution of the commit-actions. CYAN elements therefore inhibit execution until corresponding GREEN elements of other mapping invocations creates them.
It is clear from Figure 5 that list2list has a dependency on an element2element execution since there is a CYAN Telement2element. Similarly element2element in Figure 6 has a dependency on another element2element and a list2list execution. The invocations of element2element can be seen as two instances of Telement2element. One in GREEN named trace represents the successful execution of this invocation. Another in CYAN named when Telement2element represents the predicate on successful execution of an element2element referenced in a when clause.
Any dependency-driven attempt to execute the Mappings in Figures 5 and 6 is doomed to fail. list2list cannot execute until element2element has executed for the headElement. element2element cannot execute until list2list has executed. A naive polling scheduler will livelock as it polls in vain for something to execute. A slightly smarter scheduler will deadlock once nothing executes. Yet ATL executes this transformation successfully. How? See Section VI-B.
Our earlier discussion argued that execution of primitive Micro-Mappings with a single commit action is sound and our example demonstrates that Mappings with multiple commit actions (GREEN elements) may be unsound. In this example we have a cyclic dependency that not even primitive MicroMappings can avoid.
Figures 7, 8 and 9 show how a sequence of compound Micro-Mappings can execute list2list speculatively and so break the dependency cycle.
Mapping speculates the creation of the trace object wherever the easy BLUE input dependencies are satisfied. This speculated trace object is shown In RED since it has been created without checking its CYAN dependencies.
Mapping has AMBER dependencies for objects that must be provided by Speculation Micro-Mappings and CYAN dependencies for everything else that must be available before the GREEN output-related elements can be created.
Comparing Figure 8 with Figure 5 reveals that a CYAN reverseHead node and associated edges have been omitted at the bottom right. This omission is justified by the observation that reverseHead is a corollary of the element2element Mapping; a successful execution of the AMBER element2element is guaranteed to create the required CYAN element. The GREEN reverseList at the right of Figure 8 is the corresponding list2list corollary.
If the missing CYAN element was added to 8 and its element2element counterpart, the cyclic dependency returns.
3) Edge Micro-Mapping: Once Speculation and Speculated Micro-Mappings have mediated the solution to the dependency cycle, zero or more further Edge Micro-Mappings can then provide the residual GREEN edges once the nodes at their ends are available.
Fig. 9. list2list reverseHead edges compound Micro-Mapping in QVTs. 4) Failure: The speculation may fail, in which case Figures 8 and 9 do not execute and no output model elements are created; the failed speculation is only visible as a stillspeculating trace element in the trace model.
We can now understand how ATL successfully executes the example. ATL does not perform a dependency analysis and so does not detect the difficulty. ATL just executes its rules in two stages. First all the new objects are created, then all the inter-object references are populated. ATL has therefore effectively partitioned the two list2list and element2element rules into four mini-rules list2list-create + list2list-assign, and element2element-create + element2element-assign. Executing the create mini-rules before the assign mini-rules works. This is similar to the speculation/speculated partitioning above. However ATL’s partitioning is pragmatic and the successful execution fortuitous. If a more complex guard invalidates the premature creation of outputs, ATL is unable to roll-back its invalid creations.
Space permits only a very brief summary of the other benefits of the analyses facilitated by the Micro-Mapping Model of Computation.
1) Multiple Heads: Micro-Mappings with multiple heads require multiple inputs and consequently incur invocation difficulties and non-linear execution performance. Analysis of the to-many metamodel relationships allows most multiple head Micro-Mappings to be realized by a single head MicroMapping with local rather than global loops for the other heads. This typically gives linear performance with respect to the output model size. Only genuinely Cartesian problems need incur Cartesian costs.
2) Global optimizations: The simple relationship between GREEN creation and CYAN use facilitates powerful global analysis. Some of these were briefly mentioned in Section III-B
3) Static Scheduling: We find that most Micro-Mappings can be statically scheduled and so only a small number incur dynamic scheduling overheads at run-time.
4) Global Merging: The local merging in Section V-B is heavily constrained by the requirement for a mutually shared partial truth. Once a static schedule has been established, merging can be much more aggressive. Micro-Mappings may be merged into their invokers. Predicates guaranteed by an invoker can be pruned from an invoked Micro-Mapping.
5) Incremental Execution: Execution of Micro-Mappings can be persisted as an evaluation graph comprising input nodes for each BLUE input element invocation nodes for each Micro-Mapping invocation BLUE-BLUE dependency edges between invocation nodes and input nodes CYAN-GREEN dependency edges between consuming invocation nodes and producing invocation nodes Each invocation node holds its prevailing GREEN state and is aware of the nodes that consume it. The graph can be selectively re-evaluated to propagate BLUE input changes efficiently.
In Figure 10 we plot3 the performance of the DoublyLinkedListReversal transformation using a variety of transformation engines and a couple of manual implementations4. The plot demonstrates the scalability and the underlying tooling efficiency.
Fig. 10. Performance of the Doubly Linked List Reversal transformation.
Between 1000 and 50000 model elements, the top four and a half lines show superior performance for ATL and EMFTVM (the improved ATL executor) compared to Eclipse QVTo and Interpreted QVTc. However for larger models quadratic performance, probably as a consequence of requiring a linear search of the trace to resolve output/input correspondences affects ATL, EMFTVM and QVTo. Interpreted QVTc remains linear and so at 1000000 model elements, it is 10 times faster. The performance of Epsilon for large models cannot be characterized since its half line terminates abruptly; Epsilon resolves data dependences recursively and so runs out of stack for lists longer than about 1000 elements.
The lower four lines show direct Java results, the upper two for Eclipse QVTc and QVTr, and a further two manually coded reference implementations, one using EMF extensively as a consequence of a EcoreUtil copy, and another using EMF sparingly in manual code.
QVTc and QVTr performance is almost identical since both execute the same schedule for very similar mappings. The QVTr performance is slightly worse than QVTc since the naive auto-generated trace is larger; an optimization of the autogenerated trace model will make QVTr better than QVTc. The performance almost matches EcoreUtil. Further optimizations should get much closer to the manual performance. An improved object representation could enable QVTr to outperform the manual implementation.
(The interpreted QVTc or QVTr performance may improve quite significantly once some of the static analyses for the code generated approach are exploited.)
3The plots use no averaging. Single point wobbles may be due to concurrent activity. Discontinuities may be due to fortuitous cache alignment. 4Model overheads are reduced by Java generated by an EMF genmodel.
The results demonstrate that an efficient declarative schedule can be derived automatically for a difficult dependency problem.
The results also demonstrate, unintentionally, the benefit of QVTc’ explicit trace model and the consequent linear performance when an appropriate cache is synthesized for the unnavigable opposite accesses. The quadratic performance of ATL, EMFTVM and QVTo highlights an implementation deficiency that can be remedied at the expense of some extra working memory. Ensuring that the extra memory cost is modest and the additional execution time is small, probably requires similar static compile-time or load-time analyses to those performed by Eclipse QVTd.
The code and results for this example are available in the tests/org.eclipse.qvtd.doc.exe2016.tests plugin of the https://git.eclipse.org/r/mmt/org.eclipse.qvtd GIT repository. Significant bugs in Eclipse QVTd were fixed to support this example. These fixes should be available in the Oxygen M2 milestone build in mid September 2016.
Scheduling and particularly static scheduling has been a
rich research topic with provision of optimized schedules
recognized as a computationally hard problem. The many
works of the Ptolemy group [
The Graph Transformation community has been very active
in providing a rigorous foundation for graph mappings. Sadly
the QVT specification ignored this important work, preferring
instead to define the semantics of the QVTr transformation
language using an incomplete exposition of a transformation
of QVTr written in an untested QVTr to another language
(QVTc) that has at best informal semantics. The utility and
power of the QVTs graphical Micro-Mapping and its Model
of Computation may begin to bridge the gap between these two
communities. The automated coloring in QVTs is inspired by
Henshin’s [
Active Operations [
We have introduced the Micro-Mapping Model of Computation and shown how it supports efficient declarative schedules for Eclipse QVTc and QVTr.
We used the Micro-Mapping Model of Computation to demonstrate the need for speculative creation of trace objects.
We have shown how a graphical presentation of metamodel and dependency analyses tames the naive inefficiencies of a declarative schedule.
We have introduced the first implementation of the QVTc specification.
We have presented the first results for a QVTr implementation using a direct code generator.
We have mentioned some future works. Many more optimizations to do.
The authors would like to thank Adolfo Sanchez-Barbudo Herrera, Horacio Hoyos Rodriguez, Dimitris Kolovos and Richard Paige for helpful discussions about declarative scheduling approaches. Horacio prepared some of the results and prototyped some of the scheduler algorithms.