commit c62703fb3078209bc4464af2d062c2623810fd48
parent bce407c9dc13e5d0194531c760c36d738c92c131
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 18:00:38 -0700
arena: geometric block growth and retain-on-reset
Replace the fixed-64-KiB linked list (head = most-recently-allocated) with a
geometrically-growing tail-appended chain (doubling per new block up to a 1 MiB
cap) so a large arena needs O(log n) heap allocations instead of O(n). A new
cur_block cursor tracks the block being filled, distinct from the allocation-
order head.
arena_reset now RETAINS every block (the high-water capacity) and only rewinds
the bump cursor to the first block; no heap traffic on reset/refill cycles. The
old behavior freed all-but-head on every reset, which churned large-block
allocations through malloc for every per-statement fold, per-function MC emit,
and per-expansion pp-scratch reset. arena_fini is the sole path that returns
blocks to the heap.
arena_alloc walks retained blocks before going to the heap, so a reset followed
by refill reuses the existing chain in order.
Consequently the delayed-fold arena in cg/fold.c now uses the default block size
(was 4 KiB; now the geometric 64 KiB baseline): the per-statement reset retains
the block rather than churning it.
Effect on the sqlite TU compile (KIT_METRICS): large (>=32 KiB) block allocs
440 -> 124 (-72 %), total heap allocs 4,278 -> 3,961; byte-identical.
Diffstat:
3 files changed, 79 insertions(+), 60 deletions(-)
diff --git a/src/cg/fold.c b/src/cg/fold.c
@@ -30,7 +30,10 @@ ApiDelayed* api_delayed_alloc(KitCg* g) {
return d;
}
if (!g->delayed_arena_init) {
- arena_init(&g->delayed_arena, (Heap*)g->c->ctx->heap, 4096);
+ /* Default block size + block retention (arena_reset keeps the high-water
+ * capacity): the per-statement reset reuses one block instead of churning
+ * tiny 4 KiB blocks through the heap. */
+ arena_init(&g->delayed_arena, (Heap*)g->c->ctx->heap, 0);
g->delayed_arena_init = 1;
}
return arena_new(&g->delayed_arena, ApiDelayed);
diff --git a/src/core/arena.c b/src/core/arena.c
@@ -1,8 +1,11 @@
-/* Bump-pointer arena. One linked list of fixed-size blocks; new blocks
- * are allocated when a request doesn't fit. arena_reset releases all but a
- * default-size head block (so the freed-and-reallocated common case stays
- * O(1)); a retained oversize head is released too. Oversize allocations get
- * their own dedicated block. */
+/* Bump-pointer arena. A singly-linked list of blocks held in allocation order.
+ * Block sizes grow geometrically (block_size, doubling up to ARENA_MAX_BLOCK)
+ * so a large arena needs O(log n) heap allocations instead of O(n) fixed-size
+ * blocks. arena_reset RETAINS every block (the high-water capacity) and only
+ * rewinds the bump cursor to the first block, so a reset/refill cycle reuses
+ * its memory with zero heap traffic; only arena_fini returns blocks to the
+ * heap. A request larger than the current geometric size gets its own
+ * exactly-sized block. */
#include "core/arena.h"
@@ -17,6 +20,8 @@ struct ArenaBlock {
};
#define ARENA_DEFAULT_BLOCK 65536
+#define ARENA_MAX_BLOCK (1u << 20) /* geometric block-growth ceiling (1 MiB) \
+ */
static ArenaBlock* block_new(Heap* h, size_t cap) {
ArenaBlock* b =
@@ -30,9 +35,11 @@ static ArenaBlock* block_new(Heap* h, size_t cap) {
void arena_init(Arena* a, Heap* h, size_t block_size) {
a->heap = h;
a->head = NULL;
+ a->cur_block = NULL;
a->cur = NULL;
a->end = NULL;
a->block_size = block_size ? block_size : ARENA_DEFAULT_BLOCK;
+ a->next_size = a->block_size;
}
void arena_fini(Arena* a) {
@@ -43,46 +50,29 @@ void arena_fini(Arena* a) {
b = next;
}
a->head = NULL;
+ a->cur_block = NULL;
a->cur = NULL;
a->end = NULL;
+ a->next_size = a->block_size;
}
int arena_is_empty(const Arena* a) {
- /* The pristine predicate: reset would be a no-op. Either nothing is
- * allocated (head==NULL), or the head is the lone, non-oversize block with
- * cur still at its base -- exactly the state arena_reset re-establishes. */
+ /* The pristine predicate: reset would be a no-op. Either nothing was ever
+ * allocated (head==NULL), or the cursor is rewound to the first block's base
+ * -- exactly the state arena_reset re-establishes (retained blocks past the
+ * head are fine: reset keeps them either way). */
if (!a->head) return 1;
- return a->head->next == NULL && a->head->cap <= a->block_size &&
- a->cur == a->head->data;
+ return a->cur_block == a->head && a->cur == a->head->data;
}
void arena_reset(Arena* a) {
- /* Free every block past the head, then reuse the head as the O(1) reset
- * baseline -- unless it is an oversize dedicated block (cap > block_size).
- * The head is the most-recently allocated block, so a one-off large
- * allocation just before reset would otherwise become a permanently
- * inflated baseline; release it and let the next alloc size a fresh one.
- * Skip entirely when the arena is already at its reset baseline. */
- if (arena_is_empty(a)) return;
- if (a->head) {
- ArenaBlock* b = a->head->next;
- while (b) {
- ArenaBlock* next = b->next;
- a->heap->free(a->heap, b, sizeof(ArenaBlock) + b->cap);
- b = next;
- }
- if (a->head->cap > a->block_size) {
- a->heap->free(a->heap, a->head, sizeof(ArenaBlock) + a->head->cap);
- a->head = NULL;
- a->cur = a->end = NULL;
- } else {
- a->head->next = NULL;
- a->cur = a->head->data;
- a->end = a->head->data + a->head->cap;
- }
- } else {
- a->cur = a->end = NULL;
- }
+ /* Retain the high-water capacity: rewind the cursor to the first block and
+ * keep every block linked for reuse on refill. No heap traffic -- distinct
+ * from arena_fini, which is the only path that returns blocks to the heap. */
+ if (!a->head) return;
+ a->cur_block = a->head;
+ a->cur = a->head->data;
+ a->end = a->head->data + a->head->cap;
}
void* arena_zalloc(Arena* a, size_t size, size_t align) {
@@ -92,33 +82,57 @@ void* arena_zalloc(Arena* a, size_t size, size_t align) {
}
void* arena_alloc(Arena* a, size_t size, size_t align) {
- uintptr_t p, aligned;
- size_t need;
+ uintptr_t aligned;
+ size_t cap;
+ ArenaBlock* b;
if (align == 0) align = 1;
- if (a->cur) {
- p = (uintptr_t)a->cur;
- aligned = (p + (uintptr_t)(align - 1)) & ~(uintptr_t)(align - 1);
+
+ /* Fast path: bump within the current block. */
+ if (a->cur_block) {
+ aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
if (aligned + size <= (uintptr_t)a->end) {
a->cur = (u8*)(aligned + size);
return (void*)aligned;
}
}
- /* New block. */
- need = ALIGN_UP(size, align);
- if (need < a->block_size) need = a->block_size;
- {
- ArenaBlock* b = block_new(a->heap, need);
- if (!b) return NULL;
- b->next = a->head;
- a->head = b;
- a->cur = b->data;
- a->end = b->data + b->cap;
- p = (uintptr_t)a->cur;
- aligned = (p + (uintptr_t)(align - 1)) & ~(uintptr_t)(align - 1);
- a->cur = (u8*)(aligned + size);
- return (void*)aligned;
+
+ /* Current block is full -- advance through the retained blocks (the
+ * high-water capacity preserved by arena_reset) before touching the heap. */
+ while (a->cur_block && a->cur_block->next) {
+ a->cur_block = a->cur_block->next;
+ a->cur = a->cur_block->data;
+ a->end = a->cur_block->data + a->cur_block->cap;
+ aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
+ if (aligned + size <= (uintptr_t)a->end) {
+ a->cur = (u8*)(aligned + size);
+ return (void*)aligned;
+ }
+ }
+
+ /* No retained block fits: append a fresh one. Use the geometric size when the
+ * request fits it (and grow the next size), else size the block exactly to an
+ * oversize request. cap >= size + align always leaves room for alignment, as
+ * the heap returns max_align_t-aligned storage. */
+ cap = size + align;
+ if (cap <= a->next_size) {
+ cap = a->next_size;
+ a->next_size *= 2;
+ if (a->next_size > ARENA_MAX_BLOCK) a->next_size = ARENA_MAX_BLOCK;
}
+ b = block_new(a->heap, cap);
+ if (!b) return NULL;
+ b->next = NULL;
+ if (a->cur_block)
+ a->cur_block->next = b;
+ else
+ a->head = b;
+ a->cur_block = b;
+ a->cur = b->data;
+ a->end = b->data + b->cap;
+ aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
+ a->cur = (u8*)(aligned + size);
+ return (void*)aligned;
}
char* arena_strdup(Arena* a, const char* s, size_t len) {
diff --git a/src/core/arena.h b/src/core/arena.h
@@ -8,10 +8,12 @@ typedef struct ArenaBlock ArenaBlock;
struct Arena {
Heap* heap;
- ArenaBlock* head;
- u8* cur; /* points into head's buffer */
- u8* end; /* end of head's buffer */
- size_t block_size;
+ ArenaBlock* head; /* oldest block (allocation order); NULL until 1st alloc */
+ ArenaBlock* cur_block; /* block currently being filled */
+ u8* cur; /* bump cursor within cur_block */
+ u8* end; /* end of cur_block's buffer */
+ size_t block_size; /* base / minimum block size */
+ size_t next_size; /* geometric size for the next freshly allocated block */
};
void arena_init(Arena*, Heap*, size_t block_size);
