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

    LOC Node Count Edge Count Attribute Count Type Count Average InDegree Maximum InDegree Average OutDegree Maximum OutDegree
1 ArgoUML 174 516 1 002 129 2 973 258 6 895 018 100 3 72 230 3 445
2 CloudStack 1 369 952 5 390 662 16 478 218 36 650 136 100 3,1 631 140 3,1 1 198
3 Eclipse 2 294 146 8 403 914 26 254 507 58 219 100 97 3,1 1 245 390 3,1 1 958
4 Frinika 64 828 429 407 1 292 961 3 065 383 99 3 54 286 3 844
5 GWT 1 078 630 3 219 239 9 986 705 22 364 819 101 3,1 392 098 3,1 1 206
6 Hibernate 773 166 2 444 419 7 563 207 16 789 330 102 3,1 193 769 3,1 522
7 Jackrabbit 590 420 1 765 882 5 341 431 12 145 662 100 3 271 217 3 708
8 Java DjVu 23 570 129 068 372 444 926 653 92 2,9 26 918 2,9 1 026
9 javax.usb 1 161 12 231 32 388 89 399 83 2,6 969 2,6 148
10 JFreechart 327 865 865 148 2 663 967 6 022 410 93 3,1 50 658 3,1 445
11 JML 10 159 72 598 212 544 520 599 94 2,9 4 908 2,9 221
12 JTransforms 38 400 295 009 945 643 2 053 900 80 3,2 117 775 3,2 217
13 Makumba 65 065 378 204 1 127 797 2 637 424 98 3 62 717 3 445
14 OpenEJB 575 363 1 785 660 5 428 385 12 377 185 101 3 152 624 3 540
15 Physhun 4 935 36 962 108 888 263 091 86 2,9 2 944 2,9 148
16 ProteinShader 22 651 137 416 391 322 997 679 88 2,8 9 654 2,8 445
17 Qwicap Guess 443 7 903 21 222 59 069 85 2,7 918 2,7 107
18 Robocode 28 245 204 362 599 556 1 500 298 97 2,9 17 323 2,9 445
19 sdedit 14 717 145 453 413 998 1 075 471 97 2,8 12 643 2,8 445
20 Stendhal 105 411 667 142 2 037 645 4 688 300 98 3,1 49 556 3,1 445
21 Struts2 274 092 927 163 2 849 021 6 452 090 100 3,1 95 272 3,1 620
22 Superversion 29 282 238 842 705 875 1 731 692 94 3,0 2 041 3,0 445
23 SVNKit 114 189 698 753 2 203 436 4 843 209 93 3,2 57 987 3,2 272
24 Tomcat 459 579 1 338 601 4 084 668 9 302 681 102 3,1 116 637 3,1 620
25 WebWork 46 208 285 372 853 724 2 018 672 95 3 36 439 3 445
26 Weka 205 537 1 615 637 4 989 653 11 259 543 99 3,1 216 651 3,1 550
27 Xalan 349 681 708 445 2 093 338 4 937 831 93 3 87 447 3 445
28 Xins 21 698 164 989 472 003 1 193 822 89 2,9 15 169 2,9 445

Query metrics

  Visitor Query OCL
  LOC CC Param. Variables Edges Attr. Calls NEG MC
catch 78 14 4 6 3 0 1 0 9
concatenate 32 8 6 8 3 1 3 0 4
constant compare 39 10 6 11 5 0 2 2 7
no default switch 53 11 2 3 1 0 0 1 2
string compare 56 15 10 17 10 1 7 2 15
unused parameter 88 21 11 19 8 0 6 1 21
avoid rethrow 210 54 11 24 12 0 2 1 23
cyclomatic complexity 114 22 23 40 5 2 9 7 34

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

  Model catch cyclomatic complexity concatenate constant compare no default switch avoid rethrow string compare unused parameter
1 CloudStack 51 2190 0 6556 30 9 26 3557
2 ArgoUML 11 201 0 419 32 10 30 253
3 Eclipse 28 3855 0 1293 1781 27 216 4928
4 Frinika 1 114 0 59 21 0 1 192
5 GWT 11 517 0 276 158 4 49 857
6 Hibernate 29 249 0 249 14 12 2 294
7 Jackrabbit 207 496 0 114 34 15 12 527
8 Java DjVu 0 69 0 42 14 0 4 11
9 javax.usb 0 0 0 0 0 0 0 0
10 JFreeChart 0 216 0 36 4 0 1 169
11 JML 0 6 0 5 2 0 0 10
12 JTransforms 0 143 0 0 0 0 0 0
13 Makumba 6 247 0 299 8 0 28 179
14 OpenEJB 30 381 0 411 76 60 3 998
15 Physhun 0 5 0 5 0 0 0 27
16 ProteinShader 0 8 0 119 51 0 0 6
17 Qwicap Guess 0 1 0 0 0 0 0 0
18 Robocode 1 75 0 169 8 0 0 23
19 sdedit 0 19 0 75 4 3 0 6
20 Stendhal 0 118 0 386 10 0 4 261
21 Superversion 0 28 0 18 9 0 24 18
22 SVNKit 25 391 0 10 7 12 0 20
23 Struts2 66 251 0 129 13 2 15 414
24 Tomcat 113 616 0 528 45 7 16 136
25 WebWork 1 41 0 58 5 1 0 155
26 Weka 2 742 0 471 76 10 12 62
27 Xalan 17 282 0 349 26 30 49 289
28 Xins 28 39 0 109 0 0 0 50

Measurement results

Memory usage

  Model ASG EMF OCL LS IQCC INC
  Memory  Deviation Memory Deviation Memory Deviation Memory Deviation Memory Deviation Memory Deviation
1 CloudStack 2188.70 0.47 3503.17 1.39 3925.29 37.59 4016.82 2.67     10413.94 58.88
2 ArgoUML 198.17 0.80 403.67 0.90 460.90 2.25 549.10 9.13 11973.62 841.29 5068.22 42.09
3 Eclipse 2452.64 0.66 4053.91 1.87 4640.64 3.88 4744.81 1847.65     17754.44 753.93
4 Frinika 79.21 0.23 148.00 0.58 326.10 0.48 365.33 1.68 5390.91 206.00 2433.39 64.46
5 GWT 2578.84 0.12 1966.99 2.49 2178.17 2.95 3565.62 1.25     5972.58 32.93
6 Hibernate 2085.72 0.14 2523.76 1.73 2788.04 2.44 2994.85 37.49     4507.16 2.54
7 Jackrabbit 309.50 0.04 582.53 4.62 651.47 63.44 955.14 9.80 22122.79 1593.50 3652.07 59.45
8 Java DjVu 37.16 0.15 63.94 0.19 245.42 6.73 115.11 10.93 1545.64 543.90 800.01 0.06
9 javax.usb 8.50 0.01 14.00 0.06 85.37 0.06 74.69 0.19 140.68 170.83 266.67 0.01
10 JFreeChart 159.97 0.06 360.14 2.18 428.52 66.98 530.19 82.63 10560.27 273.34 4400.10 0.34
11 JML 34.87 0.16 36.67 0.04 197.36 3.12 218.70 0.16 770.72 358.91 666.67 0.05
12 JTransforms 58.06 0.01 85.89 0.87 273.48 0.79 165.42 0.42 4796.72 301.66 1733.34 0.12
13 Makumba 73.96 0.19 144.03 0.42 296.43 2.68 230.54 1.23 4384.48 74.61 2001.13 42.16
14 OpenEJB 343.79 0.26 656.07 2.89 662.37 81.46 945.65 6.50     3888.93 23.00
15 Physhun 28.88 0.05 37.91 0.12 128.20 0.23 133.37 47.98 486.36 195.91 400.00 0.02
16 ProteinShader 42.22 0.04 69.18 0.27 102.42 1.08 149.80 0.51 1530.97 498.67 933.34 0.07
17 Qwicap Guess 25.72 0.03 29.12 0.25 74.68 0.28 64.02 0.15 124.33 177.00 266.67 0.01
18 Robocode 48.16 0.03 86.52 0.24 219.37 6.55 287.81 0.47 2246.17 650.15 1200.01 1923.18
19 sdedit 45.10 0.09 71.46 0.04 106.02 3.11 159.27 8.12 1536.87 550.13 1050.01 70.29
20 Stendhal 109.11 0.06 228.78 0.51 431.37 36.05 460.11 124.24 7783.26 628.54 3383.35 68.85
21 Superversion 61.87 0.02 87.84 0.19 270.94 0.20 138.90 0.81 2676.90 959.19 1333.37 0.12
22 SVNKit 128.91 0.48 251.67 3.12 400.82 2.61 408.76 2.80 9835.10 555.87 3716.79 4819.12
23 Struts2 158.79 0.03 358.79 2.71 478.83 2.59 521.45 2.86 11636.40 180.22 4893.36 70.27
24 Tomcat 245.64 0.04 546.83 6.05 600.67 7.56 788.09 66.68 16929.36 2169.28 6637.48 64.05
25 WebWork 63.95 0.07 123.55 13.82 300.15 28.16 248.11 0.73 3484.59 980.45 1600.01 0.18
26 Weka 290.09 0.07 615.66 6.08 615.06 151.36 695.24 10.62 20357.23 1377.35 3426.81 1.00
27 Xalan 146.35 0.59 260.08 2.85 440.96 1.74 445.16 9.02 8259.32 535.28 3600.01 0.52
28 Xins 45.11 0.07 74.82 0.06 152.01 9.51 209.90 1.27 2440.81 877.80 1066.69 0.10

Analysis time

  Model Load Time One Time Analysis Commit Time Analysis Save Time Analysis
  ASG EMF OCL LS IQCC INC ASG EMF OCL LS IQCC INC ASG EMF OCL LS IQCC INC ASG EMF OCL LS IQCC INC
1 CloudStack 27.46 114.50 114.97 156.32   342.58 74.51 146.87 248.78 240.91   342.68 497.97 438.22 1453.11 1002.23   343.60 4732.56 3351.70 13496.42 8615.47   352.78
2 ArgoUML 6.66 25.36 25.25 34.59 311.54 51.91 21.40 35.66 52.72 42.35 311.62 51.99 154.04 128.28 299.92 112.13 312.35 52.73 1480.45 1054.54 2771.87 809.91 319.66 60.15
3 Eclipse 41.74 169.20 170.69 237.66   470.10 110.12 216.15 356.90 341.57   470.18 725.52 638.72 2032.80 1276.77   470.97 6879.54 4864.45 18791.73 10628.76   478.80
4 Frinika 3.03 11.06 11.07 15.41 132.46 24.54 12.95 17.09 26.97 19.92 132.54 24.62 102.23 71.30 170.10 60.57 133.27 25.33 995.08 613.49 1601.41 467.02 140.64 32.49
5 GWT 16.09 79.96 80.22 102.00   199.10 67.72 104.24 146.10 132.87   199.18 532.43 322.77 739.05 410.67   199.87 5179.54 2508.01 6668.54 3188.70   206.80
6 Hibernate 12.99 58.48 57.42 83.13   145.99 48.95 79.84 116.62 98.91   146.06 372.51 272.12 649.43 240.90   146.71 3608.19 2194.93 5977.46 1660.83   153.19
7 Jackrabbit 10.41 38.56 38.07 55.19 795.88 113.18 33.53 53.24 81.07 107.41 795.97 113.26 241.58 185.41 468.12 577.43 796.73 113.95 2322.10 1507.11 4338.52 5277.56 804.34 120.88
8 Java DjVu 1.49 4.24 4.29 6.12 41.80 9.67 6.68 7.99 188.05 7.87 41.87 9.75 53.39 41.73 1841.89 23.63 42.53 10.43 520.51 379.07 18380.32 181.23 49.11 17.24
9 javax.usb 0.64 1.35 1.32 2.06 5.20 3.15 2.04 2.18 10.82 2.31 5.40 3.22 14.68 9.66 96.26 4.54 7.21 3.80 141.09 84.41 950.68 26.84 25.37 9.59
10 JFreeChart 5.63 21.26 21.12 29.52 277.48 44.44 24.36 30.61 45.16 37.15 277.56 44.52 192.99 114.84 261.53 105.83 278.23 45.22 1879.20 957.08 2425.27 792.63 284.91 52.21
11 JML 1.12 3.20 3.18 4.41 23.53 6.61 4.79 5.78 68.86 5.19 23.60 6.68 37.86 28.97 659.97 12.21 24.25 7.32 368.53 260.88 6571.00 82.46 30.71 13.63
12 JTransforms 2.11 5.14 5.13 8.46 135.49 15.27 8.80 9.24 514.20 15.85 135.55 15.34 69.06 46.15 5095.79 82.36 136.16 15.93 671.65 415.18 50911.68 747.39 142.19 21.88
13 Makumba 2.88 9.59 9.67 13.83 129.41 21.03 12.82 15.48 25.18 19.59 129.48 21.11 102.27 68.48 164.79 71.48 130.15 21.82 996.84 598.49 1560.80 590.35 136.88 28.91
14 OpenEJB 10.63 43.53 42.76 59.59   117.06 32.51 58.84 81.49 73.38   117.14 229.41 196.65 430.12 197.50   117.83 2198.45 1574.78 3916.44 1438.75   124.82
15 Physhun 0.81 2.14 2.11 3.43 12.26 5.08 3.53 3.86 16.64 3.98 12.34 5.14 28.05 19.35 147.41 8.88 13.02 5.70 273.17 174.21 1455.10 57.90 19.84 11.30
16 ProteinShader 1.58 4.71 4.77 6.48 35.33 9.85 6.37 8.22 341.95 7.57 35.40 9.93 49.53 39.79 3376.55 17.38 36.04 10.61 481.15 355.50 33722.63 115.49 42.41 17.40
17 Qwicap Guess 0.54 1.03 1.02 1.62 4.31 2.75 1.56 1.65 8.00 1.85 4.37 2.81 10.70 7.16 70.76 3.90 4.91 3.32 102.17 62.31 698.43 24.37 10.37 8.40
18 Robocode 1.92 6.02 6.06 8.55 54.54 13.06 9.38 10.37 296.84 10.52 54.62 13.13 76.54 49.52 2913.90 28.23 55.29 13.78 748.17 441.04 29084.54 205.35 62.06 20.19
19 sdedit 1.59 4.87 4.93 6.76 43.23 10.33 6.64 8.50 167.39 7.90 43.31 10.40 52.13 41.14 1629.54 18.22 44.00 11.09 507.01 367.53 16251.08 121.37 50.91 18.00
20 Stendhal 4.44 17.14 16.84 23.33 238.86 36.44 18.29 24.97 36.80 28.72 238.94 36.52 142.91 95.41 216.38 77.29 239.63 37.24 1389.19 799.83 2012.22 562.89 246.54 44.45
21 Superversion 2.04 6.63 6.96 9.63 78.79 14.57 10.50 11.32 18.14 11.63 78.87 14.65 86.65 53.54 118.81 29.62 79.57 15.31 848.19 475.78 1125.43 209.52 86.61 21.90
22 SVNKit 4.38 17.60 17.76 24.63 267.89 38.68 17.76 25.79 41.60 34.94 267.98 38.76 138.19 99.50 256.15 127.75 268.73 39.45 1342.53 836.62 2401.71 1055.87 276.27 46.42
23 Struts2 5.73 23.50 23.23 31.96 291.73 49.08 24.17 33.18 48.26 39.92 291.81 49.16 190.13 120.36 273.50 111.57 292.52 49.88 1849.76 992.10 2525.96 828.02 299.60 57.13
24 Tomcat 8.25 33.20 32.64 43.18 483.90 69.39 28.01 45.57 70.19 57.86 483.98 69.48 205.82 156.87 408.19 190.02 484.74 70.26 1983.91 1269.90 3788.15 1511.58 492.30 78.03
25 WebWork 2.29 8.01 8.01 11.26 89.51 16.84 10.20 13.09 1044.03 13.96 89.59 16.91 81.39 58.79 10368.19 38.26 90.26 17.59 793.33 515.73 103609.80 281.27 97.02 24.35
26 Weka 9.43 37.66 37.33 51.77 526.35 111.45 36.23 51.46 81.21 74.49 526.43 111.52 277.47 175.62 476.20 278.92 527.19 112.17 2689.84 1417.24 4426.08 2323.21 534.77 118.69
27 Xalan 4.76 18.84 18.80 24.70 253.59 37.50 18.42 28.03 42.57 36.84 253.67 37.58 141.36 110.75 256.51 146.14 254.37 38.31 1370.76 937.89 2395.85 1239.11 261.37 45.63
28 Xins 1.71 5.38 5.42 7.58 48.52 11.32 7.13 9.44 315.25 9.11 48.60 11.39 55.96 46.01 3103.74 22.80 49.26 12.06 544.26 411.73 30988.67 159.73 55.85 18.68

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.