Improve PHPUnit parallel split_group generation algorithm

Given the constraints that the PHPUnit test classes need to be run
in their original order, that we might have incomplete information
about the test duration, and that the test durations vary significantly
(from 0 seconds to many tens of seconds), we want to make best efforts
to create split_groups with similar durations (and in so doing,
minimise the duration of the split_group with the longest runtime).

The existing algorithm takes the number of tests and the total
duration of tests and tries to create an even split by either duration
or test count (assuming that the zero-duration tests actually take a
similar, non-zero time to execute). This algorithm can potentially
place two long-running tests into the same group - the group might be
close to its duration limit, and the next test may be a long-running
test. In such a case, the group can end up significantly bigger than
desired.

Change the group-splitting algorithm to chunk the tests into up to
200 chunks, and assign the chunks to split_groups using a dynamic
programming algorithm that uses backtracking to find an optimal
allocation of chunks to split_groups.

Bug: T389189
Change-Id: I61ae44f3fca4a890947ea1499a99690a4fcc2bb8

0 files changed, 0 insertions, 0 deletions