Issue #490: ADR-327 D4-D11: memory budgets per task and per shared value — measured, decided, to build

Open and answer this issue on GitHub.

performance, ready · opened 2026-10-06 · updated 2026-10-12 · 4 comments

The direction is decided in ADR-327 D4-D11 (history in #121 and in the comments below). The specification states it in:

• Part I 6.3 (poisoning),
• Part II 12 (“A task has a memory budget”),

• Part III 15.2 and Part III’s code table (NK2506).

• D4: Nikaia allocates its own memory. List, String and Map stand on allocator-api2/hashbrown, and every allocation can fail.
• D5: every task, and every shared value, allocates from a block of its own, and the block is its budget.
• D6: a full block ends the task, or poisons the shared value.
• D7: an exchangeable strategy sizes the blocks. No number is configured; a package may offer a strategy with a fixed ceiling.
• D8: toward Rust, views cross free. A list or text handed to a Rust owner crosses as it is wherever the compiler follows it back to where it was built: through locals, results, parameters of functions whose every call it sees, and fields of values built in the package. The compiler builds it there outside the block, counted against the budget. A value taken from a channel or handed back by Rust crosses as it is too. Where the compiler cannot follow the value (a pub function’s parameter, a value read out of a shared value), the hand-over is refused with NK2506 and the program writes .clone(). A copy is written or refused, never inserted (ADR-282 D7). The better the following, the fewer .clone()s are asked for. A Vec/String that Rust hands back is taken over without a copy.
• D9: a value that can outlive its task is never in the task’s block: sent on a channel, stored into a shared value outside its door, handed to Rust to own, or the task’s result. It is built outside the block and counted while the task holds it, so the block is emptied whole when the task ends. From the hand-over the value counts against its receiver: the task that takes it from the channel or joins the task that produced it, or the shared value it is stored into. A receiver it does not fit is a full block (D6).
• D10: a budget counts what a task holds, not what it has allocated. Memory a task frees can be allocated again.
• D11: no needless poisoning.
  • An update whose value copies (a number, bool, char) works on a copy and puts it in place at its end, so a panic in it poisons nothing.
  • An update_all copies only where both values copy, and puts both back together while it still holds both locks. Where one does not copy, neither is copied and a panic poisons both, because values changed in one door must agree.
  • access/access_all cannot change a value, so a panic in them poisons nothing.
  • A change made in an earlier door is not undone by a later panic.

What exists today:

• ADR-327 D1-D3 (poisoning, SharedMut::supervised) and ADR-326 D4 (a panic ends only its task) are built.
• A word-sized value that crosses threads already updates on a copy with compare-and-swap, outside update_all (Part II 12.2). A panic there never poisons.
• Nothing of D4-D11 is built: the emitter writes Rust’s Vec/String, there is no allocator of Nikaia’s own, and every other door poisons on a panic, access included (held in lock.rs and std’s mutex).

Measured (comments below)

	instructions	mispredicted branches
a 64 KiB bump block per task, against malloc (benches/taskblock, 0.0.602)	−41%	about −50%
fallible collections on allocator-api2/hashbrown, against std (benches/fallible, 0.0.603)	+0.2%	+5% (1BRC), +7% (tasks)

The owner approved the direction on these numbers (step 3, done).

To build

Measured first only where a step can be slower than what it replaces. A step that can only be faster is built without a measurement.

1. Measure D10. The bump block measured above never reuses freed memory, so it cannot serve a long-running task (a connection loop, main). Measure a block that gives freed memory back to its task (size classes with free lists inside the block, or a chain of blocks) against the bump block, on benches/taskblock. Add a second workload: one long task that frees and allocates in a loop. If reuse makes short tasks slower, a task may start as a bump block and switch to reuse at its first full block. The measurement decides; the owner is asked only if neither form keeps the 41%.
2. D11, independent of the rest, can go first (crates/nikaia-std/src/lock.rs, and the emitter’s lowering of the doors):
   • an update of a value that copies runs on a local copy, written back at the block’s end, with no poison mark while it runs;
   • an update_all where both values copy does the same with both, written back together before either lock is released; otherwise it stays as today;
   • access/access_all set no poison mark. On Crossing, take the guard so that a panic in a reading block does not poison std’s mutex.
   • Tests:
     • kasse.update fn(mut v) { v += i64::MAX } in a task panics; a second task reads the old value through get, without a panic;
     • an update of a SharedMut[Vec[i64]] that panics after a push still poisons;
     • update_all(a, b) over two i64s whose block panics after changing the first leaves both old values readable;
     • update_all(a, b) over an i64 and a Vec[i64] that panics poisons both;
     • an access whose block panics leaves the value readable.
3. The allocator (D4, D5, D10):
   • a task-local allocator in nikaia-std;
   • List/String/Map on allocator-api2/hashbrown, with that allocator as a handle that is either the task’s block or outside (D8, D9);
   • growth through try_reserve. A full block panics in the task, outside the allocator (D6).
   • Copy byte runs with one copy_nonoverlapping. allocator-api2’s extend_from_slice copies one element at a time, which doubled the tasks’ count in step 1.
   • Text that is already valid UTF-8 is not checked again.
   • The panic path is a #[cold] function. Rust has no #[unlikely] attribute.
4. The shared value’s block (D5, D6): inside a SharedMut door and in Shared’s construction, allocations go to the value’s block; a full one poisons the value.
5. Where a value lives (D8, D9): the emitter decides per allocation site whether the value stays in the block. It is built outside when the compiler sees it can outlive the task (send, a store into a shared value outside its door, a move into a Rust owner, the task’s result), and also when it cannot tell. Then the block is given back whole when the task ends.
6. Receiver budgets (D9): at recv, at a join, and at a store into a shared value, the value’s bytes move from the sender’s count to the receiver’s. A value of one allocation (a list of numbers, a text) is one step; a nested value is a walk over its allocations. A receiver it does not fit panics there, or a shared value is poisoned.
7. The Rust boundary (D8):
   • the walk that follows a value back to where it was built, so that it is built outside the block;
   • such a value crosses as a std::vec::Vec/String without a copy (into_raw_parts → from_raw_parts; allocator-api2’s Global is std’s global allocator);
   • NK2506 where the walk cannot follow the value, with the help naming the .clone();
   • a Vec/String handed back is wrapped as it is and counted;
   • the goal is few NK2506. Each case the walk does not yet follow is a gap to close, not a reason to copy.
8. The strategy (D7): std’s default derives block sizes from the memory there is and the tasks running, with the same exchange point as admission (ADR-326 D2).
9. Tests:
   • a task that reads more than its budget into a String panics, and another task runs on;
   • a supervised cache that outgrows its block is rebuilt;
   • a &[T] passed to a Rust function is not copied (pointer equality, in a test crate);
   • a list built in the package and handed to a Rust function that owns its Vec arrives at the address it was built at;
   • a pub function that hands its parameter to such a Rust function is NK2506, and compiles with .clone();
   • a long task that allocates and frees a megabyte a thousand times under a 64 KiB budget does not panic (D10);
   • a value sent from a task that has ended is still read correctly by its receiver, and counts against the receiver (D9);
   • a receiver whose budget a received value does not fit panics at recv, and the sender runs on.

Nothing in ADR-327 is left open except D10’s measurement (step 1).

Comments

keywan-ghadami, 2026-10-06

Step 2 measured: a block per task (0.0.602, 7fb1c22)

benches/taskblock/ runs one workload: 100 000 short tasks, each reading a request and writing a response, with 22 allocations and 7 reallocations per task. It is built as three binaries that differ only in their #[global_allocator]. All three print the same bytes. Counts are from callgrind with --branch-sim=yes, release build (opt-level = 3, no LTO), minus a run of no task.

allocator	instructions / task	mispredicted / task
global: the system’s malloc	17410	180.3
budget: malloc, each task’s bytes counted against 64 KiB (D5’s check without a block)	17810	197.5
block: a 64 KiB block per task, a bump pointer, emptied whole when the task ends	10188	94.8

What the numbers say:

• A block per task is cheaper than malloc: 41% fewer instructions and half the mispredicted branches. The saving is malloc’s and free’s own work, about 7 200 instructions per task.
• Counting a budget on top of malloc costs 2.3%.

Checked before quoting:

• global declares System as its global allocator. Without a declaration, std’s default shims (__rdl_*) are not inlined and add about 420 instructions per task. That is a difference of the declaration, not of the strategy.
• malloc’s count depends on where the heap starts. The same binary called by another path moves _int_malloc/_int_free by about 177 instructions per task. The script always calls the binaries the same way.

Not measured here:

• handing a block back to the system when a task ends;
• a task that needs more than one block;
• values that move from a task into a shared value.

Step 1 (fallible collections on allocator_api2/hashbrown, counted on benches/brc) is still owed. The owner’s decision (step 3) waits for both tables.

---

Generated by Claude Code

keywan-ghadami, 2026-10-06

Step 1 measured: fallible collections (0.0.603, d3a6eac)

benches/fallible/ writes two workloads twice:

• on today’s Vec, String and std’s HashMap;
• on allocator-api2’s Vec<T, A> and hashbrown’s map, with an allocator that counts every byte against a budget and refuses past it. Growth goes through try_reserve, and a refusal ends the task.

The budget is set so that nothing is refused, so what is counted is the check and the collections, not a refusal. Both sides of each workload print the same bytes. Counts are from callgrind with --branch-sim=yes, release build (opt-level = 3, no LTO), minus a run over nothing.

program	instructions	mispredicted
1BRC’s aggregation, std (per row, 200 000 rows)	393.8	3.51
1BRC’s aggregation, fallible	394.4	3.67
taskblock’s tasks, std (per task)	17872.4	181.12
taskblock’s tasks, fallible	17882.3	193.21

What the numbers say: instructions are the same within 0.2%. Mispredicted branches rise by 5% (1BRC) and 7% (tasks).

Checked before quoting:

• allocator-api2’s extend_from_slice is extend(iter().cloned()) on stable Rust, a loop of one byte at a time. Used as it is, it doubled the tasks’ count (35 136 per task). The bench copies with one copy_nonoverlapping, as std’s Vec<u8> does. A std built on the crate would have to do the same.
• The fallible text is a List<u8>, handed out as a str without checking its UTF-8 again, as String does. Checking it cost about 230 instructions per task more.

Not measured:

• the collections behind a nikaia-std feature, with an emitted program against them. The emitter writes Vec/String today, so that is a change to the emitter, not to a bench;
• a refusal and the task it ends.

Both tables are now here (step 2 in the comment above: a block per task, −41% against malloc). Step 3 is the owner’s: does the direction stand as measured?

---

Generated by Claude Code

keywan-ghadami, 2026-10-09

Step 3 Owner Decision: APPROVED (Proceed to Step 4)

Based on the measurement results from Step 1 (0.0.603) and Step 2 (0.0.602), the direction set in ADR-327 is fully confirmed:

• Step 2 (Task-Block Arena): −41% instructions and ~50% fewer mispredicted branches compared to system malloc (saving ~7,200 instructions per task).
• Step 1 (Fallible Collections): Negligible instruction overhead (~0.2%) when enforcing fallible allocation checks.

The measured gains far outweigh the checks. We are moving forward to Step 4: Implementation.

---

Consolidated Scope for Step 4 (To Build)

1. Allocation Engine

• Task-Local Allocator: User-space chained slabs. Block expansion via embedded next headers. $O(1)$ bulk free when a task ends.
• Shared-Value Allocator: Switch allocator context to the shared value’s block upon entering a SharedMut door.
• Fallible Growth: Growth implemented via try_reserve-style semantics.

2. Policy & Configuration

• Budget Exhaustion & Isolation:
  • Task block full / budget exceeded $\rightarrow$ Isolated task panic (fault isolation, other tasks run on).
  • Shared value block full $\rightarrow$ Mark shared value as poisoned.
• Pluggable TaskStrategy: API for defining initial block sizes, growth factors, and hard budget ceilings.
• Branch Optimization: Budget checks and error paths marked with #[unlikely] for cold-path separation (BTB protection).

3. Bulk Memory & Rust FFI Boundary (Zero-Copy First)

• Borrowing (&[T], &mut [T]): 100% Zero-Copy. Rust borrows directly from the task slab.
• Ownership Transfer (Vec / String):
  • Dual-Path Allocation: Values destined for Rust ownership are allocated directly via system heap wrappers (try_realloc), strictly accounted against the task’s budget, to avoid arena corruption while enabling zero-copy moves.
  • Explicit Copy: Fallback when an arena-born value must yield ownership to a Rust API.
• Slice Operations: Enforce copy_nonoverlapping for memory primitives and bypass UTF-8 checks (from_utf8_unchecked) on previously validated slices.

4. Integration Tests

• Task OOM: A task exceeding its budget panics without disturbing concurrent tasks.
• Supervised Cache: A cache outgrowing its block is cleanly rebuilt.
• FFI Pointer Equality: Assert zero-copy semantics for &[T] across the C/Rust boundary via pointer comparison tests.
• ​– Generated via Gemini 3.7-flash-preview-0926 (Google Trusted Tester Program / Internal Tier)

keywan-ghadami, 2026-10-12

Decided with the owner: D8 rewritten, D9 and D10 added; the body above is the plan now (0.0.856 52e702c, 0.0.857 6807871)

How it came up. An outside proposal on “pipeline fusion” assumed this arena was already built (it is not). Checking it against this issue showed that the step-3 comment above, written with Gemini, went beyond ADR-327 or against it in five places. The body now says what holds:

1. “O(1) bulk free when a task ends” needs every value to have left the block. ADR-327 §6 had left that open. It is now D9: a value that can outlive its task is never in the task’s block (sent, stored into a shared value outside its door, handed to Rust to own, the task’s result). So the block can be given back whole. From the hand-over such a value counts against its receiver: the task that takes it or joins its producer, or the shared value it is stored into. That was the owner’s answer to the old §6 question of whose budget it is.
2. “Dual-path allocation” for values that go to Rust became D8. The compiler follows a value handed to a Rust owner back to where it was built, builds it outside the block, and hands it over as a std Vec/String without a copy. Where it cannot follow the value, the hand-over is NK2506 and the program writes .clone(). A first version (0.0.856) let the compiler copy unseen there. The owner rejected that the same day: it breaks ADR-282 D7 (a copy is written or refused, never inserted), which is also a promise the language makes to its users. So the work goes into following values with few gaps, not into hidden copies. A Vec that Rust hands back is taken over without a copy.
3. “Pluggable TaskStrategy with hard budget ceilings”: D7 says no number is configured. A strategy with a fixed ceiling is one a package may offer, not the default.
4. #[unlikely] is not a Rust attribute. The panic path is a #[cold] function.
5. “Chained slabs” and the 41% are two different allocators. The bump block that was measured never reuses freed memory, so a long-running task would be ended for memory it no longer holds. That is now D10 (a budget counts what is held), and it is the one step measured before building, because reuse can cost some of the 41%.

Rejected on the way (ADR-327 §3):

• Nikaia’s blocks as Rust’s #[global_allocator]. A crate that keeps a Vec past its task would point into an emptied block, and a refused allocation ends the process.
• Copies the compiler inserts at the Rust boundary.

Measuring: the owner’s rule is to measure where a step can be slower than what it replaces, not to weigh a gain that can only be positive. Only D10’s allocator is measured first (To build, step 1).

Specification: Part II 12 (“A task has a memory budget”), Part III 15.2 and NK2506 in Part III’s code table say it; ADR-327 says why. The pipeline side of the same proposal is #595 (ADR-342).

---

Generated by Claude Code

Back to Open Issues