commit e16197de325ce5acfa2ba59d63b6c3e03f2375ea
parent 7f080a6f5976c89447a7c7b11e77ea44b71dde1b
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 22:30:13 -0700
perf(link): fix obj-count O(n^2) in the Mach-O emitter (shift_sections, patch_ptr)
The Mach-O finalizer had two section-count quadratics that made the obj-count
link axis superlinear (each output section is its own MSec):
- shift_sections re-based each section by rescanning the ENTIRE reloc vector AND
the ENTIRE symbol vector per section -> O(nsecs * (nrelocs + nsyms)). Replace
with a per-section delta table + three single passes (O(nsecs + nrelocs +
nsyms)); arithmetically identical (delta 0 == the former no-shift early-out).
Mirrors the ELF emitter, generalized to per-section deltas (Mach-O segments
get different bases).
- patch_ptr linear-scanned all MSecs per reloc to map link_sec_id -> MSec*
(O(nrelocs * nsecs)). Build that index once after plan_layout (the code
comment already asked for it) and look up in O(1).
obj-count link now scales linearly: golden 2048/8192/16384 objs = 55/341/1045ms
(2x input -> 3.07x time), new = 44/178/379ms (2x -> 2.13x). 16384 objs
1045->379ms (2.76x), gap widens with N. Linked executables byte-identical at
1024 and 4096 objects. Verified: test-macho/link/smoke-x64 green + native
aa64-macos link&run.
Diffstat:
| M | src/obj/macho/link.c | | | 118 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------ |
1 file changed, 82 insertions(+), 36 deletions(-)
diff --git a/src/obj/macho/link.c b/src/obj/macho/link.c
@@ -238,6 +238,11 @@ typedef struct MCtx {
/* sections + segments */
MSec* secs;
u32 nsecs;
+ /* link_sec_id (1-based) -> backing MSec, NULL where none. Built once after
+ * plan_layout so shift_sections / patch_ptr map a section id to its MSec in
+ * O(1) instead of a linear scan of secs per reloc (was O(nrelocs*nsecs)). */
+ MSec** by_link_sec;
+ u32 by_link_sec_cap; /* img->nsections + 1 */
OutSec* outs;
u32 nouts;
MSeg segs[MSEG_COUNT]; /* PAGEZERO, TEXT, DATA_CONST, DATA, DWARF, LINKEDIT */
@@ -1184,43 +1189,76 @@ static void plan_layout(MCtx* x) {
* link_layout coordinates. Map each LinkSection -> its MSec and copy
* the final vaddr/file_offset so reloc-apply walks correctly. */
+/* link_sec_id -> backing MSec index, built once. */
+static void build_section_index(MCtx* x) {
+ u32 n = x->img->nsections;
+ x->by_link_sec_cap = n + 1u;
+ x->by_link_sec =
+ (MSec**)x->h->alloc(x->h, sizeof(MSec*) * x->by_link_sec_cap,
+ _Alignof(MSec*));
+ if (!x->by_link_sec)
+ compiler_panic(x->c, SRCLOC_NONE, "link_macho: oom on section index");
+ for (u32 i = 0; i < x->by_link_sec_cap; ++i) x->by_link_sec[i] = NULL;
+ for (u32 i = 0; i < x->nsecs; ++i) {
+ MSec* m = &x->secs[i];
+ if (m->link_sec_id && m->link_sec_id < x->by_link_sec_cap)
+ x->by_link_sec[m->link_sec_id] = m;
+ }
+}
+
+/* Re-base every section to its final Mach-O vaddr/file_offset, then shift the
+ * relocs and defined symbols anchored to each section by its per-section delta.
+ * A per-section delta table + three single passes (O(nsecs + nrelocs + nsyms))
+ * replaces the former per-section rescan of the whole reloc + sym vectors
+ * (O(nsecs * (nrelocs + nsyms)) — the dominant obj-count superlinearity). The
+ * ELF emitter (src/obj/elf/link.c) is the reference; this generalizes it to
+ * per-section deltas because Mach-O segments get different bases. */
static void shift_sections(MCtx* x) {
LinkImage* img = x->img;
- /* Build a quick lookup: link_sec_id -> MSec*. */
+ u32 n = img->nsections;
+ i64* dv = (i64*)x->h->alloc(x->h, sizeof(i64) * (n + 1u), _Alignof(i64));
+ i64* df = (i64*)x->h->alloc(x->h, sizeof(i64) * (n + 1u), _Alignof(i64));
+ if (!dv || !df)
+ compiler_panic(x->c, SRCLOC_NONE, "link_macho: oom on shift deltas");
+ for (u32 i = 0; i <= n; ++i) {
+ dv[i] = 0;
+ df[i] = 0;
+ }
+ /* Per-section deltas; re-base each LinkSection. Sections keyed by id (the
+ * same id relocs/syms carry), matching the former ls->id match. */
for (u32 i = 0; i < x->nsecs; ++i) {
MSec* m = &x->secs[i];
+ LinkSection* ls;
+ u32 id;
if (!m->link_sec_id) continue;
- /* Walk link_section_id slot. */
- LinkSection* ls = &img->sections[m->link_sec_id - 1u];
- /* shift relocs whose write_vaddr/file_offset live within this
- * section's original [old_vaddr, old_vaddr+size). */
- u64 old_v = ls->vaddr;
- u64 old_f = ls->file_offset;
- u64 new_v = m->vaddr;
- u64 new_f = m->file_offset;
- if (old_v == new_v && old_f == new_f) continue;
- /* Update the LinkSection itself. */
- ls->vaddr = new_v;
- ls->file_offset = new_f;
- /* Update relocs that target this section. */
- for (u32 ri = 0; ri < LinkRelocs_count(&img->relocs); ++ri) {
- LinkRelocApply* r = LinkRelocs_at(&img->relocs, ri);
- if (r->link_section_id != ls->id) continue;
- r->write_vaddr = new_v + (r->write_vaddr - old_v);
- r->write_file_offset = new_f + (r->write_file_offset - old_f);
- }
- /* Update LinkSyms that belong to this LinkSection. Match by
- * section_id rather than vaddr range — multiple input sections
- * may share the same pre-shift vaddr (each bucket in
- * link_layout starts at offset 0). */
- for (u32 si = 0; si < LinkSyms_count(&img->syms); ++si) {
- LinkSymbol* s = LinkSyms_at(&img->syms, si);
- if (!s->defined) continue;
- if (s->kind == SK_ABS) continue;
- if (s->section_id != ls->id) continue;
- s->vaddr = new_v + (s->vaddr - old_v);
- }
+ ls = &img->sections[m->link_sec_id - 1u];
+ id = ls->id;
+ if (id == 0 || id > n) continue;
+ dv[id] = (i64)m->vaddr - (i64)ls->vaddr;
+ df[id] = (i64)m->file_offset - (i64)ls->file_offset;
+ ls->vaddr = m->vaddr;
+ ls->file_offset = m->file_offset;
}
+ /* Shift relocs by their section's delta (0 == no shift, was the early-out). */
+ for (u32 ri = 0; ri < LinkRelocs_count(&img->relocs); ++ri) {
+ LinkRelocApply* r = LinkRelocs_at(&img->relocs, ri);
+ u32 id = r->link_section_id;
+ if (id == LINK_SEC_NONE || id > n) continue;
+ r->write_vaddr = (u64)((i64)r->write_vaddr + dv[id]);
+ r->write_file_offset = (u64)((i64)r->write_file_offset + df[id]);
+ }
+ /* Shift defined, non-absolute symbols. Match by section_id (multiple input
+ * sections may share a pre-shift vaddr; the bucket each starts at offset 0). */
+ for (u32 si = 0; si < LinkSyms_count(&img->syms); ++si) {
+ LinkSymbol* s = LinkSyms_at(&img->syms, si);
+ u32 id;
+ if (!s->defined || s->kind == SK_ABS) continue;
+ id = s->section_id;
+ if (id == LINK_SEC_NONE || id > n) continue;
+ s->vaddr = (u64)((i64)s->vaddr + dv[id]);
+ }
+ x->h->free(x->h, dv, sizeof(i64) * (n + 1u));
+ x->h->free(x->h, df, sizeof(i64) * (n + 1u));
}
/* ---- pass: apply relocations + collect chained-fixup sites ----
@@ -1303,12 +1341,17 @@ static u8* patch_ptr(MCtx* x, LinkImage* img, const LinkRelocApply* r,
* vaddr is the Mach-O vaddr; the corresponding MSec backs it. */
if (r->link_section_id == LINK_SEC_NONE) return NULL;
LinkSection* ls = &img->sections[r->link_section_id - 1u];
- /* Find the MSec by link_sec_id. */
+ /* MSec by link_sec_id via the prebuilt index (O(1)); fall back to a scan if
+ * the index was not built (it always is, post plan_layout). */
MSec* m = NULL;
- for (u32 i = 0; i < x->nsecs; ++i) {
- if (x->secs[i].link_sec_id == ls->id) {
- m = &x->secs[i];
- break;
+ if (x->by_link_sec && ls->id < x->by_link_sec_cap) {
+ m = x->by_link_sec[ls->id];
+ } else {
+ for (u32 i = 0; i < x->nsecs; ++i) {
+ if (x->secs[i].link_sec_id == ls->id) {
+ m = &x->secs[i];
+ break;
+ }
}
}
if (!m) return NULL;
@@ -2337,6 +2380,7 @@ void link_emit_macho(LinkImage* img, Writer* w) {
collect_imports(&x);
collect_tlv(&x);
plan_layout(&x);
+ build_section_index(&x);
shift_sections(&x);
/* entry offset within __TEXT segment. */
@@ -2633,6 +2677,8 @@ void link_emit_macho(LinkImage* img, Writer* w) {
if (x.sym_to_imp)
x.h->free(x.h, x.sym_to_imp, sizeof(u32) * x.sym_to_imp_size);
if (x.secs) x.h->free(x.h, x.secs, 0);
+ if (x.by_link_sec)
+ x.h->free(x.h, x.by_link_sec, sizeof(MSec*) * x.by_link_sec_cap);
if (x.stubs_bytes) x.h->free(x.h, x.stubs_bytes, x.stubs_size);
if (x.got_bytes) x.h->free(x.h, x.got_bytes, x.got_size);
if (x.tlv_ptrs_bytes) x.h->free(x.h, x.tlv_ptrs_bytes, x.tlv_ptrs_size);
