Skip to content

Commit 959f4de

Browse files
committed
perf: cut the allocation churn and repeated work the sanitizer found
Every item here was measured on a real corpus before and after, not reasoned about. Go corpus, event lane, first run -> now: 245.5 M allocations -> 134.8 M, 190 GB cumulative -> 29.3 GB, 158 GB never written -> 9.2 GB, 132 M churn pairs -> 35.7 M, 93 GB of allocator byte work -> 0.84 GB. Wall clock: Go 40.7 s -> 19.3 s, linux kernel 239.6 s -> 194.6 s, and all ten LSP languages faster with none slower. Graph output is unchanged, proven rather than assumed: per-class multiset digests over the full kernel index (8,563,471 nodes identical, 18/20 node classes and 18/24 edge classes byte-identical, the rest differing only in the classes a same-binary re-run also perturbs through worker merge order). The changes, each with its own reason: arena an exact arena that is appended to later restarts growth at 8 KB instead of the 64 KB default — the cross-file pass adds a few resolved calls to a compacted result, so the default block was ~60 KB untouched per result, 0.5 GB of the Go worker peak. cbm_arena_init_lazy defers the first block for arenas that are usually never used at all. scratch per-thread reuse instead of allocate-and-free per unit of work: result_compact (8 MB kept), the cross-file pass (4 MB), extract_defs' walk stack, and the sqlite index cells (a 1 MB arena replacing 12.1 M malloc/free pairs on Go). Walk frames moving into scratch is why pass_k8s now opens the keep window explicitly: without it every YAML file opened a 512 KB scratch on the main thread, +3 GB. sqlite index cells are written in place — building the record and copying it into the cell was a second allocation per entry, 16 M record buffers of pure churn on Go. registry is_test_qn and common_prefix_len in one pass, per-bucket test flags computed once instead of per candidate comparison, and the reachability keys arena allocated lazily. minhash the unique-trigram set is sized from the trigram count and skips repeats, and LSH queries reuse one seen-set per worker instead of allocating per query. parallel lsp_surface rows and the k8s manifest prep now run across workers (graph writes stay sequential and ordered), the file node is hoisted out of register_and_link_def, and configlink prepares dependency imports once with a length prefilter. go_lsp one sealed stdlib registry shared by all workers, published by CAS, instead of one per worker. Signed-off-by: Martin Vogel <[email protected]>
1 parent 632c19d commit 959f4de

37 files changed

Lines changed: 2382 additions & 510 deletions

‎internal/cbm/cbm.c‎

Lines changed: 182 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
* guard, so whichever is included first is the one this file sees. */
44
#include "foundation/arena.h" // cbm_arena_init_sized
55
#include "foundation/mem_core.h" // class accounting for the bound allocators
6+
#include "foundation/mem_events.h" // waste sanitizer: the bound allocators bypass every observer
67
#include "foundation/log.h" // cbm_log_warn -- extract.lsp.skipped
78
#include "cbm.h"
89
#include "arena.h" // CBMArena, cbm_arena_init/alloc/strdup/destroy
@@ -347,28 +348,55 @@ static mi_heap_t *sqlite_heap(void) {
347348
return tl_sqlite_heap;
348349
}
349350

351+
#if defined(CBM_MEMWASTE) && CBM_MEMWASTE
352+
#define BOUND_ALLOC(block, n, flags) \
353+
do { \
354+
if ((block) && cbm_memev_enabled()) { \
355+
cbm_memev_alloc_ex((block), (n), mi_usable_size(block), \
356+
__builtin_return_address(0), (unsigned)(flags)); \
357+
} \
358+
} while (0)
359+
#define BOUND_REALLOC(old_block, grown, n) \
360+
do { \
361+
if ((grown) && cbm_memev_enabled()) { \
362+
cbm_memev_realloc((old_block), (grown), (n), mi_usable_size(grown), \
363+
__builtin_return_address(0)); \
364+
} \
365+
} while (0)
366+
#define BOUND_FREE(block) cbm_memev_free(block)
367+
#else
368+
#define BOUND_ALLOC(block, n, flags) ((void)0)
369+
#define BOUND_REALLOC(old_block, grown, n) ((void)0)
370+
#define BOUND_FREE(block) ((void)0)
371+
#endif
372+
350373
static void *cbm_sqlite_malloc(int n) {
351374
mi_heap_t *heap = sqlite_heap();
352375
void *block = heap ? mi_heap_malloc(heap, (size_t)n) : mi_malloc((size_t)n);
353376
if (block) {
354377
cbm_mem_class_add_external(CBM_MEM_CLASS_STORE, mi_usable_size(block));
355378
}
379+
BOUND_ALLOC(block, (size_t)n, 0);
356380
return block;
357381
}
358382
static void cbm_sqlite_free(void *p) {
359383
if (p) {
360384
cbm_mem_class_remove_external(CBM_MEM_CLASS_STORE, mi_usable_size(p));
385+
BOUND_FREE(p);
361386
}
362387
mi_free(p);
363388
}
364389
static void *cbm_sqlite_realloc(void *p, int n) {
365390
size_t old_size = p ? mi_usable_size(p) : 0;
366391
mi_heap_t *heap = sqlite_heap();
392+
CBM_MEMEV_BACKING(1);
367393
void *grown = heap ? mi_heap_realloc(heap, p, (size_t)n) : mi_realloc(p, (size_t)n);
394+
CBM_MEMEV_BACKING(-1);
368395
if (grown) {
369396
cbm_mem_class_remove_external(CBM_MEM_CLASS_STORE, old_size);
370397
cbm_mem_class_add_external(CBM_MEM_CLASS_STORE, mi_usable_size(grown));
371398
}
399+
BOUND_REALLOC(p, grown, (size_t)n);
372400
return grown;
373401
}
374402
static int cbm_sqlite_size(void *p) {
@@ -384,27 +412,33 @@ static void *cbm_ts_malloc(size_t n) {
384412
if (block) {
385413
cbm_mem_class_add_external(CBM_MEM_CLASS_TS_TREE, mi_usable_size(block));
386414
}
415+
BOUND_ALLOC(block, n, 0);
387416
return block;
388417
}
389418
static void *cbm_ts_calloc(size_t count, size_t size) {
390419
void *block = mi_calloc(count, size);
391420
if (block) {
392421
cbm_mem_class_add_external(CBM_MEM_CLASS_TS_TREE, mi_usable_size(block));
393422
}
423+
BOUND_ALLOC(block, count * size, CBM_MEMEV_ZEROED);
394424
return block;
395425
}
396426
static void *cbm_ts_realloc(void *p, size_t n) {
397427
size_t old_size = p ? mi_usable_size(p) : 0;
428+
CBM_MEMEV_BACKING(1);
398429
void *grown = mi_realloc(p, n);
430+
CBM_MEMEV_BACKING(-1);
399431
if (grown) {
400432
cbm_mem_class_remove_external(CBM_MEM_CLASS_TS_TREE, old_size);
401433
cbm_mem_class_add_external(CBM_MEM_CLASS_TS_TREE, mi_usable_size(grown));
402434
}
435+
BOUND_REALLOC(p, grown, n);
403436
return grown;
404437
}
405438
static void cbm_ts_free(void *p) {
406439
if (p) {
407440
cbm_mem_class_remove_external(CBM_MEM_CLASS_TS_TREE, mi_usable_size(p));
441+
BOUND_FREE(p);
408442
}
409443
mi_free(p);
410444
}
@@ -477,13 +511,105 @@ void cbm_reset_thread_parser(void) {
477511
}
478512
}
479513

514+
enum { FIELD_CACHE_SLOTS = 512, FIELD_NAME_CACHED_MAX = 31 };
515+
typedef struct {
516+
const TSLanguage *lang;
517+
uint32_t len;
518+
TSFieldId id;
519+
char name[FIELD_NAME_CACHED_MAX + 1];
520+
} field_id_slot_t;
521+
static CBM_TLS field_id_slot_t tl_field_ids[FIELD_CACHE_SLOTS];
522+
523+
TSNode cbm_ts_child_by_field_name(TSNode node, const char *name, uint32_t name_length) {
524+
if (!name || name_length == 0 || name_length > FIELD_NAME_CACHED_MAX || ts_node_is_null(node)) {
525+
return (ts_node_child_by_field_name)(node, name, name_length); /* the real one */
526+
}
527+
const TSLanguage *lang = ts_node_language(node);
528+
uint64_t h = 0xcbf29ce484222325ULL ^ (uint64_t)(uintptr_t)lang;
529+
for (uint32_t i = 0; i < name_length; i++) {
530+
h ^= (uint8_t)name[i];
531+
h *= 0x100000001b3ULL;
532+
}
533+
field_id_slot_t *slot = &tl_field_ids[h & (FIELD_CACHE_SLOTS - 1)];
534+
if (slot->lang != lang || slot->len != name_length ||
535+
memcmp(slot->name, name, name_length) != 0) {
536+
/* The content is compared, never just the pointer: callers also pass
537+
* names built in reused buffers. */
538+
slot->id = ts_language_field_id_for_name(lang, name, name_length);
539+
slot->lang = lang;
540+
slot->len = name_length;
541+
memcpy(slot->name, name, name_length);
542+
}
543+
return ts_node_child_by_field_id(node, slot->id);
544+
}
545+
546+
static CBM_TLS TSTreeCursor tl_cursor;
547+
static CBM_TLS bool tl_cursor_live = false;
548+
549+
TSTreeCursor *cbm_thread_cursor(TSNode node) {
550+
if (tl_cursor_live) {
551+
ts_tree_cursor_reset(&tl_cursor, node);
552+
} else {
553+
tl_cursor = ts_tree_cursor_new(node);
554+
tl_cursor_live = true;
555+
}
556+
return &tl_cursor;
557+
}
558+
559+
/* Per-depth cursors for recursive walks (cbm_cursor_acquire). A walk at depth d
560+
* holds slot d while it recurses into depth d + 1; the LSP call walkers used to
561+
* create and delete a cursor at EVERY node -- 49.8 M cursor stacks on the Go
562+
* corpus (waste sanitizer, 2026-09-17). Deeper than the pool: private cursors. */
563+
enum { CURSOR_POOL_DEPTH = 128 };
564+
static CBM_TLS TSTreeCursor tl_cursor_pool[CURSOR_POOL_DEPTH];
565+
static CBM_TLS uint8_t tl_cursor_pool_state[CURSOR_POOL_DEPTH]; /* bit0 live, bit1 busy */
566+
enum { CURSOR_LIVE = 1, CURSOR_BUSY = 2 };
567+
568+
TSTreeCursor *cbm_cursor_acquire(cbm_cursor_lease_t *lease, int depth, TSNode node) {
569+
if (depth >= 0 && depth < CURSOR_POOL_DEPTH && !(tl_cursor_pool_state[depth] & CURSOR_BUSY)) {
570+
if (tl_cursor_pool_state[depth] & CURSOR_LIVE) {
571+
ts_tree_cursor_reset(&tl_cursor_pool[depth], node);
572+
} else {
573+
tl_cursor_pool[depth] = ts_tree_cursor_new(node);
574+
}
575+
tl_cursor_pool_state[depth] = CURSOR_LIVE | CURSOR_BUSY;
576+
lease->slot = depth;
577+
lease->cursor = &tl_cursor_pool[depth];
578+
return lease->cursor;
579+
}
580+
lease->private_cursor = ts_tree_cursor_new(node);
581+
lease->slot = -1;
582+
lease->cursor = &lease->private_cursor;
583+
return lease->cursor;
584+
}
585+
586+
void cbm_cursor_release(cbm_cursor_lease_t *lease) {
587+
if (lease->slot < 0) {
588+
ts_tree_cursor_delete(&lease->private_cursor);
589+
} else {
590+
tl_cursor_pool_state[lease->slot] &= (uint8_t)~CURSOR_BUSY;
591+
}
592+
lease->cursor = NULL;
593+
}
594+
480595
void cbm_destroy_thread_parser(void) {
481596
// Full cleanup: delete the parser. Call on worker thread exit.
482597
if (tl_parser) {
483598
ts_parser_delete(tl_parser);
484599
tl_parser = NULL;
485600
tl_parser_lang = CBM_LANG_COUNT;
486601
}
602+
if (tl_cursor_live) {
603+
ts_tree_cursor_delete(&tl_cursor);
604+
tl_cursor_live = false;
605+
}
606+
for (int d = 0; d < CURSOR_POOL_DEPTH; d++) {
607+
/* a busy slot belongs to a walk still on this stack: leave it */
608+
if (tl_cursor_pool_state[d] == CURSOR_LIVE) {
609+
ts_tree_cursor_delete(&tl_cursor_pool[d]);
610+
tl_cursor_pool_state[d] = 0;
611+
}
612+
}
487613
}
488614

489615
void cbm_shutdown(void) {
@@ -1635,6 +1761,7 @@ CBMFileResult *cbm_extract_file(const char *source, int source_len, CBMLanguage
16351761
* that bound and so a singleton OS allocation. One file in twelve thousand
16361762
* pays it, which is why the cost is accepted. */
16371763
enum { CBM_EXTRACT_SCRATCH_BLOCK = CBM_SZ_512 * CBM_SZ_1K };
1764+
enum { CBM_EXTRACT_SCRATCH_KEEP_BYTES = 4 * CBM_SZ_1K * CBM_SZ_1K };
16381765

16391766
static CBMFileResult *extract_file_ex_body(const char *source, int source_len, CBMLanguage language,
16401767
const char *project, const char *rel_path,
@@ -2274,6 +2401,17 @@ static CBMFileResult *extract_file_ex_body(const char *source, int source_len, C
22742401
static CBM_TLS CBMArena tl_work_arena;
22752402
static CBM_TLS bool tl_work_arena_live = false;
22762403

2404+
/* The traversal scratch arena is kept per worker the same way. A thread keeps
2405+
* one only after it has given a working arena back (so only pipeline workers,
2406+
* which call cbm_work_arena_release when they end), and only while it holds no
2407+
* more than CBM_EXTRACT_SCRATCH_KEEP_BYTES (an outsized file's arena is not
2408+
* worth holding). Before this every file created and destroyed a
2409+
* 512 KB block -- 28,145 of them on the Go corpus, 14 GB allocated, 99.9 %
2410+
* never written and 7,136 never touched (waste sanitizer, 2026-09-17). */
2411+
static CBM_TLS CBMArena tl_scratch_arena;
2412+
static CBM_TLS bool tl_scratch_live = false;
2413+
static CBM_TLS bool tl_scratch_keep = false;
2414+
22772415
void cbm_work_arena_take(CBMArena *into) {
22782416
if (tl_work_arena_live) {
22792417
*into = tl_work_arena;
@@ -2289,12 +2427,27 @@ void cbm_work_arena_release(void) {
22892427
cbm_arena_destroy(&tl_work_arena);
22902428
tl_work_arena_live = false;
22912429
}
2430+
if (tl_scratch_live) {
2431+
cbm_arena_destroy(&tl_scratch_arena);
2432+
tl_scratch_live = false;
2433+
}
2434+
cbm_result_compact_release_thread();
2435+
tl_scratch_keep = false;
2436+
}
2437+
2438+
bool cbm_work_arena_keeping(void) {
2439+
return tl_scratch_keep;
2440+
}
2441+
2442+
void cbm_work_arena_keep_begin(void) {
2443+
tl_scratch_keep = true;
22922444
}
22932445

22942446
void cbm_work_arena_give(CBMArena *from) {
22952447
if (!from || from->nblocks == 0) {
22962448
return;
22972449
}
2450+
tl_scratch_keep = true; /* a pipeline worker: its release call will come */
22982451
if (tl_work_arena_live || cbm_arena_capacity(from) > (size_t)CBM_WORK_ARENA_KEEP_BYTES) {
22992452
cbm_arena_destroy(from);
23002453
return;
@@ -2307,20 +2460,41 @@ void cbm_work_arena_give(CBMArena *from) {
23072460
/* Public entry. Owns the traversal scratch arena for the whole of one file's
23082461
* extraction: created here, handed to the body as ctx->scratch, destroyed on
23092462
* the way out. The body has seven early returns, so bracketing it in a wrapper
2310-
* is what keeps that to one create and one destroy. If the arena cannot be
2311-
* created, the body is handed NULL and the traversal stacks fall back to the
2312-
* result arena, which is what shipped before #1997. */
2463+
* is what keeps that to one create and one destroy. The arena is LAZY: it takes
2464+
* its first block when a traversal stack first needs one, so a file that builds
2465+
* no stack (most non-code files) costs nothing -- opened eagerly, 3.3 GB of
2466+
* 512 KB blocks were never read or written on the Go corpus (waste sanitizer,
2467+
* 2026-09-17). If the block cannot be allocated, the stack's allocation fails
2468+
* and it stops growing, exactly as on any later out-of-memory. */
23132469
CBMFileResult *cbm_extract_file_ex(const char *source, int source_len, CBMLanguage language,
23142470
const char *project, const char *rel_path,
23152471
int64_t timeout_micros, const char **extra_defines,
23162472
const char **include_paths, const CBMMacroTable *macro_table,
23172473
const CBMReturnTypeTable *return_type_table) {
23182474
CBMArena scratch;
2319-
cbm_arena_init_sized(&scratch, CBM_EXTRACT_SCRATCH_BLOCK);
2320-
CBMFileResult *result = extract_file_ex_body(
2321-
source, source_len, language, project, rel_path, timeout_micros, extra_defines,
2322-
include_paths, macro_table, return_type_table, scratch.nblocks > 0 ? &scratch : NULL);
2323-
cbm_arena_destroy(&scratch);
2475+
if (tl_scratch_live) {
2476+
scratch = tl_scratch_arena;
2477+
tl_scratch_live = false;
2478+
cbm_arena_rewind(&scratch);
2479+
} else {
2480+
cbm_arena_init_lazy(&scratch, CBM_EXTRACT_SCRATCH_BLOCK);
2481+
}
2482+
CBMFileResult *result =
2483+
extract_file_ex_body(source, source_len, language, project, rel_path, timeout_micros,
2484+
extra_defines, include_paths, macro_table, return_type_table, &scratch);
2485+
/* !tl_scratch_live: a nested extraction (an embedded language inside this
2486+
* file) may already have parked its own; never overwrite it. */
2487+
/* Kept up to CBM_EXTRACT_SCRATCH_KEEP_BYTES, grown blocks included: the
2488+
* definitions walk draws its frames from this arena too, so a file with
2489+
* many definitions grows it past the first block, and dropping every grown
2490+
* arena turned those files into fresh 512 KB blocks for the next file. */
2491+
if (tl_scratch_keep && !tl_scratch_live && scratch.nblocks > 0 &&
2492+
cbm_arena_capacity(&scratch) <= (size_t)CBM_EXTRACT_SCRATCH_KEEP_BYTES) {
2493+
tl_scratch_arena = scratch;
2494+
tl_scratch_live = true;
2495+
} else {
2496+
cbm_arena_destroy(&scratch);
2497+
}
23242498
return result;
23252499
}
23262500

‎internal/cbm/cbm.h‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,17 @@
66
#include "arena.h"
77
#include "tree_sitter/api.h"
88

9+
/* Field lookups by NAME resolve the name with a linear strncmp scan over the
10+
* grammar's field table on every call -- 951 M strncmp calls on the Go corpus
11+
* (waste sanitizer, 2026-09-17) across ~1,200 call sites. Tree-sitter's own
12+
* implementation is exactly "field id for name, then child by field id"; this
13+
* caches the first half per thread (language, name) and keeps the second.
14+
* Every extractor includes this header, so every call site gets it. */
15+
TSNode cbm_ts_child_by_field_name(TSNode node, const char *name, uint32_t name_length);
16+
/* Variadic: call sites spell the name and its length as ONE macro argument
17+
* (TS_FIELD("body") expands to "body", 4), which must expand before the call. */
18+
#define ts_node_child_by_field_name(...) cbm_ts_child_by_field_name(__VA_ARGS__)
19+
920
// Language enum mirrors lang.Language in Go.
1021
// Order must match lang_specs.c tables.
1122
typedef enum {
@@ -729,6 +740,16 @@ void cbm_work_arena_take(CBMArena *into);
729740
void cbm_work_arena_give(CBMArena *from);
730741
/* Drop this thread's kept working arena (end of an extraction pass). */
731742
void cbm_work_arena_release(void);
743+
/* True on a thread that has given a working arena back, i.e. a pipeline
744+
* worker whose cbm_work_arena_release is guaranteed to run: only such a thread
745+
* may keep per-thread scratch between files. */
746+
bool cbm_work_arena_keeping(void);
747+
/* Let this thread keep its per-file extraction scratch between the files of a
748+
* sequential loop; the caller must call cbm_work_arena_release on the same
749+
* thread when the loop ends (every return path). */
750+
void cbm_work_arena_keep_begin(void);
751+
/* Free the compaction scratch this thread kept (cbm_work_arena_release calls it). */
752+
void cbm_result_compact_release_thread(void);
732753

733754
CBMFileResult *cbm_extract_file(const char *source, int source_len, CBMLanguage language,
734755
const char *project, const char *rel_path, int64_t timeout_micros,
@@ -771,6 +792,25 @@ void cbm_reset_thread_parser(void);
771792
// Destroy the thread-local parser. Call on worker thread exit.
772793
void cbm_destroy_thread_parser(void);
773794

795+
// This thread's reusable tree cursor, reset to `node`. Child walks run once per
796+
// visited node; a cursor per walk was a malloc + free of its stack each time
797+
// (49.8 M on the Go corpus, waste sanitizer 2026-09-17). Valid until the next
798+
// call on this thread; released with the thread parser.
799+
TSTreeCursor *cbm_thread_cursor(TSNode node);
800+
801+
// Reusable cursors for RECURSIVE walks: one per recursion depth on this thread,
802+
// so a walk that recurses from inside its child loop never shares a cursor with
803+
// its own callers. A slot already in use (another walker nested on this thread)
804+
// hands out a private cursor instead; release deletes it. Released with the
805+
// thread parser.
806+
typedef struct {
807+
TSTreeCursor *cursor;
808+
TSTreeCursor private_cursor;
809+
int slot; /* -1: private */
810+
} cbm_cursor_lease_t;
811+
TSTreeCursor *cbm_cursor_acquire(cbm_cursor_lease_t *lease, int depth, TSNode node);
812+
void cbm_cursor_release(cbm_cursor_lease_t *lease);
813+
774814
// Shutdown the library. Call once at exit.
775815
void cbm_shutdown(void);
776816

0 commit comments

Comments
 (0)