Accelerating the kernel's build process

In the cover letter to his 23-part patch series, Stoakes described his tool use for this work:

An LLM was used to first determine where the bottlenecks were then to figure out how to improve them.

It generated a lot of code, much of it hideous.

I extensively audited and rewrote a lot of it, and heavily edited commit messages, the cover letter and comments.

The results of this work were summarized as "allmodconfig builds up to 36% faster, incremental builds up to ~70% faster, and noop builds up to ~90% faster".

How to accelerate kernel builds

Getting to that point required a lot of changes to the build process. Consider, for example, the kallsyms program, which runs during the build to create a table of all of the symbols (function and variable names) in the kernel. There are a lot of symbols, so this table can be large. Since the table can reside in memory, there is a strong incentive to make it smaller; kallsyms thus implements a special compression algorithm, described this way in the source:

Table compression uses all the unused char codes on the symbols and maps these to the most used substrings (tokens). For instance, it might map char code 0xF7 to represent "write_" and then in every symbol where "write_" appears it can be replaced by 0xF7, saving 5 bytes.

As Stoakes (or his LLM) observed, though, kallsyms performs this compression in a highly inefficient way, trying to perform each token replacement in every one of over 150,000 symbols, even though any given token will only appear in a small subset of them. This patch from the series tracks which tokens appear in which symbols, so that substitutions are only attempted in places where they will succeed. This change alone speeds kernel builds by 2-6%.

Even then, though, kallsyms outputs its table as a 37MB assembly-language file that must then be passed to the assembler to be turned into binary data. This patch causes kallsyms to output the binary data in a form that the assembler can pull in directly, reducing build times by up to 11% in the best case. Linus Torvalds applauded this change, but suggested that it could go further: kallsyms could simply output an ELF object, taking the assembler out of the picture entirely. Nobody, he suggested, would normally want to write the code needed to make kallsyms behave that way but, since an LLM is involved, "the obvious step would be to just ask the little helper bot to switch the whole kallsyms to using libelf-devel and writing an object file directly".

The build process uses the nm tool at various stages to query the contents of object files. The output from nm is sorted by default, but the build process rarely needs sorted data. This patch disables the sorting when it is not needed, improving build times by another couple of percentage points. In another patch, the various intermediate linking stages are changed to not emit relocation data, which is unneeded at that point, again improving build times by 2% or so.

Sometimes, though, the use of nm can be avoided altogether. The build process currently runs that tool on kernel objects, feeding the output to the mksysmap sed script to create data suitable for feeding to kallsyms. This patch replaces that script with new kallsyms code that reads ELF files directly and extracts the needed data, bypassing nm entirely. In the best case, this change improves build times by 12%, though the improvement seen in most cases is significantly more modest. Another modest improvement is had by not allocating the .modinfo section in the kernel image. This patch, which caches information about whether each object file is part of a module, speeds build performance, especially in larger directories.

The kernel contains a lot of header files, with the result that object files can have a huge number of dependencies. The make utility, it seems, spends a lot of time checking these dependencies in a single-threaded mode, slowing down the build, especially in cases where little has changed. This patch adds a new utility, called depcheck, that performs dependency checking in a more efficient way, taking care to only stat() each file once. This change may not last, though: Torvalds suggested that much of the trickery used to make dependency checks work properly may no longer be needed: "That whole thing is from a quarter century ago, and nobody has dared look at that code since". So the better solution might be to just remove it entirely.

Then, there is this patch, which aims to reduce the number of times that the build process invokes the compiler to probe whether a specific feature is supported. The compiler and its supported options do not change over the course of a kernel build, so it makes sense to remember which options are supported after querying them once. A new set of configuration options is added as a way of remembering and testing that information.

The modpost tool postprocesses symbol versions in loadable modules; that work involves calculating a lot of MD4 hashes. In current kernels, the data to be hashed is accumulated one byte at a time; this patch does the hashing on a per-file basis, yielding a build-time improvement of up to 6%. However, this functionality is being removed from modpost, so this change will be dropped from the series. This patch adds more caching to modpost, reducing build times by up to 12% in some cases. Finally, modpost generates a C file containing a descriptor for each module it handles; that file must then be compiled into an object file. As described in this patch, the resulting overhead is not small:

These files are compiled like any other kernel C file with all of the -include preamble, as well as including linux/module.h, header dependencies generated by fixdep of a few hundred headers, an objtool run and if LTO is being performed, a link is performed to generate native code.

On an x86-64 allmodconfig build 11,189 *.mod.c files are built, each taking ~0.24s of CPU time to compile, and module finalisation as a whole 6,300 CPU seconds, or 64 seconds of wall time when run over 128 threads.

Changing modpost to output assembly code, thus avoiding the compiler step, removes this overhead, speeding an allmodconfig build by 11% (and no-op builds by much more). Nobody will complain about an improvement like this but, again, Torvalds suggested that an even better approach would be to generate the object file directly and remove the assembler from the process as well. Beyond any speedups, he said, that change would remove the .mod.c files from the build entirely.

Other changes include this patch, which causes the finalization step at the end of each module build (which runs in milliseconds for any given module) to be batched, overcoming the inability of make to dispatch thousands of little tasks efficiently. Another patch parallelizes the hashing of files in modpost. There is a rather more complex patch that adds parallelization to the objtool utility, with large effects on some builds.

Then, there is the matter of Rust. Currently, the kernel's Rust crates are compiled serially, one at a time. That slows the kernel build considerably now, and will only slow things further as the amount of Rust code grows. This patch uses the -Zthreads option to rustc to build the crates in parallel; that option was added in Rust 1.84, which is (slightly) older than the minimum version (1.85) required by the kernel. The patch will also attempt to use the future --jobs option if it is available. Björn Baron warned, though, that parallel builds in rustc have not fully stabilized, so it is not clear that this mode should be used by default. This other patch, which allows Rust code to be built in parallel with the building of C code, should be rather safer.

The final patch in the series causes the build system to use pigz to compress the kernel if it is available. pigz is able to perform compression in parallel, significantly reducing the time required to complete this step.

In summary

See the plot (above) for another look at how these patches affect kernel-build times. All told, they add up to a significant reduction in the time required to build a kernel. It seems unlikely that developers will complain much about that. As long as they do not introduce build problems (and only the parallel Rust change appears to have any risk of doing that), there should not be much opposition to their merging.

Naturally, it was necessary to try it out. On my system, which is better suited to article writing than fast builds, a full kernel build with an empty ccache reliably takes about 960 seconds. With this patch series applied, that time drops to about 860 seconds (both are wall-clock time, the CPU-time numbers are quite a bit higher). That is roughly a 10% decrease in build time. The clean-ccache case was chosen because it is easily reproducible, but it is also dominated by actual compile time and is the scenario likely to show the least improvement. With a fully populated ccache, the patches made a difference of a few seconds in a roughly 90-second build.

At any given time, there must be an impressive number of machines performing kernel builds all over the planet. Developers will be running some of those, but there are probably far more in the many continuous-integration systems that are running. So build-time improvements may save more than developer time; they will reduce the carbon impact of the development process overall. This work, it seems, should have been undertaken long ago. One wonders what other savings may be waiting for a suitably motivated developer to take a close look.

Note: you can avoid this step in the future by logging into your LWN account.