commit f70aaa45e83ca85e25ab7145a4f4a03dd391e9fe
parent 50893346b1bb4df3b6a568933a6ec7effaf9f04e
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 11 Jun 2026 13:17:22 -0700
perf(link): pre-size the symbol hashmaps to cut resize churn
Two symbol hashmaps rehashed mid-stream on symbol-heavy links (the
SymNameIndex_resize / SymHash_resize the link profile flags at ~3% on a
1M-symbol link):
- the per-object SymNameIndex grew from obj_new's 256-slot default as a
large object was ingested;
- the linker's global symbol map img->globals grew from empty as symbols
were resolved.
Add a generic NAME##_reserve(m, n) to the hashmap facility (grows to hold
n entries without an intermediate rehash; cap stays a power of two; no-op
if already large enough). Use it:
- obj_reserve_symbols(ob, n) — readers know the symbol count from the
symtab header; read_macho calls it before streaming symbols in;
- symhash_reserve(&img->globals, used + nsyms_in_input) in
link_resolve_symbols, before each input's bulk insert (format-agnostic,
so it helps elf/coff links too).
Byte-identical (reserve is pre-allocation only; resize is order-preserving
so symbol order/output is unchanged — gate clean, linked exes byte-equal).
Measured kit ld best-of-9 on a 256k-symbol link: 314ms -> 299ms (-4.8%);
~-2.7% on a 1M-symbol resolve. Negligible on typical small links.
test-link 124/0, test-elf 41/0, test-ar 20/20, smoke-x64/rv64 + isa green.
Diffstat:
6 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/include/kit/support/hashmap.h b/include/kit/support/hashmap.h
@@ -81,6 +81,18 @@ static inline uint32_t kit_hash_u64(uint64_t x) {
NAME##_init_cap(m, h, KIT_HASHMAP_INIT_CAP); \
} \
\
+ /* Grow so `n` entries can be inserted without an intermediate rehash. \
+ * Call before a bulk insert when the count is known; a no-op if already \
+ * large enough. cap stays a power of two (the probe masks with cap-1). */ \
+ KIT_HASHMAP_UNUSED static inline void NAME##_reserve(NAME* m, \
+ uint32_t n) { \
+ uint32_t need = m->cap ? m->cap : KIT_HASHMAP_INIT_CAP; \
+ while ((uint64_t)n * KIT_HASHMAP_LOAD_DEN >= \
+ (uint64_t)need * KIT_HASHMAP_LOAD_NUM) \
+ need <<= 1u; \
+ if (need > m->cap) NAME##_resize(m, need); \
+ } \
+ \
KIT_HASHMAP_UNUSED static inline void NAME##_fini(NAME* m) { \
if (m->slots) \
m->heap->free(m->heap, m->slots, sizeof(*m->slots) * m->cap); \
diff --git a/src/link/link_internal.h b/src/link/link_internal.h
@@ -139,6 +139,7 @@ HASHMAP_DEFINE(SymHash, Sym, LinkSymId, link_sym_hash_);
static inline void symhash_init(SymHash* h, Heap* heap) {
SymHash_init(h, heap);
}
+static inline void symhash_reserve(SymHash* h, u32 n) { SymHash_reserve(h, n); }
static inline void symhash_fini(SymHash* h) { SymHash_fini(h); }
static inline LinkSymId symhash_get(const SymHash* h, Sym name) {
LinkSymId* hit = SymHash_get(h, name);
diff --git a/src/link/link_resolve.c b/src/link/link_resolve.c
@@ -236,6 +236,12 @@ void link_resolve_symbols(Linker* l, LinkImage* img) {
link_input_map_alloc(img, m, ob,
nsyms_in_input + 1u /* +1 for id-0 slot */);
+ /* Pre-size the global symbol map for this input's symbols so the bulk
+ * insert below never rehashes mid-stream. Only globals/weaks actually land
+ * in img->globals, so this slightly over-reserves; it kills the resize
+ * cascade (256 -> N) on symbol-heavy inputs (e.g. a large linked object). */
+ symhash_reserve(&img->globals, img->globals.used + nsyms_in_input);
+
it = obj_symiter_new(ob);
while (obj_symiter_next(it, &e)) {
const ObjSym* s = e.sym;
diff --git a/src/obj/macho/read.c b/src/obj/macho/read.c
@@ -496,6 +496,7 @@ ObjBuilder* read_macho(Compiler* c, const char* name, const u8* data,
ObjBuilder* ob = obj_new(c);
if (!ob) compiler_panic(c, SRCLOC_NONE, "read_macho: obj_new failed");
+ obj_reserve_symbols(ob, nsyms); /* skip the 256->nsyms resize cascade */
/* ---- pass 2: create ObjSecs and copy bytes. */
for (u32 i = 0; i < nmsecs; ++i) {
diff --git a/src/obj/obj.c b/src/obj/obj.c
@@ -145,6 +145,15 @@ ObjBuilder* obj_new(Compiler* c) {
Compiler* obj_compiler(const ObjBuilder* ob) { return ob ? ob->c : NULL; }
+/* Pre-size the symbol-name index for `n` incoming symbols. Object readers know
+ * the symbol count up front (the symtab header), so calling this before
+ * streaming symbols in skips the resize cascade off obj_new's 256-slot default
+ * on a symbol-heavy object (e.g. a large .o the linker ingests). No-op once the
+ * index is already large enough; order-preserving (resize reinserts). */
+void obj_reserve_symbols(ObjBuilder* ob, u32 n) {
+ if (ob) SymNameIndex_reserve(&ob->sym_by_name, n);
+}
+
/* Private accessors for the `_tlv_bootstrap` cache used by obj_define_tls.
* Lives in obj.c so the ObjBuilder field doesn't leak through obj.h. */
ObjSymId obj_tlv_bootstrap_get(const ObjBuilder* ob) {
diff --git a/src/obj/obj.h b/src/obj/obj.h
@@ -418,6 +418,11 @@ void obj_free(ObjBuilder*);
* against the right pool. */
Compiler* obj_compiler(const ObjBuilder*);
+/* Pre-size the symbol-name index for `n` incoming symbols (object readers know
+ * the count from the symtab header). Skips the resize cascade when ingesting a
+ * symbol-heavy object. No-op if already large enough; order-preserving. */
+void obj_reserve_symbols(ObjBuilder*, u32 n);
+
/* ---- write side (MCEmitter/CGTarget and .o readers) ---- */
ObjSecId obj_section(ObjBuilder*, Sym name, SecKind, u16 flags, u32 align);
ObjSecId obj_section_ex(ObjBuilder*, Sym name, SecKind, SecSem, u16 flags,
