Extended Program Query Evaluation

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 proposed Information and Software Technology journal paper "Performance Comparison of Query-based Techniques for Anti-Pattern Detection" we compare four different approaches for evaluating program queries. This page details all measurements done for the paper; the measures itself extend on the CSMR-WCRE 2014 paper "Anti-pattern Detection with Model Queries: A Comparison of Approaches" (detailed measurement results).

Model metrics

Query metrics

In case of visitors we are calculating the lines of Java code required to- gether with its cyclomatic complexity. The six original queries were written in less than 100 lines of code, and had a cyclomatic complexity of 10–20. The two new queries were more complex both in lines of code and cyclomatic complexity.
For graph patterns, we rely on metrics defined in [metrics-mq]: the number of query variables and parameters, the number of edge and attribute constraints, the number of subpattern calls and the combined number of negative pattern calls and match counters (NEG). It is important to note, that the metrics were not calculated from the graphical notation of Figure 3, but their implementation in EMF-IncQuery, where different subpatterns were created to allow the reuse both in the design level and during runtime. A subpattern call introduces new variables for the parameters of the subpattern, that are equal to some parameters at their call site; this might cause a large num- ber of variable constraints compared to the number of edge and attribute constraints.
To measure the complexity of OCL queries, we used a minimum complexity (MC) metric presented in [ocl-complexity] that is based on either calculating or estimating the number of model elements visited during the execution of its search, where multiple visits of the same element accounts as different ones. However, the metric definition relies on the model structures; in order to have a model-independent metric, estimates need to be provided for the models.
In the current paper, we calculate a lower bound of this metric by underestimating the number of visited model element with stating that each OCL expression or operation will be evaluated with at most one model element, that relates to the number of conditions to evaluate. This way, it is possible to get a lower bound of the complexity for instance models that have at least a single result for the query.
The complexity of the queries over the different aproaches behave similarly for almost all cases except for the following three: (i) the no default switch case uses the most simple pattern and OCL query, while in case of vis- itors, (ii) the concatenatation case uses the simplest visitor. (iii) Conversely, the calculation of cyclomatic complexity is clearly the most complex query in the graph patterns formalism and OCL, while its visitor is considerably simpler than the avoid rethrow. We believe, this difference is based on the fact that calculation cyclomatic complexity needs only the traversal of the containment hierarchy that visitors excel in.

Number of matches

Measurement results

Memory usage

Analysis time

Additional Evaluation Diagrams

Detailed diagrams were created for showing the load and search times and the memory usage of the various approaches on the different models. All the different diagrams are attached in an archive.