DRMacIver's Notebook

Reducer Pass Budgeting

Published

2019-01-14

One of the hard problems in designing test-case reducers is pass ordering: You’ve split the reducer up into a number of different passes, now you want to know what order to run them in.

A lot of why this is tricky is that some passes you just really don’t want to run until you have to because they’re much more expensive. I’m currently exploring a solution to this problem that mostly avoids it by just making that not the case.

The solution is budgeting - running a reduction pass with a maximum number of calls it’s allowed to make.

The following algorithm seems to work fairly well:

1. Set the budget to infinity, mark all passes as active.
2. For each active reduction pass:
   1. Run it, but halt it once it has made a number of unsuccessful calls that exceed the current budget.
   2. If it succeeded, set the budget to something appropriate. I’m currently trying double the mean number of calls made by a successful pass on this run through.
   3. If it failed, mark the pass as inactive.
3. If the number of active passes is one or fewer, mark all passes as active.
4. If no passes made progress, halt (note that the budget is infinite unless a pass has made progress, so this doesn’t affect correctness). Otherwise go back to step 2.

This seems to do a pretty decent job of keeping the badly behaved passes under control while still making good progress.

Other things I have tried:

1. Starting the budget low and working upwards causes a lot of wasted work.
2. Being more aggressive with lowering the budget on each pass does the same.
3. Allowing just a single pass to remain active tends to result in a lot of pointless small shrinks and not much useful progress.