Test Case Permutation to Improve Execution Time

Panos Stratis, Ajitha Rajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAutomated Software Engineering (ASE), 2016 31st IEEE/ACM International Conference on
Place of PublicationSingapore
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages6
ISBN (Electronic)978-1-4503-3845-5
ISBN (Print)978-1-5090-5571-5
Publication statusPublished - 6 Oct 2016
Event31st IEEE/ACM International Conference on Automated Software Engineering - , Singapore
Duration: 3 Sep 20167 Sep 2016


Conference31st IEEE/ACM International Conference on Automated Software Engineering
Abbreviated titleASE 2016
Internet address


Dive into the research topics of 'Test Case Permutation to Improve Execution Time'. Together they form a unique fingerprint.

Cite this