More History

We recently added history files to our pitest PR workflows to avoid expensive computation when there are multiple pushes to a PR. It worked as designed, but the speedup it provided was very modest. One reason was that the workflows were quite fast to begin with, so the potential savings were never large. The other reason is that I have been lazy and forgetful for the last 10 years.

The History of Pitest History

When I first implemented incremental analysis in pitest back in 2011, I wrote a list of five possible ways history data could be used to speed up mutation testing.

1. If an infinite loop was detected in the last run, and the class has not changed then it can be assumed that this mutation still results in an infinite loop.
2. If a mutation was killed in the last run and neither the class under test or the killing test has changed, then it can be assumed that this mutation is still killed.
3. If a mutation survived in the last run, no new tests cover it, and none of the covering tests have changed, then it must still survive.
4. If a mutation was previously killed, but the class or killing test has changed then it is likely that the last killing test will still kill it and it should therefore be prioritised above others.
5. If a number of mutations for a class previously survived but the class has changed, then it is likely that these mutations will still survive. If they are enabled simultaneously and cannot be killed as a single meta mutant, then the mutations need not be analysed individually.

The first three use the historic result to infer the current result without inserting a mutant into the JVM or running any tests against it. These strategies were implemented in the first release, and have been how pitest’s incremental analysis has worked for the last ten years.

The last two ideas were never implemented. I’m not entirely sure how useful the last one would be, but optimisation number 4 definitely makes sense and is relatively straight forward to implement. So straight forward in fact, that I assumed I must have done it for that first release and never checked until now.

Reusing past killing tests is particularly relevant when running in a PR as described in our earlier post. In this scenario, as Arcmutate is already limiting analysis to altered classes, it is highly likely that the mutated classes will have changed between runs. The other optimisations can’t be applied, but the killing test optimisation can. In most cases it means we can select a killing test on our first attempt, potentially saving significant CPU time.

So, only ten years late, optimisation 4 is finally available.