######Tags: EMF-IncQuery publication

Authors: Zoltán Ujhelyi, Ákos Horváth, Dániel Varró, Norbert István Csiszár, Gábor Szőke, László Vidács, Rudolf Ferenc In the CSMR-WCRE 2014 paper "Anti-pattern Detection with Model Queries: A Comparison of Approaches" we compare three different approaches for evaluating program queries. This page details all measurements done for the paper.

###Model sizes

The approaches were evaluated on a test set of 30 modules of 17 open source projects. The projects are sized between 1kLOC and 500kLOC, are are used in various scenarios, thus sharing different characteristics. The list of projects include the ArgoUML UML editor, JTransforms, a Fourier transformation library, the SVNKit Subversion client, the online homework system WeBWorK, the Weka data mining software and many more. The next table describes the sizes of these projects in lines of code together with the size of the ASG and EMF models in terms of nodes and edges.

###Measurement Description

All measurements were executed on a dedicated Linux-based server with 6 GB RAM running Java 6. On the server the Java ASG of the Columbus Framework was installed together with the EMF-INCQUERY model query framework. All program queries were implemented as both visitors for the ASG (by Columbus experts) and as graph patterns (by EMF-INCQUERY experts). The visitor implementation was executed on both model representations, while the graph patterns were used to initialize local search and Rete network based pattern matchers for the EMF representation. In all cases, the time to load the model from its serialized form and the time to execute the program query was measured together with the maximum heap size usage. Every program query was executed ten times, and the time and memory results were averaged. In order to minimize the interference between different runs, for each execution a new JVM was created and each query was run in isolation. The time to start up and shut down the JVM were not included in the measurement results.

###Memory and Search Time Results

The measurements showed that model load time is largely independent from the query selection. It can be seen that the load time doubles when using an EMF-based implementation over the manual Java ASG, and further increases can be seen when initializing the pattern matchers for local search and incremental queries. The required two-phase load algorithm for the EMF model (EMF case), and the time to set up the indexes (local search) and partial matches (Rete) can account for these increases. A similar increase can be seen on the memory usage: the EMF representation uses more than twice as much memory, while the incremental engine uses 10 times more memory to store its partial result caches compared to the ASG. The smaller memory footprint increase of Java ASG representation are probably caused by model-specific optimizations not applicable in generic EMF models. The additional increase for local search and Rete-based pattern matchers mainly represent the index and partial match set sizes, respectively. For each model and each program query the average search time is listed at first. The visitor implementations perform similarly, as they traverse the entire model to find the results. The time differences between the ASG and EMF visitor implementations are mainly the result of memory optimizations, as traversing the model requires more indirection then in the EMF case. The local search and Rete based solutions provide a two or three orders of magnitude faster query execution, achieved by replacing model traversal by calls to a pre-populated (and incrementally updated) index.

Additionally, the runtime of visitor implementation increases linearly with the code size. This is in line with our expectation, as visitors have to traverse the entire model during search. On the other hand, the search time for incremental queries are roughly the same for all queries, as the search means only returning the results. Surprisingly, in most of our patterns, local search time behaves similarly to incremental queries. However, the concatenation pattern behaves more like the visitors in this regard. Based on our earlier experience with different pattern matching strategies the execution performance for local search based approaches depends on the query complexity and the model structure.

###Usage Profiles

In order to compare the approaches, we calculated the total time required to execute program queries for three different usage profiles: one-time, commit-time and save-time analysis.

• One-time analysis consists of loading the model and executing each program query in a batch mode. In case the analysis needs to be repeated, the model is reloaded. In our measurements, this mode is represented by a load operation followed by a single query evaluation.
• Commit-time analysis can be used in a program analysis server that keeps the model in-memory, and on each commit, it updates this model as opposed to reloading it entirely, and then it re-executes all queries of the analysis. In our measurements, this mode is represented by a load operation followed by 10 query evaluation.
• Save-time analysis is executed whenever the programmer saves a file in the IDE, and then the IDE either executes the analysis itself, or notifies the analysis server. This mode is similar to commit-time analysis, just it is executed more often (with all queries executed as well). In our measurements, this mode is represented by a load operation followed by 100 query evaluation.

####Diagrams

One-time analysis

Commit-time analysis results

On-save analysis results

Box-plot showing the distribution of measurement results

Raw, tabular data

###Lessons learned

1. Generic model implementations, such as EMF, can substitute manually optimized, specific model implementations, as their increased memory consumption is less then a factor of 2.
2. Generic solutions require additional memory to execute up to a factor of 5 and an additional increased initialization time. However, this additional resource consumption seems acceptable for a large set of problems based on the evaluation.
3. The runtime of the analysis itself using generic model query implementations is orders of magnitude faster than manually optimized visitor queries.

Attachment: Raw measurement results