mold: A Massively Parallel Linker
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "mold: A Massively Parallel Linker".
Jane: Here's the gist of the paper. Linking is a critical step in the software build process that combines compiled object files into a single executable or shared library <ref:2608.23228#pg2> Despite decades of engineering effort, link times remain a significant bottleneck in the edit-compiledebug cycle, particularly for large C++ programs <ref:2608.23228#pg2>.
Tom: mold, a Unix/Linux linker that applies data parallelism systematically across the entire linking pipeline, links multi-gigabyte debug binaries in at most a few seconds, and often in under a second <ref:2608.23228#pg2>.
Jane: Architectural Constraints of Existing Linkers Existing linkers are constrained by order-sensitive semantics and lack formal specifications which makes it hard to change conventions <ref:2608.23228#pg2> Traditional Unix linking is defined in terms of a single left-to-right pass over the command line, and an extracted member may itself introduce new undefined references, so member extraction follows use-def chains across archives that a sequential scan naturally resolves <ref:2608.23228#pg2>.
Tom: Furthermore, pervasive parallelism is hard to retrofit because parallelizing certain passes changes the order in which global decisions are made, and making these changes amounts to rewriting much of the linker all at once <ref:2608.23228#pg2>.
Paper summary: Tom: So we're looking at this paper called "mold: A Massively Parallel Linker," and it tackles something that really slows down building big C++ programs, which is linking. It claims this tool uses data parallelism across the whole process to make multi-gigabyte debug binaries link in a few seconds, sometimes under a second >
Jane: That sounds incredible for developers who have huge projects because those build times used to be a massive bottleneck in the edit compile debug cycle >
Lu: The core idea is that existing linkers are stuck because they handle things like symbol resolution and archive processing in an order-sensitive way, which just limits how much they can use modern CPU cores >
Meng: So you're saying the old way of doing things forces everything into a single thread because the decisions have to be made one after another across the whole linking pipeline >
Lalam: Exactly. Existing linkers are constrained by those order-sensitive semantics, and if you try to add parallelism, it changes how global decisions are made, which means rewriting a huge chunk of the linker >
Tom: The authors show how mold decouples these things so they can apply data parallelism systematically across the entire linking pipeline >
Jane: They break down what existing linkers like GNU ld and lld are doing in terms of parallelization, showing where they're stuck with sequential steps >
Lu: The paper points out specific passes, like input file parsing and symbol resolution, that can be parallelized because they don't depend on the order of everything else yet >
Meng: What I want to know is how this affects deployment; if we move to a system that uses mold instead of lld or GNU ld, does it translate into a real cost reduction at scale >
Tom: The speedup comes from the cumulative effect of parallelizing all passes, meaning no single optimization is doing all the heavy lifting for the performance gain >
Jane: That cumulative effect is what’s interesting because it suggests you can improve performance by attacking every part of the process simultaneously rather than picking one hot spot >
Paper summary: Lalam: The ablation study they run shows that no single optimization dominates; instead, you get speedup from parallelizing all passes together >
Tom: And on large real-world programs, they're seeing results like up to one hundred twelve times faster than the traditional GNU ld linker > <ref:2608.23228#pg1,faster than the traditional GNU ld>
Jane: That comparison against GNU ld is pretty huge because that tool has been around forever and is single-threaded >
Lu: The paper also mentions system-level optimizations, like using huge pages for the output file and block preallocation, which are easy for any linker to adopt >
Meng: Those system tweaks are nice, but how much of the speedup they claim is actually due to those low-level OS tricks versus the core data parallelism in mold >
Tom: The scalability analysis suggests that mold speeds up steadily as you increase the thread count, which confirms it’s about parallel scalability rather than just clever system tweaks >
Jane: So if a developer is building something massive, they might see a significant time saving just by switching to this design concept >
Lu: The paper also discusses how they model section garbage collection using a mark-sweep traversal of a directed graph where sections are vertices and relocations are edges >
Meng: That sounds complex to manage in production; what’s the practical complexity of implementing that kind of graph traversal within a real build system >
Tom: It's modeled as a mark-sweep, which is a standard way to handle those kinds of dependencies when you have parallel work happening across all input files >
Jane: So we see these complex ideas being systematically applied across the entire linking process, from parsing right down to output generation >
Lalam: The paper also notes that string merging is deduplicated by inserting strings into a concurrent hash map in parallel across all input files >
Meng: A concurrent hash map sounds tricky to get right under heavy load; does that introduce new kinds of synchronization bugs or complexity when deploying this at scale >
Paper summary: Tom: It's designed for concurrency, and the goal is to keep those operations running in parallel even when dealing with massive inputs like multi-gigabyte binaries >
Jane: What this really means for a user is that they get a much faster feedback loop when they are iterating on large software projects >
Lu: The authors also talk about how symbols are named entities, and relocations are metadata instructing the linker to patch specific locations in section data to fill in addresses of symbols whose final locations aren't known at compile time >
Meng: So if you're using a shared library, the fact that position-independent code has to be managed differently because of potential address collisions is a real deployment headache >
Tom: That’s why the paper focuses on how mold handles those archive bundles and position-independent code structures better than before >
Jane: It seems like they are really addressing those deep architectural constraints of existing linkers, showing how a clean slate design can overcome that inherent sequential nature >
Lalam: The whole point is that by designing around pervasive parallelism, you get substantial end-to-end speedups because the serial or incompletely parallel work was spread throughout the pipeline >
Tom: So to sum up this paper on "mold: A Massively Parallel Linker," it shows how every major linker pass can be parallelized and that doing so yields substantial end-to-end speedups >
Jane: It suggests that the performance gap between current state-of-the-art linkers and this new design isn't due to one single bottleneck, but because serial or incompletely parallel work appears throughout the entire pipeline >
Lu: The implication is that we need to rethink how we structure these tools from the ground up if we want to keep up with the demands of large C++ programs >
Meng: For someone shipping models, it means less time waiting for builds and more time actually debugging or iterating on features, which is a tangible win >
Tom: The real story here is that when you parallelize everything systematically, the performance gain isn't from one clever trick but from the total effect across all those passes >
Conclusion: Tom: So, this paper is about mold, which is a linker that uses data parallelism to make linking multi-gigabyte debug binaries incredibly fast—sometimes under a second when you're comparing it to older tools like GNU ld or lld.
Jane: It’s interesting because most people think linking is just a slow sequence of steps, but this paper shows how you can apply parallelism across almost every single step of that process systematically.
Lu: The authors are showing how existing linkers get stuck because they have to make decisions in a strict left-to-right order, and mold redesigns the whole thing to run things at the same time where possible.
Meng: From my side, I'm interested in the scalability aspect; if this design holds up across different machine architectures, it could actually matter for how we deploy large AI models that need complex linking processes.
Lalam: I’m seeing a lot of work on string merging and symbol resolution being handled concurrently in parallel maps, which makes sense because those are massive bottlenecks when you have huge input files.
Tom: The main thing they're arguing is that the speedup isn't from one big trick, but from applying parallelism everywhere, which leads to these large end-to-end gains.
Jane: So, if you only listen to this part of the show, you should think about how we can take those old sequential linking tools and rethink them entirely by making every pass parallel.
Tom: Exactly. The implication is that the performance gap between current state-of-the-art linkers and this new design isn't due to one single bottleneck, but because serial or incompletely parallel work appears throughout the entire pipeline.
University of Tokyo
cs.OS
Submitted: 2026-08-24
Updated: 2026-08-24
Comments: 15 pages, 3 figures, 10 tables. Accepted to ASPLOS 2027
Code: https://github.com/ARM-software/abi-aa
Project page: https://gperftools.github.io/gperftools/tcmalloc.html
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 97/100
The gist: Linking is a critical step in the software build process that combines compiled object files into a single executable or shared library <ref:2608.23228#pg2> Despite decades of engineering effort…
Key concepts
- Data Parallelism
- This technique involves performing many tasks simultaneously on different pieces of data rather than one after another. Mold applies this by executing entire passes of the linker in parallel, using parallel-for loops within each pass to speed up operations like parsing and merging.
- Order-Sensitive Semantics
- Existing linkers are limited because they rely on a strict left-to-right sequence for operations. This sequential nature makes it difficult to introduce parallelism without rewriting the entire linker, as changing the order of steps can break how dependencies are resolved.
- Cumulative Parallelism
- The speedup in mold comes not from one single optimization but from parallelizing every major step in the linking process. Because no single part dominates the slowdown, speeding up all passes together results in a substantial, cumulative performance gain.
Terminology
Summary
Linking is a critical step in the software build process that combines compiled object files into a single executable or shared library <ref:2608. p. 023228#pg2> Despite decades of engineering effort, link times remain a significant bottleneck in the edit-compiledebug cycle, particularly for large C++ programs <ref:2608. p. 023228#pg2>. mold, a Unix/Linux linker that applies data parallelism systematically across the entire linking pipeline, links multi-gigabyte debug binaries in at most a few seconds, and often in under a second <ref:2608. p. 023228#pg2>.
Architectural Constraints of Existing Linkers
Existing linkers are constrained by order-sensitive semantics and lack formal specifications which makes it hard to change conventions <ref:2608.23228#pg2> Traditional Unix linking is defined in terms of a single left-to-right pass over the command line, and an extracted member may itself introduce new undefined references, so member extraction follows use-def chains across archives that a sequential scan naturally resolves <ref:2608. p. 123228#pg2>. Furthermore, pervasive parallelism is hard to retrofit because parallelizing certain passes changes the order in which global decisions are made, and making these changes amounts to rewriting much of the linker all at once <ref:2608. p. 123228#pg2>.
Data Parallelism in Major Passes
The design of mold is built around data parallelism, executing passes serially but parallelizing within each pass using parallel-for loops <ref:2608.23228#pg2>. Key passes are parallelized as follows:
-
Input File Parsing involves fully parsing all input files, including archive members, upfront and in parallel <ref:2608. p. 323228#pg2>.
-
Symbol Resolution uses an atomic compare-and-swap on the owner field of the shared symbol object to determine which definition prevails <ref:2608. p. 323228#pg2>.
4.3 String Merging deduplicates strings by inserting them into a concurrent hash map in parallel across all input files <ref:2608. p. 323228#pg2>.
4.5 Section Garbage Collection is modeled as a mark-sweep traversal of a directed graph where sections are vertices and relocations are edges <ref:2608. p. 423228#pg2>.
Performance Gains Through Cumulative Parallelism
The speedup comes from the cumulative effect of parallelizing all passes, as no single optimization dominates the overall speedup <ref:2608.23228#pg2>. An ablation study shows that no single optimization dominates; the speedup comes from the cumulative effect of parallelizing all passes <ref:2608. p. 023228#pg2>. For example, output copy + reloc. p. 1 apply adds +542% to the end-to-end link time when serialized <ref:2608. p. 323228#pg2>.
System-Level Optimizations and Scalability
Mold employs several system-level optimizations to reduce link time, including huge pages for the output file and block preallocation <ref:2608.23228#pg2> These optimizations are easy for any linker to adopt, which raises the question of how much of mold’s advantage it explains <ref:2608. p. 623228#pg2>. Scalability analysis shows that mold speeds up steadily with thread count, confirming that its advantage comes from parallel scalability <ref:2608. p. 923228#pg2>.
Comparison with State-of-the-Art Linkers
On large real-world workloads, mold links multi-gigabyte debug binaries in at most a few seconds, and often in under a second <ref:2608.23228#pg2>. It is 2.4–16.1x faster than the state-of-the-art lld linker, and up to 112x faster than the traditional GNU ld <ref:2608. p. 023228#pg2>. The performance gap is distributed across the pipeline, with parsing and symbol resolution making the largest absolute contribution to lld’s total time <ref:2608.23228#pg2>.
Conclusion
By building a new linker around pervasive parallelism, mold shows how every major linker pass can be parallelized and that doing so yields substantial end-to-end speedups <ref:2608.23228#pg2>. The gap between mold and lld is not due to one dominant bottleneck, but because serial or incompletely parallel work appears throughout the pipeline <ref:2608.23228#pg2>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Data Parallel Linking Architecture: Implement a linker that
applies data parallelism systematically across the entire linking pipeline
by structuringevery major pass as a data-parallel loop over homogeneous arrays of elements.
This allows for processingtens of millions of relocations, millions of symbols, hundreds of thousands of sections
concurrently within each phase. -
Decoupled Parsing and Resolution: Design a architecture that
decouples parsing from symbol resolution,
wheremold eagerly parses all input files—including every member of every archive—in parallel, and only then performs symbol resolution as a separate parallel pass using atomic compare-and-swap.
This overcomes the limitations of existing linkers by eliminatingentangled symbol resolution and archive processing.
-
Fine-Grained Deduplication: Incorporate specialized concurrent data structures for string merging that
avoid hash table resizing
by first estimating distinct strings using the HyperLogLog algorithm, ensuring thatidentical strings are mapped to the same entry
in parallel across all input files. -
Optimized Layout Computation: Replace sequential layout computation with a
two-level parallel scan
and use a mechanism where sections within an output section are split into groups of roughly 10,000 for parallel size and alignment computation. -
Parallel Garbage Collection: Model the
Section garbage collection
as amark-sweep traversal of a directed graph
using aparallel-for-each loop with a feeder pattern
to perform reachability traversal concurrently, significantly reducing the time spent in this pass compared to sequential execution. -
Efficient Range Extension Thunk Management: Utilize a
single linear scan during layout
that uses two cursors (leading and trailing) to create range extension thunks in parallel batches, ensuringmold eliminates the repetition by creating thunks in a single linear scan during layout rather than after it.