AGA: An Accelerated Greedy Additional Algorithm for Test Case Prioritization

Feng Li, Jianyi Zhou, Yinzhu Li, Dan Hao, Lu Zhang

Abstract

Test Case Prioritization (TCP) is a critical technique in modern software engineering, designed to order test cases such that those with the highest fault-detection capability are executed earliest. While the Greedy Additional (GA) algorithm is widely regarded as the "gold standard" for effectiveness, its $O(m^2n)$ time complexity renders it impractical for large-scale industrial applications. This paper presents the Accelerated Greedy Additional (AGA) algorithm, which optimizes the standard GA approach through two primary mechanisms: specialized data structures to reduce computational complexity and a heuristic iteration limit to eliminate redundant processing. Experimental results across 55 open-source projects and 22 industrial subjects at Baidu demonstrate that AGA achieves speedups of up to 44x while maintaining the same fault-detection effectiveness as the original GA algorithm.

Introduction

In the era of continuous integration and rapid deployment, regression testing often becomes a bottleneck. Large-scale systems, such as those managed by Google or Baidu, may involve millions of test cases. Test Case Prioritization (TCP) addresses this by reordering tests to maximize early fault detection, measured by the Average Percentage of Faults Detected (APFD).

Among existing TCP techniques, the Greedy Additional (GA) algorithm is the most effective. It iteratively selects the test case covering the maximum number of previously uncovered program elements. However, its performance scales poorly with the number of test cases ($m$) and program elements ($n$). As software systems grow, the computational overhead of GA becomes prohibitive, leading many practitioners to settle for faster but less effective alternatives.

The AGA Algorithm

AGA optimizes the traditional GA approach through two distinct components: AGA_C and AGA_I.

AGA_C: Reducing Time Complexity

Standard implementations of GA often rescan the entire coverage matrix in every iteration to identify the next best test case. AGA_C replaces this exhaustive search with specialized data structures:

  • Forward and Inverted Indices: By mapping code elements back to the tests that cover them, the algorithm avoids scanning irrelevant data.
  • Incremental Updates: Instead of a full scan, AGA_C only updates the "uncovered" counts for tests that share elements with the most recently selected test case. This optimization reduces the complexity from $O(m^2n)$ to $O(kmn)$, where $k$ represents the number of iterations.

AGA_I: Reducing Iteration Count

The standard GA algorithm continues its selection process until all tests are prioritized, resetting the "covered" status every time 100% coverage is reached. The authors observed that the probability of finding new faults drops significantly after the first few coverage cycles. AGA_I introduces a heuristic limit—specifically 10 iterations—after which the algorithm switches to a computationally cheaper "Greedy Total" strategy. This prevents the algorithm from wasting time on low-utility iterations that do not improve fault detection.

Experimental Evaluation

The researchers evaluated AGA against standard GA and the FAST algorithm (a common speed-oriented alternative) using a robust dataset:

  • Open-Source Subjects: 55 Java projects from GitHub and the Defects4J benchmark, ranging from 1,600 to 177,000 lines of code.
  • Industrial Subjects: 22 large-scale C projects from Baidu, featuring up to 500,000 lines of code and over 4,000 test cases.

Key Results

1. Significant Performance Gains

AGA demonstrated substantial speed improvements over the standard GA algorithm. In open-source projects, AGA was on average 5.95x faster. In the Baidu industrial environment, the speedup was even more pronounced, reaching an average of 44.27x. Furthermore, AGA outperformed the FAST algorithm, being 4.29x faster on average while providing better prioritization quality.

2. Preservation of Effectiveness

Crucially, the speedups did not come at the cost of accuracy. The APFD scores for AGA were statistically indistinguishable from the standard GA algorithm. This confirms that the "10-iteration" rule and the indexing optimizations successfully preserve the fault-detection capabilities of the original greedy approach.

3. Industrial Viability

The dramatic speedup in the Baidu case study suggests that AGA is uniquely suited for large-scale production environments where traditional greedy algorithms were previously considered too slow to implement.

Discussion and Limitations

While AGA represents a significant step forward, some limitations remain. The "10-iteration" rule is a heuristic derived from the study's subjects; while it proved robust across 77 diverse projects, different software domains might require tuning this threshold. Additionally, the current evaluation focused on statement and method coverage. Future research could explore how AGA performs with more complex criteria, such as branch or path coverage, and further validate its performance against a wider array of real-world historical faults.

Conclusion

The Accelerated Greedy Additional (AGA) algorithm effectively bridges the gap between theoretical effectiveness and industrial efficiency. By optimizing data access patterns and eliminating redundant iterations, AGA allows developers to utilize the high-performance Greedy Additional logic in large-scale systems without the traditional time penalty. This makes high-quality test case prioritization accessible for even the most demanding CI/CD pipelines.

Summary updated

BibTeX
@article{li2022aga,
  author = {Feng Li and Jianyi Zhou and Yinzhu Li and Dan Hao and Lu Zhang},
  title = {{AGA: An Accelerated Greedy Additional Algorithm for Test Case Prioritization}},
  journal = {IEEE Trans. Software Eng.},
  year = {2022},
  doi = {10.1109/tse.2021.3137929},
}
Figure