Weekly Paper Notes — one of the top picks from the 2026-08-29 CS paper digest. Area: Operating Systems / Systems.
Authors: Rui Ueyama (The University of Tokyo) arXiv: 2608.23228 · PDF · Code
TL;DR
mold is a Unix/Linux ELF linker built around one commitment: every major pass is a data-parallel loop over a homogeneous array, and nothing important is left sequential. The enabling move is decoupling input parsing from symbol resolution. Traditional linkers interleave the two because archive semantics are defined by a left-to-right scan of the command line — an archive member is pulled in only if it satisfies a reference outstanding at the moment the scan reaches it, and pulling it in creates new references. mold instead parses every input file eagerly and in parallel, including every member of every archive, and only then resolves symbols in a second parallel pass where each file installs itself as a symbol’s owner via atomic compare-and-swap. Archive member inclusion falls out afterwards as a liveness walk over owner pointers.
That decoupling unblocks the rest of the pipeline. Relocation scanning becomes a parallel-for with relaxed atomic bitwise-OR on per-symbol flags. Section garbage collection becomes a parallel mark with a feeder queue. Identical code folding becomes hash-based color refinement, where each iteration is embarrassingly parallel. Layout computation becomes a two-level parallel scan. On nine large open-source programs, mold is 2.4–16.1x faster than a version of LLVM lld that has mold’s system-level tricks retrofitted into it, and up to 112x faster than GNU ld. It links TensorFlow’s 9.9 GiB debug shared library in 3.23 seconds where lld takes 52.16.
What problem is the paper actually attacking?
Compilation has absorbed decades of research attention; linking has absorbed almost none. That asymmetry does not match where the time goes. A TensorFlow debug build produces 24 GiB of object files that the linker must fold into a single 9.9 GiB shared library, and developers pay that cost on every relink in the edit-compile-debug loop. Compilation of a single changed file is fast and incremental. The link is neither.
The two serious prior attempts both came out of Google. GNU gold was written from scratch in 2008 as an ELF-only replacement for the venerable BFD-based GNU ld, and it was substantially faster. gold also introduced threading — but as task parallelism: a work queue with dependency tokens, where independent tasks such as reading different input files could overlap. In practice the dependency chains serialize nearly everything, the measured speedup was negligible or slightly negative, and gold ships with multi-threading disabled by default. LLVM lld came next and took the pragmatic route, parallelizing the passes that could be isolated — some post-parse work, relocation scanning, output writing — and achieving 2–9x over gold. But symbol resolution, the pass that sits in the middle of everything, stayed single-threaded.
The paper’s Table 1 makes this concrete by tabulating which of nine passes each linker parallelizes. lld’s row is a mix; mold’s is uniform. And that uniformity is the whole argument, because Amdahl’s law is unforgiving here: parallelizing a subset leaves the serial remainder as a hard ceiling. The measured consequence is visible at 64 cores — lld plateaus at 16 threads with a 2.6x speedup while mold reaches 13.5x at 32.
Ueyama identifies three reasons the incremental path stalls, and they are more interesting than “nobody tried hard enough.” First, order-sensitive semantics: archive resolution is defined procedurally as a left-to-right scan, which is why users must wrap circularly dependent archives in -start-group/-end-group to request rescanning. Second, there is no formal specification — ELF standardizes the object file format, not how a linker should process inputs, so GNU ld is the de facto reference and any observable behavioral difference gets filed as a bug. A mature linker cannot afford that experiment; a new one whose early adopters knowingly accept differences can. Third, retrofitting pervasive parallelism changes the order global decisions are made, the representations carrying those decisions, and the interface to every downstream pass — which is most of a rewrite anyway.
The mechanism: decouple parsing from resolution, then parallel-for everything
The architectural decision is stated in one line: parse all input files upfront and in parallel, including every archive member, so that symbol resolution can be a single parallel pass over the result.
Parsing reads ELF headers, section headers, and symbol tables; relocation tables are located but not decoded until later. Symbol names are interned so that every file referencing a name shares one symbol object and symbol identity reduces to pointer equality. Interning is itself parallel and lock-free by construction — names are binned by hash into thread-local buffers during parsing, then each bin is deduplicated independently, with no shared concurrent structure.
Resolution is then a compare-and-swap tournament. Each file attempts to install itself as owner of the symbols it defines, and a seven-rank precedence table breaks ties: strong defined beats weak defined beats strong-in-archive-or-shared-library beats weak-in-archive-or-shared-library beats common beats common-in-archive beats undefined, with ties within a rank going to whichever input file appears earlier on the command line. Ueyama is candid that these rules are heuristic, because ELF leaves most of the interactions among regular objects, archive members, and shared libraries unspecified. He tried several orderings and kept the one that disagreed least with traditional linkers, then validated it by building the entire Gentoo repository: two packages out of more than 19,000 failed because of the difference.
Archive inclusion then becomes trivial. Because CAS has already pointed every defined symbol at its owning file, the linker marks non-archive inputs live and follows owner pointers transitively. This is not merely a reimplementation of the sequential scan — it is order-insensitive. The walk can reach a member that appears earlier on the command line than the file referencing it, and it follows circular dependencies with no rescanning. mold accepts -start-group and -end-group for compatibility and ignores them.
The same pattern repeats through the pipeline, and two cases are worth naming because they are not obvious.
String merging. A Firefox debug build contains roughly 21 million mergeable strings, nearly three quarters of them duplicates. mold inserts them into a concurrent hash map in parallel across all files. oneTBB’s general-purpose concurrent map was not fast enough, so the paper’s map avoids resizing entirely: estimate the distinct-string count with HyperLogLog first, allocate a table large enough up front, then let every file insert with atomic CAS.
Identical code folding. ICF merges read-only sections with identical contents and identical relocations, which makes section identity recursive — two sections match only if their relocation targets match. That is bisimulation equivalence over a labeled digraph. Rather than Hopcroft-style partition refinement, mold uses the hash-based color refinement that Schätzle et al. applied to MapReduce bisimulation reduction, equivalent to 1-dimensional Weisfeiler-Leman. Iteration 1 hashes contents, flags, and relocation types but not targets; iteration N hashes each section’s previous hash together with its targets’ previous hashes, so the hash summarizes all walks of length up to N. The sequence refines monotonically and converges when the distinct-hash count stops growing. Every iteration is embarrassingly parallel and needs no synchronization — the price is a few extra rounds of work traded for the absence of pairwise comparison.
Why it stays fast outside the algorithms
A meaningful share of the paper is system-level work that has nothing to do with parallelism, and Ueyama handles the resulting attribution problem well: he retrofits the transferable optimizations into lld and reports every comparison against that improved baseline. Huge pages, output file preallocation, the memory allocator, and parallel teardown of file mappings need no architectural restructuring, so lld gets all four. They compose roughly additively and make lld 1.1–2.1x faster than as shipped — the Firefox debug link drops from 7.04 s to 4.44 s. Every speedup quoted in the paper is measured against that lld, so the numbers isolate architecture rather than accumulated micro-optimizations.
The teardown trick deserves a mention on its own because it is pure latency accounting. When a process holding many memory-mapped files calls _exit, the kernel reclaims the address space in a single thread and only then notifies the parent — and the parent here is the build system, waiting, so that reclamation is perceived as link time. mold drops its mappings in parallel with madvise(MADV_DONTNEED) before exiting, which unlike munmap does not serialize on the exclusive address-space lock on Linux, and leaves contents in the page cache so the next link finds files warm. That alone shortens the Firefox debug link by 0.3 s when retrofitted into lld. mold then hides the remainder behind a two-process architecture: fork a child that does the actual linking, have it signal the waiting parent once the output file is written and closed, and let the parent — which holds almost nothing — exit immediately while the kernel reclaims the child in the background. Another 10% of user-perceived link time.
Metadata representation matters too. Input files, symbols, and sections are allocated in a dedicated arena and refer to each other by 32-bit offsets rather than 64-bit pointers, halving cross-reference storage and shrinking the records that many passes traverse. The whole linker is about 28,000 lines of C++20 shared across targets, plus 300–1300 lines per architecture, covering 14 of them through templates parameterized on an architecture type.
Results
The end-to-end table covers nine programs — Blender, Chromium, Clang, ClickHouse, Firefox, Godot, LibreOffice, PyTorch, TensorFlow — in both release and debug configurations, output binaries from 0.15 to 9.91 GiB, medians of five runs after a warmup that brings inputs into the page cache. Speedups grow with link size, because small links are dominated by startup costs both linkers pay and large links give lld’s serial passes more to do. Most programs land at 2.4–5.7x. TensorFlow’s debug build hits 16.1x, but the paper immediately decomposes that number rather than banking it: the link applies a version script with two dozen glob patterns, which lld matches against 2.5 million defined symbols one pattern at a time on one thread, consuming about 30 of its 52 seconds. Without that pathology the speedup would be roughly 7x. Chromium’s debug build at 7.0x is the cleaner illustration of scale — 40,945 input files, of which parsing alone costs lld about 7 of its 13.2 seconds.
Peak memory is essentially a wash between mold, lld, and gold, all of which do I/O through mmap and are dominated by the resident pages of mapped input and output files. mold’s eager parsing of every archive member adds little because it touches only symbol and section tables, not section contents. GNU ld uses explicit read/write and therefore reports a markedly lower peak RSS on large debug links — a genuine difference, though it comes bundled with being one to two orders of magnitude slower.
The ablation is the most persuasive table in the paper, and it argues against a story the reader might otherwise assume. Each row forces one pass single-threaded while everything else stays parallel. Output copy plus relocation application costs the most when serialized (+542%), followed by symbol resolution (+125%) and section garbage collection (+114%) — but input parsing still adds 52%, build-ID computation 62%, relocation scanning 43%, string merging 40%. No single optimization dominates. Leaving any one pass sequential visibly dents the result, which is precisely the claim that “parallelize all of them” was meant to support.
The ARM64 results temper the headline. On an M1 Ultra restricted to its 16 performance cores, mold’s advantage narrows to 1.7–12.6x. Fewer but faster cores favor a sequential linker: lld’s Firefox debug link improves to 3.26 s while mold’s regresses to 1.02 s from 0.89 s on the 64-core Threadripper. And there is an honest cost accounting for the parallelism itself — reaching 13.5x latency reduction at 32 threads consumes 73% more CPU time than the single-thread run, and going to 64 threads burns another 80% (21.1 s to 38.2 s of CPU) for wall-clock time that does not move at all. Hence mold’s default cap of 32 threads.
Two smaller findings are worth carrying away. At one thread the linkers are nearly tied — 12.2 s for mold against 11.4 s for lld — because mold’s parallel architecture has costs a sequential linker never pays (eager full parsing, extra refinement rounds) that are roughly offset by faster algorithms and compact representations. The advantage is entirely scalability, not constant factors. And GNU ld could not link 7 of the 18 workload configurations at all, for reasons ranging from unimplemented options to missing ELF features, which suggests lld rather than GNU ld is now the practical compatibility baseline for large modern C++.
Why this matters
The obvious reading is that a build-pipeline bottleneck got 3–5x faster and developers relink dozens of times a day. That is real, and mold has already been adopted widely enough that the Gentoo validation was possible at all.
The more transferable reading is about how legacy interfaces ossify. mold’s central speedup is not an algorithm — it is the decision to stop honoring a semantics defined by a sequential scan. The archive rules, -start-group, and the “which definition wins” corner cases exist because the first Unix linker processed the command line left to right, and every linker since has had to reproduce that ordering to avoid being called buggy. mold’s liveness walk is order-insensitive and arguably better behaved (circular archives just work), but shipping it required accepting that two of 19,000 Gentoo packages would break. An established linker cannot make that trade; a new one can. The paper is explicit that this asymmetry is why drastic improvements come from new linkers rather than existing ones, and the observation generalizes well beyond linking.
The engineering-methods point is worth stating too. Retrofitting mold’s system-level tricks into lld before measuring, so the reported gaps reflect architecture rather than accumulated polish, is more rigor than benchmark sections in systems papers usually carry — and it makes the ablation’s “no single optimization dominates” conclusion trustworthy rather than merely asserted.
Read alongside
- Ian Lance Taylor, “A New ELF Linker” (GCC Summit 2008) — the gold design, including the task-parallel work queue that mold’s serial-pass structure was chosen against.
- Kell, Mulligan, and Sewell, “The Missing Link: Explaining ELF Static Linking, Semantically” (OOPSLA 2016) — the formal semantics for ELF linking that Ueyama cites as covering only small static C programs, illustrating how little specification exists.
- Schätzle et al. on MapReduce bisimulation reduction — the hash-refinement algorithm mold reuses for identical code folding.
- Flajolet et al., “HyperLogLog” (2007) — the cardinality estimator that lets mold size its string-merging hash table correctly on the first try.
- Blelloch, “Prefix Sums and Their Applications” (1990) — the two-level parallel scan behind mold’s layout computation.
Links
📄 arXiv abstract · 📄 PDF · 💾 mold on GitHub
Part of the Weekly CS Paper Digest series. Summary written from a close read of the preprint; figures cropped from the arXiv PDF and reproduced here under fair use for educational commentary.