Tool performance

We conducted some experiments to evaluate the performance of DDJ.

DDJ is described in this paper:

• David Insa, Josep Silva
  An Algorithmic Debugger for Java
  Proceedings of the 26th IEEE International Conference on Software Maintenance (ICSM 2010).
  © IEEE
  Available: PDF preprint

The implementation was tested with a collection of real applications (e.g., an interpreter, a parser, a debugger, etc). The table below summarizes the results of the experiments performed. These experiments were performed with a Intel Core2 Quad 2.67 GHz with 2GB RAM.

Benchmark	Number of variables	ET size	ET time	First node time	Cache limit	ET depth
Argparser	8.812	2 MB	22 s	407 ms	7/7	7
Cglib	216.931	200 MB	230 s	719 ms	11/14	18
Kxml2	194.879	85 MB	1318 s	1844 ms	6/6	9
Javassist	650.314	459 MB	556 s	844 ms	7/7	16
Jtestcase	1.859.043	893 MB	1913 s	1531 ms	17/26	57
HTMLcleaner	3.575.513	2909 MB	4828 s	609 ms	4/4	17
Average	1084248,67	758 MB	1477,83 s	992,33 ms	8,67/10,67	20,67

For each benchmark, the second and third columns give an idea of the size of the execution. Fourth and fifth columns are time measures. Finally, sixth and seventh columns show memory bounds. Concretely:

• Column Benchmark contains the names of the benchmarks;
• Column Number of variables shows the number of variables participating in the execution considered;
• Column ET size shows the size in MB of the ET when it is completed, this measure has been taken from the size of the ET in the database (of course, it includes compaction);
• Column ET time is the time needed to finish the ET;
• Column First node time is the time needed to complete the first node of the ET;
• Column Cache limit shows the presentation and logic bounds of these benchmarks. After these bounds, the computer was out of memory;
• Column ET depth shows the depth of the ET after it was constructed;

The last two columns of the table give an idea of how big is the ET shown in the GUI before it is out of memory. In general, five levels of depth is enough to see the question asked and the part of the computation closely related to this question. In the experiments only HTMLcleaner was out of memory when showin five levels of the ET in the GUI.

Evaluation of the execution trees balancing technique

The technique for balancing execution trees is described here:

• David Insa, Josep Silva, Adrián Riesco
  Speeding Up Algorithmic Debugging Using Balanced Execution Trees.
  Proceedings of the 7th International Conference on Tests and Proofs (TAP 2013).
  © Springer-Verlag, 2013.
  Available: PDF preprint

We debugged 31 Java benchmarks. Some benchmarks are Java programs implemented by university students; others are small to medium Java benchmarks including games, mathematical transformations, etc; and others are real Java applications such as a parser or a library.

The experiments were done with a collection of small to large programs, and they are divided into two sets. The first set considers the application of the balancing technique by only collapsing/projecting chains with a maximum of five chages. The second set considers the application of the balancing technique without any restriction (i.e., no chain is neccessary to project or collapse nodes). The following tables summarize the results of the experiments:

where

• Column Benchmark contains the names of the benchmarks;
• Column Nodes shows the size of the ET: the number of nodes (i.e., method invocations performed during the execution of the program) in the ET associated with each benchmark;
• Column Proj. / nodes / lenght shows the number of projected nodes inserted into the ET / the number of nodes that have been projected / and the average lenght of the nodes projected;
• Column Col. / nodes / lenght shows the number of colapsed nodes inserted into the ET / the number of nodes that have been colapsed / and the average lenght of the nodes colapsed;
• Column Proj. Time shows the time needed by the debugger to project the chains;
• Column Col. Time shows the time needed by the debugger to colapse the chains;
• Column Bal. Time shows the time needed by the debugger to balance the whole ET;
• Column Quest. shows the average number of questions done by the debugger before finding the bug in the original ET;
• Column Quest. Bal. shows the average number of questions done by the debugger before finding the bug in the balanced ET;
• Column % shows the improvement achieved with the balancing technique.

The last row shows the averages:

• Cells Proj. Time and Col. Time averages show the average time of projecting and colapsing a chain in all benchmarks;
• Cell Bal. Time average shows the average time of balancing all benchmarks (weighting the benchmarks according to their number of nodes);
• Cell Quest. average shows the average number of questions done by the debugger in all benchmarks in the original ET;
• Cell Quest. Bal. average shows the average number of questions done by the debugger in all benchmarks in the balanced ET;
• Cell % average shows the improvement achieved with the balancing technique in all benchmarks.

Evaluation of strategies for algorithmic debugging

All the strategies implemented in DDJ are described here:

• Josep Silva
  A Survey on Algorithmic Debugging Strategies
  Advances in Engineering Software. Volume 42 Issue 11, November, 2011
  Available: PDF preprint

The following table summarices the results of the experiments (this table is updated from time to time. We are currently implementing the strategy subterm dependency tracking and we will evaluate it and share the results soon).

Each row of the table represents the summary of a collection of experiments performed with the associated benchmark. In particular, for each benchmark, we produced its associated ET and assumed that the buggy node could be any node of the ET (i.e., any subcomputation in the execution of the program could be buggy). Therefore, we performed a different experiment for each possible case.

In particular, benchmark factoricer was debugged 62 times with each strategy; each time, the buggy node was a different node, and the results shown are the average number of questions performed by each strategy. Similarly, benchmark cglib was debugged 1216 times with each strategy, and so on.

where

• Column Benchmark contains the names of the benchmarks;
• Column Nodes shows the size of the ET: the number of nodes (i.e., method invocations performed during the execution of the program) in the ET associated with each benchmark;
• Column D&QH shows the number of questions asked (as an average) by Divide & Query by Hirunkitti;
• Column D&QS shows the number of questions asked (as an average) by Divide & Query by Shapiro;
• Column DR&Q shows the number of questions asked (as an average) by Divide by Rules & Query;
• Column HF shows the number of questions asked (as an average) by Heaviest First;
• Column MRF shows the number of questions asked (as an average) by More Rules First;
• Column HD-P shows the number of questions asked (as an average) by Hat Delta with the heuristic that computes the proportion of correct and wrong nodes;
• Column TD shows the number of questions asked (as an average) by Top-Down;
• Column HD-Y shows the number of questions asked (as an average) by Hat Delta with the heuristic that counts correct nodes (answered YES);
• Column HD-N shows the number of questions asked (as an average) by Hat Delta with the heuristic that counts wrong nodes (answered NO);
• Column SS shows the number of questions asked (as an average) by Single Stepping.