DRMacIver's Notebook
Reducing the Reduction Pass Ordering Problem
Reducing the Reduction Pass Ordering Problem
Most test-case reducers are composed of many different passes, each performing a different class of operation. For example, you might have a pass that reorders values and a pass that deletes them.
The reduction pass ordering problem is that what order you run these passes in can have a huge impact on performance, and a moderate impact on the quality of end result.
I’m starting to be of the opinion however that this is an illusion, caused by the fact that our reduction passes are too large. If you have a reduction pass that, say, tries deleting each element, then when you start from \(N\) elements you could instead just have \(N\) reduction passes that try deleting a single element.
Once you’ve made your reduction passes this small, running any given pass is very cheap, and it seems like then most orderings do a pretty good job. For example, the following seems to work pretty well as the core loop of a reducer:
- Generate the set of all reduction passes that could have an effect on the current reducer.
- Run them in a random order.
This works particularly well if your passes are adaptive, so that they make \(O(1)\) SUT calls when they fail to do anything and may make up to \(O(\log(k))\) calls when making \(k\) to achieve progress equivalent to running \(k\) appropriate choices of pass from the same category (e.g. deleting an interval around the element).
It does seem possible to do better than uniformly at random for choosing these, but there doesn’t really seem to be more than a factor of two variation regardless of how clever you are with your ordering (unless I’m missing an option that is better than anything I’ve tried so far).