In this Test Automation series, we investigate ways to optimise code integration and delivery speed without trading off software quality. In a previous article we explored the “when” to run tests during continuous integration. An equally important question to answer is “what” tests to run.

What are some industry guidelines we could apply to a codebase with thousands or millions of tests?

One line, thousands of tests

In a test setup that grew organically, without any optimizations, a developer edits one component file. The CI queues the whole test suite (let’s imagine 10,000 tests).

Each of these might only take a few milliseconds to run individually, but we’re already talking about 10 minutes of CI run. It might not look like much, but that’s enough for a developer to switch context and lose focus. Who never decided to go make themselves a coffee (quickly turning into a 30-minute break) while waiting for the test completion percentage to painfully reach 100%? Now multiply this by the number of developers in your team, and factor in a growing test corpus as your software matures.

Another insidious drawback of “mega” pipelines is that bundling every test behind one or a few triggers de-incentivizes code granularity and modularity when developing features.

This organic approach does not scale, so let’s see how we can improve it.

Funnel chart narrowing from 10,000 tests to 1,000 via dependency mapping, then to 100 via failure prediction

The low hanging fruit

Change Impact Analysis is the discipline of “identifying the potential consequences of a change, or estimating what needs to be modified to accomplish a change” (Bohner and Arnold). Basically: if we change this part of the app, what components or other pieces will break? What stakeholders will be impacted?

While businesses mainly use it for project estimates, we can also apply it to find which tests need to run after a specific component was updated. Through dependency mapping (“this component is imported by this module”, “this API route is used by this method”…), it becomes relatively easy to determine which subset of the software was changed, and thus which corresponding tests must run.

Or in Meta’s Engineering team’s own terms:

“A common approach to regression testing is to use information extracted from build metadata to determine which tests to run on a particular code change. By analyzing build dependencies between units of code, one can determine all tests that transitively depend on sources modified in that code change.”

Many test frameworks make this option available out of the box. For example Jest or Playwright exposes some kind of --only-changed flag:

// math.test.js

const { sum } = require('./math.js');

// With --onlyChanged, jest will only run this test if only sum changed (and if this is the only test importing sum)
test('adds 1 + 2 to equal 3', () => {
  expect(sum(1, 2)).toBe(3);
});

For many codebases, modular development (making sure components are scoped) and optimizing for short dependency chains are enough to reduce the number of tests run on each change by an order of magnitude. Our developer is now only running 1,000 tests, yay!

For a company at the scale of Meta, however, even this approach resulted in too many tests (10^4) being run on simple changes.

What’s likely to break?

In 2018, Meta started investigating this problem. They postulated that it’s impossible to know in advance and select the most minimal set of tests that would fail against a given change. As such, they didn’t need to chase a perfect solution. They just needed a good enough one.

So they invested in Predictive Test Selection (PTS), powered by machine learning, to select a subset of tests to run when a PR lands. The rest run later, in a “stabilization” phase of the CI/CD pipeline, ensuring complete coverage.

flowchart LR
    subgraph Training
        direction LR
        HC[Historic code change]
        T1[Test]
        FP[Failure or pass]
        TSM1[Test selection model]
        HC --> FP
        T1 --> FP
        FP --> TSM1
    end

    subgraph Prediction
        direction LR
        NC[New code change]
        T2[Test]
        TSM2[Test selection model]
        POF[Probability of failure]
        NC --> TSM2
        T2 --> TSM2
        TSM2 --> POF
    end

    TSM1 -.trained model.-> TSM2

Which features did the algorithm use to train itself?

  • Is the code change a “hot” portion of the codebase? What is the number of files touched in the areas with the most churn?
  • What’s the size of the change? Larger changes are more likely to break tests.
  • Who owns this code? Code changed by more contributors is likelier to break tests.
  • How often a test was added when updating this part of the codebase? How did this part of the codebase evolve?
  • How distant is the code from the tests? (Topology of the build dependencies)
  • History and results of recent test runs.

There are some costs in maintaining such a system: developing the model, gathering historical test results, training the model against these, measuring efficiency and calibrating, deploying the model and continuously retraining it. That’s why it should be considered only after hitting serious scale limitations.

Accounting for flaky tests is also needed to avoid polluting the training data. In their paper, Meta says they simply rerun any failing tests 10 times to eliminate any flakiness.

According to Meta, this technique reduced the total infrastructure cost of testing changes by a factor of two, while guaranteeing that over 95% of individual test failures and over 99.9% of faulty changes are still reported back to developers. And it’s not only Meta: Microsoft uses a similar technique, described in another paper from 2018. They claim to save 18% of CI test time while retaining a test outcome accuracy of 99.99%.

These are serious optimizations, further reducing the number of tests run on any changes by an extra order of magnitude. In our example, that’s how we go from running 10,000 tests to scoping down to 100.

But we didn’t run the other 9,900 tests!?

That’s right, and some bugs would possibly only surface by running them. Bugs a Predictive Test Selection model would otherwise miss.

For Meta, this optimisation trades correctness for latency: missed failures surface later, and rarely. A PTS approach favors faster failure signal over thoroughness of quality verification:

  • Less thorough testing at diff - and land-time would cause developers to learn about errors that need to be corrected at a later time, in the extreme case at the stabilization phase. This increases the need to context-switch between tasks, which negatively impacts developer productivity.
  • More thorough testing prior to landing a diff, although reducing the chances of detectable bug being committed to master branch, negatively impacts the cost of testing and/or latency of correctness signal provided to a developer.

Venn diagram from Meta’s paper showing failed tests approximated by build dependencies, static code references, and dynamic analysis Source: Predictive Test Selection, Meta

The other 9,900 tests run in a later phase of code integration (at Meta, this is the “stabilization” phase), ensuring complete coverage before the software is released to customers.

An alternative setup is entirely possible if early confidence in CI is too important: keep running the entire test corpus, and use this model only to reorder it, running the tests most likely to fail first.

Actionable items for every team

Implementing machine learning in any testing environment should only be done when hitting serious scale limitations. Most teams have other priorities to invest in first. It’s still an interesting technique to be aware of, and some companies have even productized it into a commercially available solution (disclaimer: I’ve never used these):

But there are more immediate action items for teams of any size:

  • Turn on --only-changed flags in your test frameworks. This comes with extra benefits:
  • Make sure you regularly reassess the quality and relevance of your test corpus. This is something Google touches on in their CI efficacy blog post. A test that never fails is a useless test that consumes important resources and time. It should be removed.
  • Good data is the prerequisite of any optimisation at scale: historical test and CI results, run frequency, and correlation with codebase changes.

I’m Théo Penavaire, a senior CI/CD and Test Automation Engineer with more than 6 years of experience working with codebases at scale. If testing times are becoming a bottleneck for you, reach out and we’ll figure out an optimisation strategy that works for your environment and constraints.

The next part of this test automation series will land soon. Subscribe if you’d like it in your inbox.

Sources