Contemporary model query and transformation engines typically provide built-in facilities for retrieving all instances of a particular type/kind regardless of their location in a model (i.e. OCL's allInstances()). When implemented in a naive manner, such facilities can be computationally expensive for large models. We contribute a novel approach for implementing allInstances()-like facilities for EMF models, which makes use of static analysis and metamodel introspection and we report on the results of extensive benchmarking against alternative approaches.
As models involved in MDE processes get larger and more complex[
The majority of contemporary model query and transformation languages provide support for retrieving collections of all model elements that are instances of a particular type/kind. For example, OCL, QVTr, ATL, and Acceleo provide the built-in allInstances() operation which can be invoked on a type to return a set containing all its instances (e.g. Person.allInstances()), Epsilon's EOL provides the getAllOfType() and getAllOfKind() operations, and QVTo the objects(type : Type) and objectsOfType(type : Type) operations that operate in a similar way. We collectively refer to all such operations as allInstances() in the remainder of the paper.
For le-based EMF models, a naive strategy to implement allInstances() is to navigate the in-memory model element containment tree upon invocation, and collect and return all instances of the requested type. Repeatedly traversing the containment tree to fetch all instances of the same type for multiple invocations of the operation on that type is clearly ine cient, so the majority of model query and transformation engines provide support for caching and reusing the results of previous invocations of the operation (this is straightforward for side-e ect free languages but requires some additional book-keeping for languages that can mutate the state of a model).
When a query (or a transformation) contains a large number of calls to allInstances() for di erent types, instead of traversing the containment tree for each of these calls/types on demand, it can be more e cient for the execution engine to pre-compute and cache all these collections in one pass at start-up instead (greedy caching ). This can incur a higher upfront cost and increase the memory footprint, however, for a su ciently high number of invocations on di erent types, it is very likely to pay o eventually { particularly as models grow in size.
Overall, when more than one calls to allInstances() are made for di erent types in the context of a query, the on-demand approach is sub-optimal in terms of performance. On the other hand, if a query only calls allInstances() on a small number of types (compared to the total number of types in the metamodel), greedy caching is wasteful. 3
Given in-advance knowledge of the metamodel of a model, and the types on which allInstances() is likely to be invoked in the context of a query (e.g. obtained through static analysis of the query itself) operating on that model, in this section we demonstrate how a query execution engine can e ciently pre-compute and cache the results of only these invocations by traversing the contents of the model only once.
We demonstrate the proposed algorithms and their supporting data structures with reference to a concrete OCL-like query language (Epsilon's EOL). For conciseness, we also restrict the discussion to EOL queries operating on a single EMF-based model which conforms to an Ecore metamodel comprising exactly one EPackage. However, the proposed approach is trivially portable to other query and transformation languages of a similar nature, and to queries that involve more than one models conforming to multi-EPackage metamodels. 3.1
Figure 1 demonstrates a data structure (in the form of a metamodel), an instance of which needs to be populated at compile-time (e.g. by statically analysing the query of interest and by introspecting the metamodel of models on which it will be executed) in order to facilitate e cient execution of allInstances() at runtime.
CacheCon guration acts as a container for the EClasses of the model's metamodel that the engine may need to retrieve all instances of in the context of the query of interest. EClasses of interest can be linked to a CacheCon guration through the latter's allOfKind and allOfType references (EOL, like QVTo, support distinct operations for computing all direct and indirect instances of a given type). We intentionally refrain from discussion the traverse reference in Figure 1 for now. 3.2
The rst step of the process is to generate an initial version of the cache con guration model by statically analysing the query of interest. Figure 2 demonstrates the type-resolved abstract syntax graph of the example EOL program illustrated in Listing 1.1, which operates on models conforming to the metamodel of Figure 3. To compute the initial version of the cache con guration model we need to iterate through the abstract syntax graph and locate instances of: { MethodCallExpression for which the name of the method called is allOfKind, allOfType, allInstances (alias of allOfKind()), the resolved type of their target expression is ModelElementType, and which have no parameter values; { PropertyCallExpression for which the name of the property is all (alias of allOfKind()), and the resolved type of their target expression is ModelElementType.
Listing 1.1. An example EOL Program
Having identi ed the calls of interest, we construct a new CacheCon guration and for each call to allOfType() we create an allOfType link to its respective EClass. Similarly, for all other calls of interest we link the respective EClasses to the cache con guration via its allOfKind reference. The initial extracted cache con guration model for our running example is illustrated in Figure 5. Following the process discussed above, the execution engine can now be aware of all the allInstances() collections it needs to pre-compute and cache (WebPage.allOfType() and Member.allOfKind() in our running example). The next step is to collect the model elements of interest in one pass and as e ciently as possible. A straightforward collection strategy would involve navigating the entire model containment tree, assessing whether each model element is of one of the types of interest and, if so, adding it to the appropriate cache(es).
However, by inspecting the example model in Figure 4, we observe that traversing the containment closure of the modules reference of the \Computer Science" Department model element is guaranteed not to reveal any model elements of interest (according to the metamodel of Figure 3 modules can only contain lectures and neither of these types of elements are of interest to the query). This observation can be generalised and exploited to prune the subset of the containment tree that the engine will need to visit in order to populate the caches of interest.
To achieve this we need to analyse the metamodel and compute the subset of containment references that can potentially lead to elements of interest. The proposed algorithm is illustrated in Algorithm 1. Please note that the algorithm has been simpli ed for presentation purposes and that implementations of the algorithm need to make use of memoisation to avoid in nite recursion that can be caused by circular containment references of no interest. Adding the computed containment references that need to be traversed at runtime to the (incomplete) cache con guration model of Figure 5, produces the (complete) con guration model of Figure 6. 3.4
Having computed the cache con guration model, the nal step includes traversing only the identi ed containment references of the in-memory model at runtime in a top-down recursive manner to collect and cache the elements of interest.
For example, with reference to the example model of Figure 4, the instance collection process starts at the top-level :University element. The element's EClass is not linked to the cache con guration via one of its allOfType or allOfKind references, and as such the element is not cached. Navigating the university's departments reference reveals a :Department element, which also does not need to be cached. The process does not need to navigate the department's modules reference as it is not linked to the cache con guration via the latter's traverse reference, and as such it proceeds with its members reference. Traversing the members reference reveals an instance of Student and an instance of Sta , both of which are cached in preparation for the Member.allOfKind() invocation. Similarly, the webpage reference of :Sta is traversed and reveals a :WebPage, which is also cached in preparation for the WebPage.allOfType() invocation. let cm = the initial version of the con guration cache model; let p = the EPackage that the model conforms to; let refs = empty list of EReferences; foreach non-abstract EClass c in p do foreach containment EReference r of c do
call shouldBeTraversed(r); end end function shouldBeTraversed(r : EReference) : Boolean let types = transitive closure of r 's type and all its sub-types; if types includes any of the EClasses in cm then add r to refs; return true; end else end end foreach containment EReference tr of each of the types do if shouldBeTraversed(tr) then
return true; end end return false;
In this section we report on the results of benchmarks performed on four di erent strategies for computing allInstances().
2. Greedy pre-caching (G)1 3. Type-aware pre-caching (T)2 4. Type-and-reference-aware pre-caching (TR) Benchmarks were performed on a computer with Intel(R) Core(TM) i7 CPU @ 2.3GHz, with 8GB of physical memory, running OS X Yosemite. The version of the Java Virtual Machine used was 1.8.0 31-b13. Results are in seconds.
For our benchmarks, models of varying sizes obtained from reverse engineered
Java code in the 2009 GraBaTs contest3 are used. These models, named set0,
set1, set2, set3 and set4 (9.2MB, 27.9MB, 283.2MB, 626.7MB, 676.9MB
respectively) are stored in XMI 2.0 format and have been used for various benchmarks
for di erent tools [
To quantify model coverage in our benchmarks, we counted the number of elements in each data set and then automatically generated EOL programs which exercise 20%, 40%, 60%, 80% and 100% of the total elements for each data set. An example generated EOL program is provided in Listing 1.2.
We then executed all the generated EOL programs and measured performance in terms of the time taken to load the models with the four di erent strategies and the time taken to execute the programs.
Listing 1.2. An example of generated EOL program for model element coverage 1 var size = 0; 2 var methodInvocation = MethodInvocation.all.first(); 3 size = size + MethodInvocation.all.size(); 4 var qualifiedName = QualifiedName.all.first(); 5 size = size + QualifiedName.all.size(); 6 ... 7 size.println(); 1 As discussed in Section 2, this approach naively pre-computes all possible allOfType and allOfKind caches. 2 This approach makes use of static analysis as discussed in Section 3.2 but does not prune containment references and as such it needs to visit the entire containment tree at runtime. It is included in this benchmark only to assess the additional bene ts of containment reference pruning. 3 GraBaTs2009: 5th Int. Workshop on Graph-Based Tools, http://is.tm.tue.nl/ staff/pvgorp/events/grabats2009/ The obtained results are presented in Table 1. Initials L, G, T and TR represents the approaches aforementioned (Lazy, Greedy, Type-Aware and Typeand-Reference-Aware). Since the execution time of the EOL programs for G, T and TR is practically the same4, we only present one result for all three of them under the * columns. Imp. represents the performance improvement of a certain approach, Load represents the time it takes to load the models, whereas Exec. represents the time it takes to execute the EOL programs. Finally, Total represents the time it takes to load the model and execute an EOL program for a single experiment.
From the benchmarks we observe that with the Greedy, Type-Aware and Type-and-Reference-Aware approaches, programs execute signi cantly faster than with the Lazy approach. These approaches require more time to load the models due to the overhead incurred by their respective caching logic; such overhead a ects the performance for small data sets (set 0 in this case). However, as the size of models gets larger, these approaches provide marginal bene ts in terms of the time it takes to load a model and to execute an EOL program (total time). In general, TR provides better performance but for some cases in which TR needs to visit elements deep in the containment tree, T and G marginally outperform it. In terms of memory footprint, the three approaches behave very similarly and incur a small linear overhead compared to L. 5
Several database-based model persistence prototypes have been proposed for
persisting and loading large models, including Morsa [
Computing allInstances() in such systems typically does not require traversing the entire model and can be achieved through e cient internal queries expressed in the underpinning database's native query language (e.g. SQL, Cypher). Despite the clear technical advantages of database-based technologies, there are still valid reasons for using le-based formats (e.g. XMI) for model persistence in certain contexts, such as standards-compliance, tool interoperability, and compatibility with existing le-based version control systems such as Git and Subversion. 4 This is expected as all three strategies populate all caches required before the EOL program executes. In this paper we have proposed a novel approach for computation and caching of allInstances()-like operations (e.g. used in declarative model transformation rules) on in-memory EMF models. We have compared the proposed approach against three alternative approaches via extensive benchmarking and demonstrated the bene ts it delivers in terms of aggregate model loading and query execution time. Such an approach brings bene ts only to model management programs which trigger multiple calls to allInstances().
In future iterations of this work, we wish to investigate how static analysis and metamodel introspection can be used to further improve performance of computationally-expensive queries at runtime (e.g. by constructing and maintaining in-memory indexes that can improve the performance of collection ltering operations applied to the results of allInstances()).