Further Parallelization Optimizations

Originally I parallelized tests using a round-robin approach: when each worker process finishes running a test, it asks the supervisor which test to run next. When you get down to the final tests, this minimizes the amount of time cores are sitting idle waiting for the last one to finish.

However, in practice, the round-robin approach was much slower than having each of (say) 4 workers pick 1/4 of the tests and run those to completion. This is presumably faster because it eliminates the Inter-Process Communication overhead the round-robin approach requires. (If Node had threads that overhead would probably be negligible, but it doesn't, so here we are.)

There are still several things we could try, which might potentially speed this up even more. I'm not saying we should do all of these things, just writing them down as potential areas to explore.

Parallelize fuzz test runs

By design, it's possible to have a fuzz test with n=100 run all 100 iterations in parallel.

We aren't currently doing this, but we could. I'd expect this to have higher memory overhead, but less CPU idling at the end of the test run, and thus an overall lower duration for the same test suite.

Parallelize Shrinking

When a test fails, shrinking takes longer than just about anything else. I haven't investigated to what extent shrinking could be parallelized, but if it can be, there are probably substantial wins there.

Just-in-time round-robin

Start off by having all worker processes plow ahead without communicating with the supervisor, just like how they do today.

Once the first worker finishes, have it report to the supervisor "I'm finished, and now I'm idle." At this point we switch into round-robin model. The supervisor then tells all the other workers "finish up what you're doing, then report where you left off, and that you're idle." At that point the supervisor has all the information necessary to round-robin the remaining tests.

It's possible that this would avoid cases that are possible today, where one worker is holding up the show. Worth noting that I started working on this, but it added significant complexity so I backed off and decided to table it.

Run slowest tests first

Do what Jest does, which is to sort tests by duration - I guess based on caching that from previous test runs, and/or possibly some heuristic - and run the slowest ones first.

For us, this is probably a matter of running fuzz tests first (especially in case they fail and require shrinking, although if we can parallelize shrinking and test-running in the first place, that might be less of a big deal), and someday Webdriver tests - which I would certainly expect to be the slowest.

It's also possible that users wouldn't want this, or perhaps would want to be able to turn it off. Certainly output can be printed in the original order regardless, but this could delay your getting info on what failed. (The thing is, usually if I care about order of test execution, I'm using something like only or skip anyway. So I suspect this may not matter.)

Start by reading the existing worker and supervisor scheduling implementation, then trace how fuzz-test runs and shrinking are executed. Compare the proposed fuzz parallelization, shrinking, just-in-time round-robin, and slowest-first ideas with measured test-suite duration and memory use. The issue has no named files or single acceptance criterion, so a completed direction would need a selected approach and benchmarked improvement.