Regression testing is frequently performed in a time constrained environment. This paper explains how 0/1 knapsack solvers (e.g., greedy, dynamic programming, and the core algorithm) can identify a test suite reordering that rapidly covers the test requirements and always terminates within a specified testing time limit. We conducted experiments that reveal fundamental trade-offs in the (i) time and space costs that are associated with creating a reordered test suite and (ii) quality of the resulting prioritization. We find knapsack-based prioritizers that ignore the overlap in test case coverage incur a low time overhead and a moderate to high space overhead while creating prioritizations exhibiting a minor to modest decrease in effectiveness. We also find that the most sophisticated 0/1 knapsack solvers do not always identify the most effective prioritization, suggesting that overlap-aware prioritizers with a higher time overhead are useful in certain testing contexts.
Alspaugh, S., Walcott, K. R., Belanich, M., Kapfhammer, G. M., & Soffa, M. L. (2007). Efficient time-aware prioritization with knapsack solvers. Proceedings of the International Workshop on Empirical Assessment of Software Engineering Languages and Technologies.
Want to cite this paper? Look in the BiBTeX file of gkapfham/research-bibliography for the key "Alspaugh2007".