Test Case Permutation to Improve Execution Time

With the growing complexity of software, the number of test cases needed for eective validation is extremely large. Executing these large test suites is expensive, both in terms of time and energy. Cache misses are known to be one of the main factors contributing to execution time of a software. Cache misses are reduced by increasing the locality of memory references. For a single program run, compiler optimisations help improve data locality and code layout optimisations help improve spatial locality of instructions. Nevertheless, cache locality optimisations have not been proposed and explored across several program runs, which is the case when we run several test cases.
In this paper, we propose and evaluate a novel approach to improve instruction locality across test case runs. Our approach measures the distance between test case runs (number of different instructions). We then permute the test cases for execution so that the distance between neighboring test cases is minimised. We hypothesize that test cases executed in this new order for improved instruction locality will reduce time consumed.
We conduct a preliminary evaluation with four subject programs and test suites from the SIR repository to answer the following questions, 1. Is execution time of a test suite affected by the order in which test cases are executed? and 2. How does time consumed in executing our permutation compare to random test case permutations? We found that the order in which test cases are executed has a definite impact on execution time. The extent of impact varies, based on program characteristics and test cases. Our approach outperformed more than 97% of random test case permutations on 3 of the 4 subject programs and did better than 93% of the random orderings on the remaining subject program. Using the optimised permutation, we saw a maximum reduction of 7.4% over average random permutation execution time and 34.7% over the worst permutation.