Note that "pick the commit with best expected information gain" in git_bayesect isn't optimal even in the no overhead regime. I provide a counterexample in the writeup, which implies ajb's heuristic is also not optimal. I don't see a tractable way to compute the optimal policy.

One idea: if you always spend time testing equal to your constant overhead, I think you're guaranteed to be not more than 2x off optimal.

(and agreed with ajb on "just use ccache" in practice!)