https://github.com/int3 created https://github.com/llvm/llvm-project/pull/234857
Emit singleton suffixes directly and scan common prefixes in one pass, avoiding repeated byte-wise partitioning. Preserve radix traversal, node allocation order, and terminal encoding. This speeds up builds that emit large export tries. Wall time with [LinkerBench](https://github.com/int3/macho-linker-bench), #233399 → this PR, Release, assertions off. Median ± 95% CI over at least 20 interleaved runs per side. M4 Mac mini (10 cores, 16 GB): | Link | Exports | Default threads | 1 thread | | --- | ---: | ---: | ---: | | rust-analyzer (debug) | 248,607 | 650.3 ± 1.2 → 625.4 ± 1.9 ms (−3.8%) | 951.7 ± 0.9 → 870.3 ± 1.7 ms (−8.6%) | | SourceKit-LSP | 105,359 | 604.2 ± 2.3 → 605.4 ± 1.6 ms | 774.5 ± 1.3 → 767.5 ± 0.6 ms (−0.9%) | | Firefox for iOS | 82,489 | 552.6 ± 0.9 → 552.0 ± 1.6 ms | 651.8 ± 1.3 → 646.5 ± 1.3 ms (−0.8%) | | libLLVM | 55,996 | 365.3 ± 1.0 → 365.7 ± 1.0 ms | | rust-analyzer (release), Telegram and Firefox for macOS are unchanged (1.00×). Ryzen 7 7700 (Linux), default threads, all 15 LinkerBench workloads: rust-analyzer (debug) goes from 1.241 ± 0.011 to 1.158 ± 0.006 s (−6.7%); the other 14 workloads are within noise of 1.00×. Assisted by Opus 5.5 >From 603b2ae7280c71933444f70744840a2326a7b556 Mon Sep 17 00:00:00 2001 From: Jez Ng <[email protected]> Date: Mon, 19 Oct 2026 11:05:22 +0200 Subject: [PATCH 1/2] [lld-macho] Build the export trie by edges, not bytes (NFC) Emit singleton suffixes directly and scan common prefixes in one pass, avoiding repeated byte-wise partitioning. Preserve radix traversal, node allocation order, and terminal encoding. On a Ryzen 7 7700, a rust-analyzer debug link with 248,607 exports changes from 2079 to 1948 ms at one thread and 1269 to 1185 ms at eight threads (median wall times over four interleaved pairs). --- lld/MachO/ExportTrie.cpp | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/lld/MachO/ExportTrie.cpp b/lld/MachO/ExportTrie.cpp index 4a9e14c3d920d..55235219fb3b1 100644 --- a/lld/MachO/ExportTrie.cpp +++ b/lld/MachO/ExportTrie.cpp @@ -226,6 +226,19 @@ void TrieBuilder::sortAndBuild(MutableArrayRef<const Symbol *> vec, if (vec.empty()) return; + // A singleton needs just one edge for its remaining suffix. + if (vec.size() == 1) { + const Symbol *sym = vec.front(); + StringRef suffix = sym->getName().drop_front(lastPos); + if (!suffix.empty()) { + TrieNode *newNode = makeNode(); + node->edges.emplace_back(suffix, newNode); + node = newNode; + } + node->info = ExportInfo(*sym, imageBase); + return; + } + // Partition items so that items in [0, i) are less than the pivot, // [i, j) are the same as the pivot, and [j, vec.size()) are greater than // the pivot. @@ -264,6 +277,20 @@ void TrieBuilder::sortAndBuild(MutableArrayRef<const Symbol *> vec, // sortAndBuild(vec.slice(i, j - i), node, lastPos, pos + 1); vec = vec.slice(i, j - i); ++pos; + // Skip the rest of a common prefix without partitioning at every byte. + if (vec.size() > 1) { + StringRef firstName = vec.front()->getName(); + size_t commonEnd = firstName.size(); + for (const Symbol *sym : vec.drop_front()) { + StringRef name = sym->getName(); + commonEnd = std::min(commonEnd, name.size()); + size_t commonPos = pos; + while (commonPos < commonEnd && firstName[commonPos] == name[commonPos]) + ++commonPos; + commonEnd = commonPos; + } + pos = commonEnd; + } goto tailcall; } } >From 470f33ec44ca83a72cb3378bdeaaf56bbc2dc467 Mon Sep 17 00:00:00 2001 From: Jez Ng <[email protected]> Date: Mon, 19 Oct 2026 04:02:38 -0700 Subject: [PATCH 2/2] Improve comments in ExportTrie.cpp Refactor comments for clarity and optimization explanation. --- lld/MachO/ExportTrie.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/lld/MachO/ExportTrie.cpp b/lld/MachO/ExportTrie.cpp index 55235219fb3b1..2caf0f7ede6bd 100644 --- a/lld/MachO/ExportTrie.cpp +++ b/lld/MachO/ExportTrie.cpp @@ -226,7 +226,7 @@ void TrieBuilder::sortAndBuild(MutableArrayRef<const Symbol *> vec, if (vec.empty()) return; - // A singleton needs just one edge for its remaining suffix. + // Create singletons in one go instead of doing a tail call per character. if (vec.size() == 1) { const Symbol *sym = vec.front(); StringRef suffix = sym->getName().drop_front(lastPos); @@ -277,7 +277,8 @@ void TrieBuilder::sortAndBuild(MutableArrayRef<const Symbol *> vec, // sortAndBuild(vec.slice(i, j - i), node, lastPos, pos + 1); vec = vec.slice(i, j - i); ++pos; - // Skip the rest of a common prefix without partitioning at every byte. + // Skip the rest of a common prefix instead of doing a tail call per + // character. if (vec.size() > 1) { StringRef firstName = vec.front()->getName(); size_t commonEnd = firstName.size(); _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
