Tag Archives: Concurrency

Concurrent Test Execution: Partitioning the Tests

When you execute your test suite across multiple machines, the tests should run concurrently. You want each test to run exactly once, so it’s important to partition the work correctly and efficiently.

You also want the total durations of the machines’ tests to be similar, so that you don’t have one machine still running long after the others have finished.

Here’s one way to do that.

The test machines will need:

  • A list of the names of the tests to execute.
  • A list of the names of the machines participating.

The names of the tests should be arranged by their expected durations: longest to shortest.

The names of the machines should be arranged by the expected “power” (speed of execution): fastest to slowest.

Each test machine makes some initial computations:

  • The count n of test machines participating.
  • The 0-based index i of its own machine name among the listed machine names.

In order for the testing to be distributed more or less evenly (by duration) among the test machines, each machine allocates to itself some of the tests.

The first, and fastest, machine (i == 0) is assigned:

  • The first (longest) test from the first n tests.
  • The last (shortest) test from the next n tests.
  • The first (longest) test from the next n tests.
  • The last (shortest) test from the next n tests.
  • And so forth.

More generally, for machine i, the tests are those among the listed tests that are at the following 0-based indexes:

  • n
  • 2ni – 1
  • 2n + i
  • 4ni – 1
  • 4n + i

You can think of it this in a simple way. If there are four test machines, then the tests — listed from longest to shortest — would be allocated to the machines as follows:   0,1,2,3;   3,2,1,0;   0,1,2,3;   3,2,1,0;   ….

This constitutes a partition (each test is allocated exactly once), and tends to distribute execution time evenly across the test machines.

Advertisements