Proposal: faster and smaller MC/DC

This post describes a proposal and is a call for clients, if you will. I have an idea for an optimization in the GCC MC/DC instrumentation (-fcondition-coverage) that I estimate would reduce the overhead in both compile time, object size, and run time, roughly 2-3 times, and I am looking for clients to fund this work.

GCC has supported MC/DC since version 14 (released May 2024) and works quite well. I recently fixed a performance bug that made a massive difference for (very) large expressions, which went unnoticed for a while because such large expressions are quite uncommon and the performance has been adequate. I do believe we can improve both the compile time and the quality of instrumentation further.

I did some more experiments and compared the compile times for a couple of real-world programs. The baseline is built with no flags, coverage with -ftest-coverage -fprofile-arcs, and MC/DC with -ftest-coverage -fcondition-coverage on GCC 14.2. This table shows that compile times are very sensitive to the program structure and that MC/DC slows down compiles significantly, sometimes up to 3 times. All compile times are in seconds.

Object sizes too are greatly affected by instrumentation, albeit slightly less consistent, but does support that the generated instrumentation (and not the analysis) is the main driver for compile times. The object sizes are in megabytes (MB).

Faster compiles are important and goes beyond simple ergonomics. Increased latency in the edit-compile-test cycle is very detrimental to both efficiency and effectiveness; reduced latency empowers engineers to solve harder problems and, in my experience, in a better way. The faster compile does not just save time (which is already precious and expensive), but reduces context switches and makes for a stronger feedback loop. The importance of fast and solid feedback loops is well understood, and has been covered by countless books, articles, blog posts, and talks. I would argue it is vital to optimize the edit-compile-test cycle when working with MC/DC since reaching (and understanding) coverage often is the most expensive and time consuming phase of system development.

There’s efficiency to be gained, too, just by reducing the time wasted waiting for the compiler to finish. When developing the test suite for MC/DC the program will be recompiled many times which will effectively be idle, so just a few seconds here and there add up fast.

The improvements in size- and runtime overhead means even larger programs can fit on small embedded system, which is particularly relevant the context of MC/DC as safety critical systems often run on small computers, ECUs, microcontrollers. This goes beyond just edit-compile-test friction; if instrumented programs cannot run on the device it is not just a mere inconvenience, it is a barrier to progress.

The compile time and size tests show that the overhead of coverage instrumentation greatly depends on the structure of the program. Note that compilation is a complicated process and the 2-3x reduction in overhead is an estimate.

To make this improvement in GCC happen, send an email to j@patch.no and I will send you a formal proposal and discuss the terms. After we sign the contract I will implement these optimizations and take care of upstreaming and integrating the changes into GCC.