6 ms·

Faster CI with Selective Testing

45 points by lihaoyi 2y ago

dshacker 2y ago
Hah, funnily enough this is exactly what I was working on this year :)
brunoarueira 2y ago
On my last job, since the project is based on Ruby on Rails, we implementei this https://github.com/toptal/crystalball https://github.com/toptal/crystalball and additional modifications based on the gitlab setup. After that, the pull requests test suite runs pretty fast
hinkley 2y ago
Years ago there was a system that would track code coverage per test and would rerun only the tests that intersected with the lines you changed., as a more specific watch command. But watch itself still has a lot of value, because it starts in the gap between when you save changes and get curious about the state of the tests.
reynaldi 2y ago
Interesting, I just now know about selective testing after reading this post. But, now I wonder when do you do selective testing and when do you just break up the codebase?
- lihaoyi 2y ago
  Even if you break up a codebase, you need selective testing. Let's say you have 100 small repos, and make a change to one. How confident are you in the changed repo's test suite that you can guarantee there are no bugs that will affect other related repos? If not, which other repos do you test with your change to get that confidence?
  - menaerus 2y ago
    Splitting the code into 10s or 100s repositories is a cancer. It's almost as if you're intentionally trying to make your dev life miserable by pretending that you speeded up the dev turnaround times by not running the full test circle.
- atmosx 2y ago
  You break up the codebase when the communication patterns in the org calls for it e.g. engineers complain about it. It’s not a purely technical problem.
deathanatos 2y ago
Path-based selection of tests, in every single CI system I have ever seen it implemented in, is wrong. TFA thankfully gets the "run the downstream dependent tests" which is the biggest miss, but even then, you can get the wrong answer. Say I have the following: paths a/* need to run tests A, and paths b/* need to runs tests B. I configure the CI system as such. Commit A' is pushed, changing paths under a/* only, so the CI runs tests A, only. The tests fail. A separate engineer, quickly afterwards (perhaps, lets say, even before the prior commit has finished; this could just be two quick merges) pushes commit B', changing paths under b/* only. The CI system runs tests B only, and they all pass so the commit is marked green incorrectly. Automated deployment systems, or other engineers, proceed to see passing tests, and use a broken but "green" build. Since ever rarely do I see the downstream-tests requirement correctly done, and almost always the "successive miss" bug, I'm convinced for these reasons path based is just basically a broken approach. I think a better approach is to a.) compute your inputs to the tests, and cache results, and b.) have the CI system be able to suss out flakes and non-determinism. But I think a.) is actually quite difficult (enough to be one of the hardest problems in CS, remember?) and b.) is not at all well supported by the current CI systems. (I have seen both of these approaches result in bad (known bad, had the tests run!) builds pushed to production. The common complaint is "but CI is slow" followed by a need to do something, but without care towards the correctness of that something. Responsibility for a slow CI is often diffused across the whole company, managers do not want to do the hard task of getting their engineers to fix the tests they're responsible for, since that just doesn't get a promotion. So CI remains slow, and brittle.)
- emidln 2y ago
  It's possible to use bazel to do this. You need to be very explicit (The Bazel Way(tm)), but in exchange, you can ask the graph for everything that is an rdep of a given file. This isn't always necessary in bazel (if you avoid weird integration targets, deploy targets, etc) where `bazel test //...` generally does this by default anyway. It's sometimes necessary to manually express due to incomplete graphs, tests that are not executed every time (for non-determinism, execution cost, etc), and a few other reasons but at least it's possible.
  - 2y ago
pluto_modadic 2y ago
I think... an approach that might work... is testing the immediate unit first (fastest, guess by changed files), then dependent tests you didn't test yet (e.g., guessing based on imports), then integration tests that use the feature, then full tests (regardless), then fuzzing... order the test by what is likely to fail quickest. you could even have deployed it during the dependent tests (and run the full and fuzz tests overnight), and have it report back that "no, the commit actually didn't pass". or, bonus points, if you just made a new test case as part of a bugfix or regression ticket, it should definitely test that test unit you just modified first. any commit in a tests/ folder or `test_`. I mean... maybe it should be running on your laptop...
rurban 2y ago
When your CI is too big, do at least a random selection. So you'll catch bugs at least as somewhen. With selective testing you just ignore them
motorest 2y ago
The premise of this article sounds an awful lot like a solution desperately searching for a problem. The scenario used to drive this idea is a slippery slope fallacy that tests can take over an hour to run after years. That's rather dubious, but still this leaves out the fact that tests can be run in parallel. In fact, that is also a necessary condition of selective testing. So why bother with introducing with yet more complexity? To make matters worse if your project grows so large that your hypothetical tests take over an hour to run, it sounds like the project would already be broken down into modules. That, alone, already allows tests to only run if a specific part of the project run. So it's clear that test run time is not a problem that justifies throwing complexity to solve it. Excluding the test runtime argument, is there anything at all that justifies this?
- mhlakhani 2y ago
  In large mono-repos, like this one is presumably targeting, running all tests in the repo for a given PR would take years (maybe even decades/centuries) of compute time. You have to do some level of test selection, and there are full time engineers who just work on optimizing this. The test runtime argument is the main one IMO. (source: while I did not work on this at a prior job, I worked closely with the team that did this work).
  - motorest 2y ago
    > In large mono-repos, like this one is presumably targeting, running all tests in the repo for a given PR would take years (maybe even decades/centuries) of compute time. No, not really. That's a silly example. Your assertion makes as much sense as arguing that your monorepo would take years to build because all code is tracked by the same repo. It doesn't it, does it? Why? How you store your code has nothing to do with how you build it.
    - danpalmer 2y ago
      Being a monorepo is typically about more than just how code is stored, it leads to very different practices about dependency management, building, etc. On the monorepo I work on, the fact it is a monorepo is intrinsically linked to the build, testing, and deployment processes in many ways. The ideal is that your build system by-necessity contains the data to be able to selectively test – typically the case if you're linking code in some way. You import a library, now your tests get run if that library changes. As the article suggests, this breaks down over service boundaries, but as you suggest, you still hopefully have modules you can link up. The problem is when you have hundreds of services, maintaining those dependencies manually could be hard. When you have thousands it may be nearly impossible. When you have hundreds of thousands it may be impossible. I think applying ML to that problem so that you can incrementally understand the ever changing dependencies across services. I can also assure you that however smart the build system is, there will always be spooky action at a distance between components.
turboponyy 2y ago
Nix solves this as a byproduct (as it does with many things) of its design. You can have your tests be a "build", where the build succeeds if your tests pass. Any builds can be cached, which means you're essentially caching tests you've already run. Since Nix is deterministic, you never have to rerun any tests until anything about them that could change the evaluation changes.
- fire_lake 2y ago
  Nix is mostly deterministic due to lots of effort by the community but it’s hard to maintain full determinism in your own tests.
  - IshKebab 2y ago
    Basically the only sane answer is Bazel (or similar). We currently use path based test running because I couldn't convince people it was wrong, and it regularly results in `master` being broken. I don't really have a great answer for when that stops scaling - especially for low level things e.g. when Android changes bionic do they run every test because everything depends on it? Technically they should. The only other cool technique I know of is coverage-based test ranking, but as far as I know it's only used in silicon verification. Basically if you have more tests than you can run, only run the top N based on coverage metrics.
  - turboponyy 2y ago
    There's always the escape hatch of marking a derivation as impure. However, most tests should really have no reason to be impure by design. And tests that do depend on side effects might as well be re-evaluated every time.
    - fire_lake 2y ago
      The problem is it’s hard to know which tests are impure.
ay 2y ago
The better you can describe the interdependencies between the components, the more chances the selective approaches have. However, often if you knew about a given dependency, you might have avoided bugs in the first place! A simple scenario to illustrate what I have in mind: a system with two plugins, A and B. They provide completely independent functionality, and are otherwise entirely unrelated. Plugin A adds a new function which allocates a large amount of memory. All tests for A pass. All tests for B pass. The tests for B when A is loaded fail. Turns out A has done two things: 1) the new memory allocation together with the existing memory allocations in B causes an OOM when both are used. 2) the new function addition offset the function table in the main program, and the plugin B was relying on a haedcoded function index, which didn’t change, by sheer chance, for years. Those are the the tales based on the real world experience, which made me abandon the idea for the project I am working on (VPP) - the trade offs didn’t seem to be worth it. For some other scenario they may be different though, so thanks for looking into this issue!
Ar-Curunir 2y ago
I’ve wanted something like this deeply integrated into my programming language. The compiler already knows that fine-grained dependency information; it should be able to use that to ignore tests for modules that are not in the dependency subgraph of the diff
atq2119 2y ago
Another helpful tool that should be mentioned in this context is the idea of merge trains, where a thorough test run is amortized over many commits (that should each have first received lighter selective testing). This doesn't necessarily reduce the latency until a commit lands, though it might by reducing the overall load on the testing infrastructure. But it ensures that all commits ultimately get the same test coverage with less redundant test expense. That avoids the problem where a change in component A can accidentally break a test that is only tested on changes to component B. (It also eliminates regressions that occur when two changes land that have a semantic conflict that wasn't detected because there was no textual conflict and the changes were only tested independently.)
the_gipsy 2y ago
> Selective testing is a key technique necessary for working with any large codebase or monorepo: picking which tests to run to validate a change or pull-request, because running every test every time is costly and slow. Wait, is it really? Or is it preemptively admitting defeat?
gorset 2y ago
Selective testing is great also for smaller projects to help keep velocity high for merging and working with branches with many commits. I implemented selective testing using bazel for a CI some years ago, and it was painful to get it right. When finished even bigger branches would only take seconds-to-minutes to go through the pipeline, which was a significant improvement from the ~30 minutes build when I started working with the project, even though the project size grew a lot. Glad to see mill-build is prioritizing this feature.
k3vinw 2y ago
Another approach that helped us was relocating integration tests out of the main CI build which were costly and not critical to run as part of every CI build. We now run them daily against the latest version of the build.
lbriner 2y ago
Like others, I think this is a solution describing an idealised problem but it very quickly breaks down. Firstly, if we could accurately know the dependencies that potentially affected a top-level test, we are not like to have a problem in the first place. Our code base is not particularly complex and is probably around 15 libraries and a web app + api in a single solution. A change to something in a library potentially affects about 50 places (but might not affect any of these) and most of the time there is no direct/easy visibility of what calls what to call what to call what. There is also no correlation between folders and top-level tests. Most code is shared, how would that work? Secondly, we use some front-end code (like many on HN), where a simple change could break every single other front-end page. Might be bad architecture but that is what it is and so any front-end change would need to run every UI change. The breaks might be subtle like a specific button now disappears behind a sidebar. Not noticeable on the other pages but will definitely break a test. Thirdly, you have to run all of your tests before deploying to production anyway so the fact you might get some fast feedback early on is nice but most likely you won't notice the bad stuff until the 45 minutes test suite has run at which point, you have blocked production and will have to prove that you have fixed it before waiting another 45 minutes. Fourthly, a big problem for us (maybe 50% of the failures) are flaky tests (maybe caused by flaky code, timing issues, database state issue or just hardware problems) and running selective tests doesn't deal with this. And lastly, we already run tests somewhat selectively - we run unit tests on branch uilds before building main, we have a number of test projects in parallel but still with less than perfect Developers, less than perfect Architecture, less than perfect CI tools and environments, I think we are just left to try and incrementally improve things by identifying parallelisation opportunities, not over-testing functionality that is not on the main paths etc.

45 points by lihaoyi 2y ago

Hah, funnily enough this is exactly what I was working on this year :)

On my last job, since the project is based on Ruby on Rails, we implementei this https://github.com/toptal/crystalball https://github.com/toptal/crystalball and additional modifications based on the gitlab setup. After that, the pull requests test suite runs pretty fast

hinkley 2y ago

Years ago there was a system that would track code coverage per test and would rerun only the tests that intersected with the lines you changed., as a more specific watch command. But watch itself still has a lot of value, because it starts in the gap between when you save changes and get curious about the state of the tests.

reynaldi 2y ago

Interesting, I just now know about selective testing after reading this post. But, now I wonder when do you do selective testing and when do you just break up the codebase?

lihaoyi 2y ago
Even if you break up a codebase, you need selective testing. Let's say you have 100 small repos, and make a change to one. How confident are you in the changed repo's test suite that you can guarantee there are no bugs that will affect other related repos? If not, which other repos do you test with your change to get that confidence?
- menaerus 2y ago
  Splitting the code into 10s or 100s repositories is a cancer. It's almost as if you're intentionally trying to make your dev life miserable by pretending that you speeded up the dev turnaround times by not running the full test circle.
atmosx 2y ago
You break up the codebase when the communication patterns in the org calls for it e.g. engineers complain about it. It’s not a purely technical problem.

deathanatos 2y ago

Path-based selection of tests, in every single CI system I have ever seen it implemented in, is wrong. TFA thankfully gets the "run the downstream dependent tests" which is the biggest miss, but even then, you can get the wrong answer. Say I have the following: paths a/* need to run tests A, and paths b/* need to runs tests B. I configure the CI system as such. Commit A' is pushed, changing paths under a/* only, so the CI runs tests A, only. The tests fail. A separate engineer, quickly afterwards (perhaps, lets say, even before the prior commit has finished; this could just be two quick merges) pushes commit B', changing paths under b/* only. The CI system runs tests B only, and they all pass so the commit is marked green incorrectly. Automated deployment systems, or other engineers, proceed to see passing tests, and use a broken but "green" build. Since ever rarely do I see the downstream-tests requirement correctly done, and almost always the "successive miss" bug, I'm convinced for these reasons path based is just basically a broken approach. I think a better approach is to a.) compute your inputs to the tests, and cache results, and b.) have the CI system be able to suss out flakes and non-determinism. But I think a.) is actually quite difficult (enough to be one of the hardest problems in CS, remember?) and b.) is not at all well supported by the current CI systems. (I have seen both of these approaches result in bad (known bad, had the tests run!) builds pushed to production. The common complaint is "but CI is slow" followed by a need to do something, but without care towards the correctness of that something. Responsibility for a slow CI is often diffused across the whole company, managers do not want to do the hard task of getting their engineers to fix the tests they're responsible for, since that just doesn't get a promotion. So CI remains slow, and brittle.)

emidln 2y ago
It's possible to use bazel to do this. You need to be very explicit (The Bazel Way(tm)), but in exchange, you can ask the graph for everything that is an rdep of a given file. This isn't always necessary in bazel (if you avoid weird integration targets, deploy targets, etc) where `bazel test //...` generally does this by default anyway. It's sometimes necessary to manually express due to incomplete graphs, tests that are not executed every time (for non-determinism, execution cost, etc), and a few other reasons but at least it's possible.
- 2y ago

pluto_modadic 2y ago

I think... an approach that might work... is testing the immediate unit first (fastest, guess by changed files), then dependent tests you didn't test yet (e.g., guessing based on imports), then integration tests that use the feature, then full tests (regardless), then fuzzing... order the test by what is likely to fail quickest. you could even have deployed it during the dependent tests (and run the full and fuzz tests overnight), and have it report back that "no, the commit actually didn't pass". or, bonus points, if you just made a new test case as part of a bugfix or regression ticket, it should definitely test that test unit you just modified first. any commit in a tests/ folder or `test_`. I mean... maybe it should be running on your laptop...

rurban 2y ago

When your CI is too big, do at least a random selection. So you'll catch bugs at least as somewhen. With selective testing you just ignore them

motorest 2y ago

The premise of this article sounds an awful lot like a solution desperately searching for a problem. The scenario used to drive this idea is a slippery slope fallacy that tests can take over an hour to run after years. That's rather dubious, but still this leaves out the fact that tests can be run in parallel. In fact, that is also a necessary condition of selective testing. So why bother with introducing with yet more complexity? To make matters worse if your project grows so large that your hypothetical tests take over an hour to run, it sounds like the project would already be broken down into modules. That, alone, already allows tests to only run if a specific part of the project run. So it's clear that test run time is not a problem that justifies throwing complexity to solve it. Excluding the test runtime argument, is there anything at all that justifies this?

mhlakhani 2y ago
In large mono-repos, like this one is presumably targeting, running all tests in the repo for a given PR would take years (maybe even decades/centuries) of compute time. You have to do some level of test selection, and there are full time engineers who just work on optimizing this. The test runtime argument is the main one IMO. (source: while I did not work on this at a prior job, I worked closely with the team that did this work).
- motorest 2y ago
  > In large mono-repos, like this one is presumably targeting, running all tests in the repo for a given PR would take years (maybe even decades/centuries) of compute time. No, not really. That's a silly example. Your assertion makes as much sense as arguing that your monorepo would take years to build because all code is tracked by the same repo. It doesn't it, does it? Why? How you store your code has nothing to do with how you build it.
  - danpalmer 2y ago
    Being a monorepo is typically about more than just how code is stored, it leads to very different practices about dependency management, building, etc. On the monorepo I work on, the fact it is a monorepo is intrinsically linked to the build, testing, and deployment processes in many ways. The ideal is that your build system by-necessity contains the data to be able to selectively test – typically the case if you're linking code in some way. You import a library, now your tests get run if that library changes. As the article suggests, this breaks down over service boundaries, but as you suggest, you still hopefully have modules you can link up. The problem is when you have hundreds of services, maintaining those dependencies manually could be hard. When you have thousands it may be nearly impossible. When you have hundreds of thousands it may be impossible. I think applying ML to that problem so that you can incrementally understand the ever changing dependencies across services. I can also assure you that however smart the build system is, there will always be spooky action at a distance between components.

turboponyy 2y ago

Nix solves this as a byproduct (as it does with many things) of its design. You can have your tests be a "build", where the build succeeds if your tests pass. Any builds can be cached, which means you're essentially caching tests you've already run. Since Nix is deterministic, you never have to rerun any tests until anything about them that could change the evaluation changes.

fire_lake 2y ago
Nix is mostly deterministic due to lots of effort by the community but it’s hard to maintain full determinism in your own tests.
- IshKebab 2y ago
  Basically the only sane answer is Bazel (or similar). We currently use path based test running because I couldn't convince people it was wrong, and it regularly results in `master` being broken. I don't really have a great answer for when that stops scaling - especially for low level things e.g. when Android changes bionic do they run every test because everything depends on it? Technically they should. The only other cool technique I know of is coverage-based test ranking, but as far as I know it's only used in silicon verification. Basically if you have more tests than you can run, only run the top N based on coverage metrics.
- turboponyy 2y ago
  There's always the escape hatch of marking a derivation as impure. However, most tests should really have no reason to be impure by design. And tests that do depend on side effects might as well be re-evaluated every time.
  - fire_lake 2y ago
    The problem is it’s hard to know which tests are impure.

ay 2y ago

The better you can describe the interdependencies between the components, the more chances the selective approaches have. However, often if you knew about a given dependency, you might have avoided bugs in the first place! A simple scenario to illustrate what I have in mind: a system with two plugins, A and B. They provide completely independent functionality, and are otherwise entirely unrelated. Plugin A adds a new function which allocates a large amount of memory. All tests for A pass. All tests for B pass. The tests for B when A is loaded fail. Turns out A has done two things: 1) the new memory allocation together with the existing memory allocations in B causes an OOM when both are used. 2) the new function addition offset the function table in the main program, and the plugin B was relying on a haedcoded function index, which didn’t change, by sheer chance, for years. Those are the the tales based on the real world experience, which made me abandon the idea for the project I am working on (VPP) - the trade offs didn’t seem to be worth it. For some other scenario they may be different though, so thanks for looking into this issue!

Ar-Curunir 2y ago

I’ve wanted something like this deeply integrated into my programming language. The compiler already knows that fine-grained dependency information; it should be able to use that to ignore tests for modules that are not in the dependency subgraph of the diff

atq2119 2y ago

Another helpful tool that should be mentioned in this context is the idea of merge trains, where a thorough test run is amortized over many commits (that should each have first received lighter selective testing). This doesn't necessarily reduce the latency until a commit lands, though it might by reducing the overall load on the testing infrastructure. But it ensures that all commits ultimately get the same test coverage with less redundant test expense. That avoids the problem where a change in component A can accidentally break a test that is only tested on changes to component B. (It also eliminates regressions that occur when two changes land that have a semantic conflict that wasn't detected because there was no textual conflict and the changes were only tested independently.)

the_gipsy 2y ago

> Selective testing is a key technique necessary for working with any large codebase or monorepo: picking which tests to run to validate a change or pull-request, because running every test every time is costly and slow. Wait, is it really? Or is it preemptively admitting defeat?

gorset 2y ago

Selective testing is great also for smaller projects to help keep velocity high for merging and working with branches with many commits. I implemented selective testing using bazel for a CI some years ago, and it was painful to get it right. When finished even bigger branches would only take seconds-to-minutes to go through the pipeline, which was a significant improvement from the ~30 minutes build when I started working with the project, even though the project size grew a lot. Glad to see mill-build is prioritizing this feature.

k3vinw 2y ago

Another approach that helped us was relocating integration tests out of the main CI build which were costly and not critical to run as part of every CI build. We now run them daily against the latest version of the build.

lbriner 2y ago

Like others, I think this is a solution describing an idealised problem but it very quickly breaks down. Firstly, if we could accurately know the dependencies that potentially affected a top-level test, we are not like to have a problem in the first place. Our code base is not particularly complex and is probably around 15 libraries and a web app + api in a single solution. A change to something in a library potentially affects about 50 places (but might not affect any of these) and most of the time there is no direct/easy visibility of what calls what to call what to call what. There is also no correlation between folders and top-level tests. Most code is shared, how would that work? Secondly, we use some front-end code (like many on HN), where a simple change could break every single other front-end page. Might be bad architecture but that is what it is and so any front-end change would need to run every UI change. The breaks might be subtle like a specific button now disappears behind a sidebar. Not noticeable on the other pages but will definitely break a test. Thirdly, you have to run all of your tests before deploying to production anyway so the fact you might get some fast feedback early on is nice but most likely you won't notice the bad stuff until the 45 minutes test suite has run at which point, you have blocked production and will have to prove that you have fixed it before waiting another 45 minutes. Fourthly, a big problem for us (maybe 50% of the failures) are flaky tests (maybe caused by flaky code, timing issues, database state issue or just hardware problems) and running selective tests doesn't deal with this. And lastly, we already run tests somewhat selectively - we run unit tests on branch uilds before building main, we have a number of test projects in parallel but still with less than perfect Developers, less than perfect Architecture, less than perfect CI tools and environments, I think we are just left to try and incrementally improve things by identifying parallelisation opportunities, not over-testing functionality that is not on the main paths etc.