commit 9670b86965fba2c727db42255967f7c64b27e0f0
parent 442fdc5555d055f48a12b59956a60177ad9413a8
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 13 Jun 2026 00:51:10 -0700
perf(obj): index relocations by section (kill O(n_sec*n_reloc) emit scan)
The native object emitters (macho/elf/coff) each rescanned the entire flat
reloc table once per section to build per-section relocation tables —
O(n_sections * n_relocs), a latent superlinear axis that grows with
-ffunction-sections and per-literal .rodata fan-out (PERF-TCC-SLIM.md D6).
Add a lazily-built per-section reloc index on ObjBuilder: a counting sort of
the live relocs keyed by section_id that preserves ascending global order
within each section. obj_reloc_count becomes O(1) and a new obj_reloc_section
yields a section's live reloc indices directly, so each emitter iterates only
its own relocs. The index is invalidated on reloc add and on obj_sweep_dead.
The macho symdiff (ADD/SUB) pairing still peeks the global next (ri+1) exactly
as before and skips the SUB partner only when it is globally adjacent in the
bucket, preserving byte-identical output.
Gate: scripts/perf_identity_gate.sh byte-identical across all categories;
test-elf/macho/ar/link green under ASan/UBSan.
Diffstat:
5 files changed, 124 insertions(+), 24 deletions(-)
diff --git a/src/obj/coff/emit.c b/src/obj/coff/emit.c
@@ -343,7 +343,6 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
/* COFF stores NumberOfRelocations as u16; sections with > 65535
* relocs use the IMAGE_SCN_LNK_NRELOC_OVFL extension which we don't
* implement in v1. Panic if any single section exceeds the limit. */
- u32 total_relocs = obj_reloc_total(ob);
for (u32 ci = 0; ci < nsecs; ++ci) {
CSec* cs = &secs[ci];
u32 nr = obj_reloc_count(ob, cs->obj_sec);
@@ -569,15 +568,15 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
/* ---- pass 4: build per-section relocation tables --------------- */
for (u32 ci = 0; ci < nsecs; ++ci) {
CSec* cs = &secs[ci];
- u32 nr = cs->number_of_relocations;
+ u32 nr;
+ const u32* rix = obj_reloc_section(ob, cs->obj_sec, &nr);
if (!nr) continue;
u8* buf = (u8*)arena_alloc(c->scratch, (size_t)COFF_RELOC_SIZE * nr,
_Alignof(u32));
u32 j = 0;
- for (u32 ri = 0; ri < total_relocs; ++ri) {
- const Reloc* r = obj_reloc_at(ob, ri);
- if (r->removed) continue;
- if (r->section_id != cs->obj_sec) continue;
+ /* rix[] lists this section's live relocs in ascending global order. */
+ for (u32 k = 0; k < nr; ++k) {
+ const Reloc* r = obj_reloc_at(ob, rix[k]);
if (r->sym == OBJ_SYM_NONE) {
compiler_panic(c, SRCLOC_NONE,
"emit_coff: reloc without symbol not supported "
diff --git a/src/obj/elf/emit.c b/src/obj/elf/emit.c
@@ -454,8 +454,6 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
/* ---- pass 3: build .rela.<name> contents ------------------------ */
/* Allocate one .rela section per obj section that has any relocs. */
- u32 total_relocs = obj_reloc_total(ob);
-
typedef struct RelaPlan {
u32 obj_section; /* obj section the rela applies to */
u8* bytes; /* arena-allocated rela bytes */
@@ -468,15 +466,15 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
for (u32 si = 1; si < nobjsec; ++si) {
const Section* host = obj_section_get(ob, si);
if (!host || host->removed) continue;
- u32 nr = obj_reloc_count(ob, si);
+ u32 nr;
+ const u32* rix = obj_reloc_section(ob, si, &nr);
if (!nr) continue;
u8* buf =
(u8*)arena_alloc(c->scratch, (size_t)rela_size * nr, _Alignof(u64));
u32 j = 0;
- for (u32 i = 0; i < total_relocs; ++i) {
- const Reloc* r = obj_reloc_at(ob, i);
- if (r->removed) continue;
- if (r->section_id != si) continue;
+ /* rix[] lists section si's live relocs in ascending global order. */
+ for (u32 k = 0; k < nr; ++k) {
+ const Reloc* r = obj_reloc_at(ob, rix[k]);
u32 etype = reloc_to(r->kind);
if (etype == ELF_R_AARCH64_NONE /* == ELF_R_X86_64_NONE == 0 */ &&
r->kind != R_NONE) {
diff --git a/src/obj/macho/emit.c b/src/obj/macho/emit.c
@@ -537,17 +537,20 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
u32 total_relocs = obj_reloc_total(ob);
for (u32 i = 0; i < nsecs; ++i) {
MSec* m = &secs[i];
- u32 nr = obj_reloc_count(ob, m->obj_sec);
+ u32 nr;
+ const u32* rix = obj_reloc_section(ob, m->obj_sec, &nr);
if (!nr) continue;
/* Worst case: each reloc may be preceded by an ARM64_RELOC_ADDEND
* pair entry. We size the buffer for that upper bound. */
u8* buf = (u8*)arena_alloc(c->scratch, (size_t)MACHO_RELOC_SIZE * nr * 2,
_Alignof(u32));
u32 j = 0;
- for (u32 ri = 0; ri < total_relocs; ++ri) {
+ /* rix[] lists this section's live relocs in ascending global order, so
+ * each is in-section and non-removed by construction. The symdiff
+ * pairing below still peeks the *global* next (ri+1) exactly as before. */
+ for (u32 k = 0; k < nr; ++k) {
+ u32 ri = rix[k];
const Reloc* r = obj_reloc_at(ob, ri);
- if (r->removed) continue;
- if (r->section_id != m->obj_sec) continue;
if ((r->kind == R_ADD8 || r->kind == R_ADD16 || r->kind == R_ADD32 ||
r->kind == R_ADD64) &&
ri + 1u < total_relocs) {
@@ -597,7 +600,9 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
((unsigned_type & 0xfu) << 28));
++j;
}
- ++ri;
+ /* Skip the SUB partner (global ri+1) — it is this section's next
+ * live reloc iff it is globally adjacent in the bucket. */
+ if (k + 1u < nr && rix[k + 1u] == ri + 1u) ++k;
continue;
}
}
diff --git a/src/obj/obj.c b/src/obj/obj.c
@@ -100,6 +100,19 @@ struct KitObjBuilder {
/* Linked-image view (segments + dynamic info). NULL on relocatable
* inputs; lazily created by obj_image_ensure. See obj.h. */
ObjImage* image;
+ /* Per-section reloc index (lazy cache). Without it, every native emitter
+ * rescans the whole flat reloc table once per section — O(n_sections *
+ * n_relocs), a latent superlinear axis that grows with -ffunction-sections
+ * and literal fan-out. `reloc_index` holds the global indices of live
+ * relocs grouped by section in ascending global order; `reloc_index_off`
+ * is the prefix-offset array (len reloc_index_nsec+1) so section `s`'s run
+ * is reloc_index[off[s] .. off[s+1]). Rebuilt by obj_reloc_index_ensure
+ * when `reloc_index_dirty` (set on reloc add and on obj_sweep_dead). */
+ u32* reloc_index;
+ u32* reloc_index_off;
+ u32 reloc_index_nsec; /* #sections reloc_index_off was sized for */
+ u32 reloc_index_len; /* #live relocs in reloc_index */
+ u8 reloc_index_dirty;
};
struct ObjSymIter {
@@ -194,6 +207,12 @@ void obj_free(ObjBuilder* ob) {
SecKeyIndex_fini(&ob->sec_by_key);
WeakAliases_fini(&ob->weak_aliases);
obj_image_free_(ob);
+ if (ob->reloc_index)
+ ob->heap->free(ob->heap, ob->reloc_index,
+ sizeof(u32) * ob->reloc_index_len);
+ if (ob->reloc_index_off)
+ ob->heap->free(ob->heap, ob->reloc_index_off,
+ sizeof(u32) * (ob->reloc_index_nsec + 1u));
ob->heap->free(ob->heap, ob, sizeof(*ob));
}
@@ -819,6 +838,7 @@ void obj_reloc_ex(ObjBuilder* ob, ObjSecId section_id, u32 offset,
r->pair = (u8)pair;
r->sym = sym;
r->addend = addend;
+ ob->reloc_index_dirty = 1; /* invalidate the per-section reloc index */
/* Any reloc against this symbol is enough to retain it through the
* emit-time UNDEF prune. See ObjSym::referenced. */
obj_sym_mark_referenced(ob, sym);
@@ -1105,10 +1125,76 @@ void obj_sweep_dead(ObjBuilder* ob) {
if (!lk || lk->removed) s->link = OBJ_SEC_NONE;
}
}
+
+ /* Removed flags changed — the per-section reloc index must rebuild. */
+ ob->reloc_index_dirty = 1;
}
/* ---- read side ---- */
+/* (Re)build the per-section reloc index: a counting sort of the live relocs
+ * keyed by section_id, preserving ascending global order within each section.
+ * O(n_relocs + n_sections). Idempotent while the index stays clean; callers
+ * reach it through obj_reloc_count / obj_reloc_section. Cast away const at the
+ * call sites — the index is a lazily-filled cache, not logical state. */
+static void obj_reloc_index_ensure(ObjBuilder* ob) {
+ u32 nsec, total, i, nlive;
+ u32* off;
+ if (ob->reloc_index_off && !ob->reloc_index_dirty) return;
+ nsec = Sections_count(&ob->sections);
+ total = Relocs_count(&ob->relocs);
+
+ if (!ob->reloc_index_off || ob->reloc_index_nsec != nsec) {
+ if (ob->reloc_index_off)
+ ob->heap->free(ob->heap, ob->reloc_index_off,
+ sizeof(u32) * (ob->reloc_index_nsec + 1u));
+ off = (u32*)ob->heap->alloc(ob->heap, sizeof(u32) * (nsec + 1u),
+ _Alignof(u32));
+ ob->reloc_index_off = off;
+ ob->reloc_index_nsec = nsec;
+ } else {
+ off = ob->reloc_index_off;
+ }
+ memset(off, 0, sizeof(u32) * (nsec + 1u));
+
+ /* Pass 1: tally live relocs into off[section_id + 1]. */
+ nlive = 0;
+ for (i = 0; i < total; ++i) {
+ const Reloc* r = Relocs_at(&ob->relocs, i);
+ if (r->removed) continue;
+ ++off[r->section_id + 1u];
+ ++nlive;
+ }
+ /* Prefix-sum: off[s] = start of section s's run; off[nsec] = nlive. */
+ for (i = 1; i <= nsec; ++i) off[i] += off[i - 1u];
+
+ if (!ob->reloc_index || ob->reloc_index_len != nlive) {
+ if (ob->reloc_index)
+ ob->heap->free(ob->heap, ob->reloc_index,
+ sizeof(u32) * ob->reloc_index_len);
+ ob->reloc_index =
+ nlive ? (u32*)ob->heap->alloc(ob->heap, sizeof(u32) * nlive,
+ _Alignof(u32))
+ : NULL;
+ ob->reloc_index_len = nlive;
+ }
+
+ /* Pass 2: scatter global indices into per-section runs. A heap-temp cursor
+ * (seeded from off[]) keeps the prefix offsets intact for the readers. */
+ if (nlive) {
+ u32* cur = (u32*)ob->heap->alloc(ob->heap, sizeof(u32) * (nsec + 1u),
+ _Alignof(u32));
+ memcpy(cur, off, sizeof(u32) * (nsec + 1u));
+ for (i = 0; i < total; ++i) {
+ const Reloc* r = Relocs_at(&ob->relocs, i);
+ if (r->removed) continue;
+ ob->reloc_index[cur[r->section_id]++] = i;
+ }
+ ob->heap->free(ob->heap, cur, sizeof(u32) * (nsec + 1u));
+ }
+ ob->reloc_index_dirty = 0;
+}
+
u32 obj_section_count(const ObjBuilder* ob) {
return Sections_count(&ob->sections);
}
@@ -1119,13 +1205,20 @@ const Section* obj_section_get(const ObjBuilder* ob, ObjSecId id) {
}
u32 obj_reloc_count(const ObjBuilder* ob, ObjSecId id) {
- u32 i, total = Relocs_count(&ob->relocs), n = 0;
- for (i = 0; i < total; ++i) {
- const Reloc* r = Relocs_at(&ob->relocs, i);
- if (r->removed) continue;
- if (r->section_id == id) ++n;
+ obj_reloc_index_ensure((ObjBuilder*)ob);
+ if (id >= ob->reloc_index_nsec) return 0;
+ return ob->reloc_index_off[id + 1u] - ob->reloc_index_off[id];
+}
+
+const u32* obj_reloc_section(const ObjBuilder* ob, ObjSecId id, u32* out_len) {
+ obj_reloc_index_ensure((ObjBuilder*)ob);
+ if (id >= ob->reloc_index_nsec) {
+ if (out_len) *out_len = 0;
+ return NULL;
}
- return n;
+ if (out_len)
+ *out_len = ob->reloc_index_off[id + 1u] - ob->reloc_index_off[id];
+ return ob->reloc_index + ob->reloc_index_off[id];
}
u32 obj_reloc_total(const ObjBuilder* ob) { return Relocs_count(&ob->relocs); }
diff --git a/src/obj/obj.h b/src/obj/obj.h
@@ -604,6 +604,11 @@ const Section* obj_section_get(const ObjBuilder*, ObjSecId id);
u32 obj_reloc_count(const ObjBuilder*, ObjSecId section_id);
u32 obj_reloc_total(const ObjBuilder*);
const Reloc* obj_reloc_at(const ObjBuilder*, u32 idx); /* 0..total-1 */
+/* The global indices of section_id's live relocs, ascending (the order
+ * obj_reloc_at expects), via a cached per-section index — O(1) lookup instead
+ * of rescanning the flat table. *out_len gets the count (may be 0 -> NULL). */
+const u32* obj_reloc_section(const ObjBuilder*, ObjSecId section_id,
+ u32* out_len);
/* Diagnostic spelling for a RelocKind. The returned pointer is a static
* literal that mirrors the enum identifier without the R_ prefix (e.g.
