More precisely what I did was minimization on an unusually slow example input, but I don't think I can share the code. The approach generalizes, though:
To verify performance, you would set it up to benchmark the code in question (in Haskell, this would probably mean using Criterion) and then assert that it was "fast enough" (probably relative to the size of the input).
In fact, I've done something similar to this.