Extended Program Query Evaluation

######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 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

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.