My colleague did some analysis of batching and found through simulation that if the average failure rate of PRs is above a certain level, then the batch bisection strategy takes longer than simply testing one at a time.
Here are some plots of this using the worst-case bounds documented in the bors-ng README.md.
The original bors used a more simple system (it just tested one PR at a time all the time).
The one-at-a-time strategy is O(N), where N is the total number of pull requests.
The batching strategy is O(E log N), where N is again the total number of pull requests and E is the number of > pull requests that fail.
In the plot, you can see for example that if the PR failure rate is 30% and there is a batch of 10 PRs (i.e. 3/10 fail) then batch-bisection is no better than one-at-a-time (worst case). If there are more than 10 PRs in the batch then it’s worse.
I would like to use bors-ng but in our situation the batch size and failure rate may both be high. Would it be very difficult to switch to the one-at-a-time strategy if this becomes a problem?