Performance#

Status: partly implemented — rounds P1 to P12 are done (P8 for the arithmetic). P11, which waited for the VM, is built as ir/counted.trb; section 5.1 is its specification and records its result. Of section 6, the allocation budget per conformance program is a tier B gate.

What a construct of TorbScript costs after lowering and -O2, which abstractions are free and which are not, and the findings that stand between the two. The goal this document is written against is docs/ARCHITECTURE.md's: fast and memory-frugal, almost on the level of a low-level language, with zero-cost abstractions wherever possible - a one-field type must vanish completely.

Everything below is measured on one machine (Windows 11, 16 cores, gcc 13.2.0 MinGW-W64 UCRT, -std=c11 -O2 -g0 -Wall -Wextra) against the compiler as it stands. Every claim carries its evidence: an excerpt of torb ir, an excerpt of the emitted C, or a number from benchmarks/. A claim with no evidence is not in this document.

the source ─► the IR ─► program.c ─┐
                                    ├─► gcc -O2, separate translation units, no LTO ─► the binary
             runtime/*.c ───────────┘

1. The performance model#

What a user can rely on, in the order the costs matter.

1.1 A value is its bytes, and a binding is a name for them#

A record whose estimated size is at most 32 bytes and that is not recursive is Inline: a C struct, passed and returned in registers, copied by assignment, never counted. type Meters { value: Float64 } is layout ... inline size 8 and a double in the C. A record over 32 bytes, or one in a cycle of the field graph, is Boxed: a pointer to a counted block, so copying it is a retain and writing through it is a copy on write.

Nesting is free. Outer { Middle { Inner { count: Int } } } is three layouts of inline size 8, and deep.middle.inner.count = 7 is the single instruction write %0.middle.inner.count.

1.2 What carries a count#

String, the runtime containers (list, map, set), a Boxed layout, a trait-typed value, a closure with an environment, a Shared object and a captured var Box. Nothing else. Counts are plain integers, not atomic (BACKEND 2.5).

A count changes at three places, and the common case of each is static inline in runtime/include/torb.h:

program.c and the runtime are separate translation units and this toolchain has no working LTO (BACKEND 6.3), so the inlining is by hand: the header holds the common case and memory.c holds the rest (torb_retain_slow, torb_release_slow, torb_make_unique_slow). Finding 13 measured what that is worth: "less than it looks" before P5 to P7, and 8 to 26% on the rows that count blocks after them.

1.3 Parameters are borrowed, and the last use is a move#

A parameter is Borrowed by default: the caller keeps the count for the whole call, so an ordinary call changes no count at all. A parameter is Owned where the callee stores the value, and at an Owned position whose operand is not live afterwards the argument is a Move and not a Copy - that is what makes list = list.added(x) change in place. Finding 1 is the one shape where the liveness says "still live" although nothing reads the value again.

1.4 Monomorphization, and the one place it stops#

A generic call whose witness is known is monomorphized: Vector2<Int> is a struct { int64_t f_x, f_y; } and a.plus(b) is a direct call. A generic call that reaches a trait-typed value is dictionary passing: one instance per bound, and every member call is a load of a function pointer out of a table plus an indirect call, which no C compiler devirtualizes because the table is read out of the value.

A collection literal was the second kind. [1, 2, 3] has the type List<Int>, and List is a trait, so the lowering writes Object(List<Int64>): a heap box holding the torb_list, plus one witness pointer. Round P5 takes that box back off again wherever the program says which container is inside it (compiler/src/ir/devirtualize.trb, finding 2): every slot and every function result a value flows between is one class, and a class whose producers are all one payload with the same static tables becomes that payload - slots, parameters, result, and every callWitness on it the direct call of the member the table named.

Dictionary passing is therefore what two implementations in one place cost, not what a collection costs. What still boxes is what the analysis may not follow: a value in a field of a record, a value a closure captures, a value narrowed to another trait, and a value two implementations meet in.

A member of a witness table used to be on that list and no longer is. Its signature may not move - the thunk casts the erased receiver to the payload and calls exactly that signature - so round P6 stopped trying to move it and copies it instead: the pass runs twice, and between the two runs every frozen function a direct call already names gets a copy under a name no table holds (specializeFrozenCallees). The table keeps the original, the direct call site gets the copy, and the second run reads the copy's result as an ordinary location. ArrayList.iterate is what that is for, and the cursor of a for over a list, a map, a set or a string is a record on the frame since (finding 5).

1.5 What is checked#

Integer overflow, division by zero and every index are checked in every profile, because they are semantics and not diagnostics. The check is __builtin_add_overflow plus a cold branch. What it costs depends entirely on what else the code is doing: in a loop whose chain is latency-bound it is free (benchmarks/arithmetic), and in a recursion whose whole body is three arithmetic operations and two calls it is 2.37x (benchmarks/call-depth).

A check that cannot fire is not emitted. Round P8 added a forward interval analysis over one function (compiler/src/ir/ranges.trb): what a slot can hold at one point, from an integer constant, from the operation that computed it, and from the comparison a Branch stands on. An Add, Subtract, Multiply or Negate whose result provably fits its own width becomes the plain C operator, which is what makes the counter of every for and every index - 1 under a guard free. Nothing about the semantics moved: unknown is the whole range of the type, so an operation the analysis does not follow keeps its check, and a division still checks its divisor because that is not a question about a width. Finding 8 has the numbers and says what is still on the table.

1.6 What a user pays for at the call site, in one table#

2. The zero-cost contract#

An abstraction is zero-cost when the program that uses it and the program that writes out what it means compile to the same machine code. Each row says holds or does not hold and names the evidence. Ratios are from section 4.

Every row that does not hold used to have one cause: a value whose concrete type the compiler knows, boxed behind a trait anyway. Round P5 removed that cause wherever the program decides the payload, round P6 removed the last of it that was a signature rather than a value, and round P7 removed the read-copy-write of an element. What the rows above are now is what is underneath all three: the Option round trip of every next and every get (a standard library question), the bounds check of an index (the half of finding 8 that is still open), and a trait-typed value in a field - which is what the stages of a pipeline are built around and what the row of a List<List<Int>> still is.

3. The findings#

Ranked by (gain x frequency) / effort. Each entry says what is generated, what it costs, where the fix goes, what it is worth, what it risks, and the test that pins it.

F1. x = f(x) is a move, because the assignment defines the slot#

Pattern. numbers = appended(numbers, index), state = state.with(key, value) - the participle style the whole language is written in.

What is generated.

b2:
  %5 = call t_..._appended(%0 owned last, %2 borrowed)
  write %0 = %5 owned last

No retain in front of the call, so makeUnique %2 inside appended finds a count of one and copies nothing.

Why it works. A Write whose reference.steps is empty defines its base, which is what definedSlot (compiler/src/ir/verify.trb) answers for it. Three things follow from that one rule and nothing else is written anywhere:

• the base is not a use, so the backward liveness walk lets the last real use of the old value be the argument of the call - and an Owned argument at a last use is a Move (compiler/src/ir/operand.trb);
• the old value is released where it dies: after the instruction that read it last, at the definition that nothing reads (var t = make() t = other), or on the edge into the block that overwrites it - all three by the rules the ownership pass already had;
• the C back end's Write stores without releasing, because the ownership pass released. A var parameter is the exception: its storage is the caller's and no slot of this frame counts what is in it, so the release stays at the store (compiler/src/backend/c/body.trb).

A panic runs nothing on the way out - no release, no drop (CONCEPT, "A panic is output") - so a call that panics between the move and the store leaves what it was handed, exactly as a panic anywhere else does.

The cost it removed. O(length) per append became amortized O(1). benchmarks/accumulate at 60 000 appends: 20 allocations and 1.05 MB copied, against 16 allocations and 1.05 MB in the C twin - the same bytes, which is what "the last use is a move" means. The retained shape paid 120 006 allocations and 20.0 GB for the same 60 000 appends.

What holds it. The extended verifier reports %n is overwritten while it still owns a value at a write whose slot was not emptied, which is the invariant in one sentence; compiler/tests/ownership.test.trb pins the IR of the loop; and reassignment.trb, participle.trb and counted.trb of the conformance suite run every shape of an overwrite with the leak gate on.

F2. A collection literal is a trait-typed value, and the program says which one#

Pattern. var x = [1, 2, 3], var m: Map<String, Int> = [:] - every collection in every program.

What was generated. The checker gives [1, 2, 3] the type List<Int>, which is a trait, so the IR type is Object(List<Int64>) and the lowering coerces the freshly built ArrayList into a box. compiler/src/ir/lower/collection.trb says so in its own module comment: "The type of a literal is a trait-typed value ... it does not name the implementation."

%1 = new List(d_Int64)
%0 = traitValue %1 owned last tables(table w_std_x2f_collections_list_List__List_Int64_Int64)
makeUnique %0
callWitness value %0 bound 0 member 3(%6 borrowed)

What is generated now. compiler/src/ir/devirtualize.trb, between lowerWorkspace and insertOwnership:

%1 = new List(d_Int64)
%0 = move %1
makeUnique %0
call n_std_x2f_collections_list_ArrayList_add__Int64(&%0 borrowed, %6 borrowed)

and numbers[index], two functions away, is call n_std_x2f_collections_list_ArrayList_get__Int64(%0 borrowed, %1 borrowed) inside an Index.at whose self is a List(Int64) - a call gcc inlines, which is what makes the bounds check and the Option visible to it at all.

How it decides. The unit is not a slot but a class of locations: every slot of every function plus the result of every function, joined wherever a value flows between two of them - an argument into a parameter, a result out of a call, a Return, a Read or a Write of the whole slot. A class loses its box when every producer is a TraitValue of the same payload with the same static tables and nothing in it is poisoned. Then the slots, the parameters and the result take the payload's type, the TraitValue becomes a Copy - a Move at its last use - and every CallWitness on it becomes the direct Call of the member the table named, with the receiver as the first argument and as a place where the member takes var self.

Everything the analysis cannot follow poisons what stands in it: a value built into a record, captured by a closure, narrowed to another trait, handed to an erased ABI (a CallClosure, or any argument of a CallWitness), read out of a path, or taken out of a container. So does every parameter and result of a function that something other than a Call of the program reaches - a member of a witness table above all, whose thunk casts the erased receiver to the payload and calls exactly that signature, and with it a function a Closure points at, a function of the runtime, a helper of an element descriptor and the accessor of a module const. Two implementations that meet in one place poison it too, which is the case dictionary passing exists for.

The annotation is not what decides it. const items: List<Int> = [1, 2, 3] loses its box like every other literal: what the analysis follows is where a value goes, not how a binding was written. benchmarks/list-index writes var numbers: List<Int> = [], hands it out of filled() as List<Int> and indexes it in total(numbers: List<Int>), and all five positions - the local, the result, the temporary, the parameter, and the self of the Index.at instance - are one class holding one torb_list.

Nothing about the language changed. The checker is untouched, the type of a literal is still the trait, and the diagnostics, Show and every message say what they said. Two things in the output moved: the IR text, and one line of the C back end - a witness table is emitted with external linkage now, because a table the devirtualization made unreachable would otherwise be a static const that nothing reads, which is an error under -Wunused-const-variable -Werror. The runtime gained torb_map_make_unique and torb_set_make_unique beside torb_list_make_unique, because a var path through a concrete map needs the same one-line call a list already had.

What it costs and what it bought. Section 4 has the table. The shape of it: list-index -31% (399 ms to 275 ms) and record-write -31% (1.25 s to 0.87 s) with the same allocation counts, because what went away is the dispatch and not a block; map-count -20%, pipeline -13% and list-iterate -12%. pipeline also loses one of its five allocations per pipeline (125 to 105 for 20 pipelines), because the Filtered stage is a record now instead of a box. The compiler's own program.c is 274 875 bytes smaller for the same sources (63 265 243 against 62 990 368), which is what the direct calls and the boxes that are not built save; the three-line list program of finding 12 goes from 25 696 to 25 102 bytes and keeps all 24 of its witness thunks, because a table that nothing reaches is still emitted. That was finding 12, the biggest single item left in the C of a small program, and round P10 took it.

The risk. A class that is peeled although something still needs the box is a wrong program. Three things hold it: the analysis poisons by construction (a position it does not recognize is poisoned, never ignored), every question the IR verifier would ask about the direct call is asked before the rewrite - the member has to be a plain function of the program with no witness parameters, the receiver exactly the payload, every argument the type its parameter declares, the result what the slot at the call site holds - and a class that fails any of them is poisoned instead of half rewritten.

What is left on the table. A class is all or nothing: one use that has to be a box keeps the box for every other use of the same value. Boxing at that use instead - inserting a TraitValue in front of the one argument, the one field or the one return that needs it - would cover rows.add cells in benchmarks/nested-write, where the inner list is peeled everywhere except where it goes into the outer one. It costs one allocation at the point of escape and nothing anywhere else, so it is worth measuring rather than assuming; it is the first thing to try if a later round wants more of this finding.

The test. compiler/tests/devirtualize.test.trb pins both halves: a value written as the trait and used in its own frame is the payload, a result and a parameter of the trait become the payload together, a var fn member is the ordinary var path of a concrete value - and, on the other side, a value built into a record keeps its box, two implementations in one parameter keep the dispatch, and a member of a witness table keeps the signature its thunk calls. compiler/tests/lower-collections.test.trb pins the loop whose cursor is concrete, and the conformance suite runs all 84 programs with the leak gate on.

F3. A nested index write goes into the grid's own storage#

Pattern. grid[row][column] = value, world.entities[id].health = 1, rows[i].add(x).

What was generated. The outer list was concrete after round P5 and its set a direct call; the row is an element of a container and therefore a value the frame had a count of, so the MakeUnique in the middle copied it.

%10 = read %0
%11 = call t_std_..._Index_at__...(%10 borrowed last, %4 borrowed)   # the row - retains it
release %10
...
makeUnique %11                                                # count is 2, so this COPIES the row
callWitness value %11 bound 0 member 8(%7 borrowed, %15 borrowed)
makeUnique %0
call n_std_x2f_collections_list_ArrayList_set__...(&%0 borrowed, %4 borrowed, %11 owned last)

What is generated now. compiler/src/ir/elements.trb, a peephole after devirtualizeProgram:

makeUnique %0
makeUnique %0[%4]
callWitness value %0[%4] bound 0 member 8(%7 borrowed, %13 borrowed)

Nothing is taken out and nothing is put back. %0[%4] is a PathStep.Element into the grid's own storage, so the makeUnique on it finds a count of one - the grid is the only owner of the row - and copies nothing.

How it decides. The round trip the lowering writes is a Read of the container, Index.at into a slot of the frame, the access, and MutableIndex.set back. The pass looks for exactly that quadruple inside one block and rewrites it only when all of this holds: the put-back is the runtime's own torb_list_set (through the wrapper that every native fn of std/ reaches it by), the take-out is a member the lowering recorded as an index read (IrProgram.elementReaders, by symbol, so a copy specializeFrozenCallees made is the same member), the container is a Runtime(ListStorage, Item), the element has no owner but the container, every use of the element in between is a place and not a value read, and nothing in between touches the container or the key. Everything that cannot be proved is proved false, and what the pass refuses keeps the copy it always had.

It is not a change of the lowering, which is what the P6/P8 round wrote down here: takenElement runs while the container is still Object(List<Int>), and the devirtualization is two passes later. One thing in the lowering did move: the value of an assignment is lowered before the path is formed, because a take-out is part of the access and BACKEND 2.3 says an access begins once everything the assignment needs has been evaluated - the keys first, in source order, then the value, then the access. Without it grid[row][column] = failing() would reach failing() at two different moments depending on whether the write went through the taken-out element or through the step.

The panic is the language's. a[index] out of range panics index 9 is out of bounds for a length of 3, because that is what the at of ArrayList and of Array says. So PathStep.Element carries a LocationId, which the pass reads out of the body the call would have run - the site of the one panic of at - and torb_list_element_address panics with the index and the length there. A reader whose body does not have that one panic is not rewritten at all.

The cost it removed. benchmarks/nested-write writes 3 840 000 cells of an 800 x 800 grid. It paid 7 688 813 allocations and 31.7 GB copied for it, against 803 allocations and 5.1 MB in C. Section 4 has what it pays now: 8 813 allocations, every one of them the construction of the grid, and 64% of the time gone.

What is left. The row of a List<List<Int>> is still an Object box, because it goes into the outer list and the devirtualization poisons a value that is built into a container. So a write is one makeUnique of that box at the element's address and one witness call through it - no copy and no allocation, and one indirect call. Boxing at the use instead of at the class (finding 2, "what is left on the table") is what would take the rest.

The risk. An interior pointer is valid only while no other write to the container can happen, which is what exclusivity guarantees (BACKEND 2.3); the pass asks the IR the same question once more over the window it rewrites.

The test. compiler/tests/elements.test.trb pins both halves: the shapes that lose the round trip, and a container two implementations meet in, which keeps it. tests/conformance/nested-write.trb runs every shape of the write with the leak gate on and proves copy on write - a copy taken before a write still reads what it read - and tests/conformance/element-place-panic.trb pins that a write out of range says what a read says.

F4. A field of a record in a list is one store through the list#

Pattern. points[index].y = value - how every entity-component loop is written.

What was generated. Index.at into a temporary, write %8.y, then MutableIndex.set back - both of them a direct call since round P5, and still a round trip that copies the record in each direction:

%8 = call t_std_..._Index_at__...(%7 borrowed last, %4 borrowed)
write %8.y = %12 borrowed
makeUnique %0
call n_std_x2f_collections_list_ArrayList_set__...(&%0 borrowed, %4 borrowed, %8 borrowed)

What is generated now. The same Element step as finding 3, and the record never moves:

%7 = call t_std_..._Index_at__...(%0 borrowed, %4 borrowed)
%8 = read %7.x
%9 = constant s_literal__Int64_1
%10 = intrinsic add.i64 %8, %9
makeUnique %0
write %0[%4].y = %10 borrowed

The makeUnique %0 is the ordinary one the ownership pass inserts for every counted owner on the path of a write; the element itself is an inline record and carries no count, so there is nothing else to make unique.

The cost it removed. benchmarks/record-write writes 30 000 000 fields: 958 398 microseconds to 394 118, a 59% cut, with the same 23 allocations - what went away is not a block but the read, the copy and the second bounds-checked call per write. Against its C twin it is 12.61x, where it was 28.71x before the round and 75.60x before round P5.

What is left. The read on the right-hand side (made[index].x) is still Index.at, which is a call, a bounds check and a copy of the whole record for one field. That is the read half, and it is the open half of finding 8 plus the Option of get - not this finding.

The risk. As finding 3.

The test. As finding 3, with benchmarks/record-write as the budget.

F5. for over a collection: the cursor is a record on the frame#

Pattern. Every for over anything that is not a range - the most written construct in the language.

What was generated.

%3 = callWitness value %0 bound 0 member 5()     # iterate(): an Object(Iterator<T>) on the heap
b1:
  makeUnique %3                                  # every turn
  %5 = callWitness value %3 bound 0 member 0()   # next(): an indirect call answering an Option
  %6 = tag %5
  switch %6 case 0 b2, otherwise b4

Round P5 had already removed all of that for an Iterate nothing boxes, and the containers of std/ were the case that was left: ArrayList.iterate is a member of the Iterate table, a table member's signature may not move, and so the member answered the boxed Iterator<Item> however concrete its receiver was.

What is generated now.

%2 = call t_std_x2f_collections_list_ArrayList_iterator__Int64_x24_direct(%0 owned last)
b1:
  %4 = call t_std_x2f_collections_list_ListIterator_next__Int64(&%2 borrowed)
  %5 = tag %4
  switch %5 case 0 b2, otherwise b4

with slot %2 local iterator: Record(T_std_x2f_collections_list_ListIterator__Int64).

How it decides. Not by moving the frozen signature but by copying the member. devirtualizeProgram runs the whole analysis twice, and between the two runs specializeFrozenCallees copies every frozen function that a direct call already names and whose signature holds an Object at all, under a name no table holds (..._x24_direct, where _x24_ is how the mangler writes a $ and no source name can produce one). The direct call sites are pointed at the copy; the table keeps the original, so the erased ABI is untouched and a program that really dispatches pays exactly what it paid. The second run then reads the copy's result and its parameters as ordinary locations, and the class of the cursor has one producer - the TraitValue of ListIterator<Item> inside the copy - so it loses its box like any other.

A copy is only made for a callee that is called, which is what keeps it from being dead code: eleven copies in the two-file program of compiler/tests/lower.test.trb.

What it costs in code size. When the round landed, the compiler's own program held 1 021 copies and was 1 682 633 bytes of C larger for them - 2.6% of 64 MB, and the whole of what this round's code generation added - and 334 of the 1 021 gained nothing: their signature came out of the second run exactly as it went in, because the class they are in was poisoned for some other reason. Those copies are dropped again now (dropIdleCopies, the second ledger of finding 12): the copies are appended after every other function and nothing but a Call this pass wrote ever points at one, so taking them back is a remap of a contiguous tail of FunctionIds over the Call instructions and specializedFunctions, and nothing else. On main 6f9d340b the stage-2 program.c held 200 copies (184 _x24_direct and 16 _x24_direct_x24_site) in 236 791 bytes; 42 of them were idle, and the program keeps 158 in 176 636 bytes. Finding 12 has the whole ledger.

What it covers. A list, a map, a set, a String's chars() and every user Iterate. Iterate.filter is a table member too, so a stage of a pipeline is answered as a Record(Filtered) now rather than a box.

Level 3 turned out to be unnecessary. The plan was a dominator walk that hoists a makeUnique out of a loop head. There is nothing left to hoist: a concrete cursor is an inline record, and dropUncountedMakeUnique removes the makeUnique of a place that carries no count at all. A loop head holds one only where the cursor is still a box, which is where the dispatch is real.

The cost it removed. One allocation per loop, one makeUnique and one indirect call per turn. benchmarks/list-iterate allocates 24 blocks for 40 loops where it allocated 64 - the same 24 benchmarks/list-index allocates for the same data - and benchmarks/pipeline 85 where it allocated 105.

What was left. The Option per turn and the cross-unit torb_list_get, neither of which gcc can see through, so list-iterate was still 44x against a pointer walk that vectorizes. Round P11 (a for over a concrete list as a counted loop over Element steps, specified and measured in 5.1) took both out for the flat lists; the standard library question of an Iterator that answers "is there one" and "the value" separately stays open for every other iterator.

The test. compiler/tests/devirtualize.test.trb pins all three halves: the cursor of a for whose iterable is concrete is a record on the frame although a table names the member, the member the table names keeps the box it promised, and a loop over a value that two implementations meet in keeps its dispatch, its box and its makeUnique.

F6. An interpolation is one allocation, because a part may still be a number#

Pattern. "{a} and {b}", and print of anything that is not already a string.

What is generated.

%5 = constant s_literal__String_row_x20_
%6 = constant s_literal__String__x3a__x20_
%8 = intrinsic remainder.i64 %1, %7
%4 = intrinsic textConcat %5, %1, %6, %8

const torb_text_part parts[4] = { { .kind = TORB_PART_TEXT, .text = s5 },
                                  { .kind = TORB_PART_SIGNED, .signed_value = s1_index },
                                  { .kind = TORB_PART_TEXT, .text = s6 },
                                  { .kind = TORB_PART_SIGNED, .signed_value = s8 } };
s4_line = torb_text_concat_parts(parts, 4);

No Show.show at all: torb_text_concat_parts measures the parts, allocates the result once and writes each part into it with the same formatter its torb_show_* uses.

Which parts. Exactly the types the prelude declares native, which textPartKindOf (compiler/src/ir/layout.trb) answers for: every integer width, every float width, Bool, Char, Void, and String, whose Show is the identity. A second implementation of a trait for a type is an error, so no program can give one of them a show of its own. A value with a Show the program has to call - a record, a case, a tuple, a trait-typed value - is a text before the concatenation reads it, exactly as it was.

The cost it removed. benchmarks/interpolation: 2 000 003 allocations for 2 000 000 interpolations, against 2 in C, where the shown shape paid 6 000 004. One allocation per interpolation is the String it answers, which a language with value semantics cannot do without - the C twin writes into a stack buffer and keeps nothing. The same fix halves a program that only builds keys: benchmarks/map-count allocates 50 110 blocks against 100 111.

What holds it. interpolation.trb and floats.trb of the conformance suite compare every shown form against stage 0 byte for byte, which is what holds the format rather than the type list; runtime/tests/text_test.c compares each part kind against the matching torb_show_*; and compiler/tests/lower-text.test.trb pins the IR and the C.

print is the shape beside it and keeps its texts: the join with one space and one \n is the runtime's, and the parts of a variadic call are not the parts of one text. print "{a} {b}" pays one allocation, because the interpolation inside it is the one text.

F7. A closure the callee cannot keep has its environment on the frame#

Pattern. A closure written straight as the argument of a call that only calls it: applied(1, { _ * factor }), and every receiver closure and DSL block.

What is generated.

T_environment__t_closure__..._scaled_0 s1_environment = { 0 };
...
torb_environment_on_frame((torb_environment *)&s1_environment, NULL);
s1_environment.f_factor = s0_factor;
s1.code = (void (*)(void))F_t_closure__..._scaled_0;
s1.environment = (torb_environment *)&s1_environment;
s2 = t_..._applied(s1);
torb_environment_release(s1.environment);

The environment is a local of the frame, declared beside the slots so no goto crosses an initialization. It is a whole environment in every other way: torb_environment_on_frame writes count one, the drop of its layout and the block kind TORB_BLOCK_FRAME_ENVIRONMENT, which torb_environment_release answers by running out the count and running the drop without a free. So every capture is released exactly once, and nothing is allocated.

Which closures. Two answers have to agree, and BACKEND's decision 14 names both: "conservatively, when it is written directly as an argument of a call and is not stored by the callee".

• The checker says local, which is the first half: the closure stands straight as a call argument (compiler/src/ir/lower/closure.trb).
• The IR says the callee does not keep it, which is the second: the slot the Closure wrote is used only as an argument of a call no callee of which may keep that parameter, as the callee of a CallClosure, or by the Release this frame emitted (framedClosures in compiler/src/backend/c/body.trb).

"May keep" is a summary of its own (compiler/src/ir/kept.trb) and not the ownership summary. A parameter can be borrowed and still be kept: an argument of a witness call or of a closure call is borrowed whatever the member at the other end does with it (compiler/src/ir/operand.trb), so a callee whose body is actions.add action on a trait-typed List stores the closure behind a borrowed parameter. The summary is a least fixpoint over the call graph: a parameter is kept when it reaches a store, a Construct, a capture, a Copy, a Return, a place, an argument of a CallClosure, or a parameter of a callee that keeps it. A witness call asks every member it can reach - the member at its index in every table of the value's trait, which is the whole set because the program is closed - so names.contains(name) on a List<String> keeps its frame environment: no find of a List table keeps its predicate. A witness whose tables cannot be named keeps every argument. Everything that cannot be proved is proved false.

Iterate.map is the case that shows why the second half is needed: the closure is local, and map builds it into a Mapped record it answers, which the frame may answer on. Its parameter is Owned, so the environment is a block.

The gain. One allocation per closure creation, and the environment's fields become locals that gcc can keep in registers. It does not show in benchmarks/closure, where the closure is made once outside the loop; it shows wherever a closure is made inside one.

What holds it. closure-frame.trb of the conformance suite makes a closure with a counted capture inside a loop, two at once, and one the callee keeps and calls after the call has ended, with the leak gate on; closure-kept-by-callee.trb has callees that keep it through a trait-typed List, a closure call, a bound and a trait-typed value; compiler/tests/lower-closures.test.trb pins both halves of the C; runtime/tests/memory_test.c pins that a frame environment costs no block and still drops its captures.

F8. An overflow check that cannot fire is not emitted#

Pattern. Arithmetic on a value whose range the surrounding code already decided - index - 1 under if index < 2 { return index }, and every loop counter.

The cost it removed. It depends on what else is going on, and the spread is the finding. A C twin of benchmarks/call-depth, the same recursion three ways on the same machine:

So the checks were 1.8x here, and the two that cannot fire are now the two the middle row leaves out. The wall time barely moved for it: the same recursion is 378 ms without the change and 371 ms with it, fastest of fifteen runs each, which is inside this machine's own band for that program. The reason is in the generated C - torb_subtract_i64 is a static inline of torb_number.h and its __builtin_sub_overflow stands under if (s0_index < 2) return ..., so gcc's own value range propagation was already folding those two branches away. What the round changes is therefore not what gcc emits here but what the IR says, and that is where it will be read: the VM has no value range propagation to fold anything with, and neither has a C compiler without the overflow builtins (the #else arm of BACKEND 3.3 is four operations and a shift per addition).

What is generated.

b2: # torbscript/benchmarks/call-depth.trb:10 join
  %4 = constant s_literal__Int64_1
  %5 = intrinsic subtract.i64.unchecked %0, %4 at torbscript/benchmarks/call-depth.trb:13:13
  %6 = call t_..._fibonacci(%5 borrowed)
  %7 = constant s_literal__Int64_2
  %8 = intrinsic subtract.i64.unchecked %0, %7 at torbscript/benchmarks/call-depth.trb:13:36
  %9 = call t_..._fibonacci(%8 borrowed)
  %10 = intrinsic add.i64 %6, %9 at torbscript/benchmarks/call-depth.trb:13:3

The addition of the two results keeps its check, because nothing bounds what a call answers - and it is the one that can really overflow.

How it decides. compiler/src/ir/ranges.trb, a forward interval analysis per function, between the devirtualization and the ownership pass. One Interval per slot, and three sources of facts and no others: an integer Constant, the arithmetic that computed a slot, and the comparison a Branch stands on, which narrows both of its operands in the two successors. The fixpoint is reverse postorder with widening at the head of a loop - and only over the slots that loop writes, because widening the rest would take the bounds of an outer _round away inside an inner loop - followed by a narrowing pass that reads the same equations once more from the settled answer.

Unknown is the whole range of the type, never "no fact". A slot the analysis does not follow holds anything its width allows; every instruction resets what it may define before it says anything, including every slot a callee may write through a var argument; the bounds are exact Int64 arithmetic, so an operation whose result interval cannot even be written down keeps its check. That is what makes a wrong answer impossible rather than unlikely.

What it covers. The increment of every for index in 0..n, including a nested one and the counter around it; index - 1 and index - 2 under a guard; arithmetic on values the function knows exactly. What it does not: sum = sum + value, a field read, a call result, and UInt64, whose upper bound does not fit the Int64 the intervals are computed in.

The bounds check of a list is the other half this finding promised, and ir/bounds.trb removes it where a loop proves the index: for index in 0..list.length() over a list the body does not change reads list[index] as one Element step with checked off - torb_list_item in C, no comparison, no copy of a shared storage - instead of the call of the at of ArrayList and its Option. The proof is a forward analysis of two facts, index >= 0 and index < length (read off the guard of the loop, where length is the one length() read of a list that is written nowhere else in the function); anything it cannot prove keeps the call and its panic. The VM keeps its comparison (ListItemAddress) and drops only the copy. tests/conformance/list-bounds-proven.trb holds both sides.

The risk. A wrong range is a missing panic, which is an observable difference between the two back ends. tests/conformance/range-checks.trb is the program that holds it: a guarded subtraction and a loop counter that the analysis does drop, with their answers pinned, and an addition nothing bounds that still panics with arithmetic overflow in `+` at its own line. overflow.trb, negate-overflow.trb and division-by-zero.trb are unchanged and still green.

The test. compiler/tests/ranges.test.trb pins both halves - the dropped check and the kept one, the guard that bounds one end and not the other, and a division, which keeps its check because a divisor is not a width - and compiler/tests/lower.test.trb pins the counted loop with add.i64.unchecked in its step block.

F9. A pipeline builds one box per stage and one per stage's iterator#

Pattern. list.map { }.filter { }.sum().

What is generated.

%1 = closure t_closure__..._0 captures() local
%2 = call t_std_..._Iterate_map__...(%0 owned last, %1 owned last)     # a Mapped record, boxed
%3 = closure t_closure__..._1 captures() local
%4 = callWitness value %2 bound 0 member 1(%3 borrowed last)            # a Filtered record, boxed
%5 = call t_std_..._Iterate_sum__...(%4 borrowed last)

and driving it allocates a FilteredIterator, a MappedIterator and a ListIterator, each boxed.

The cost. benchmarks/pipeline allocates 85 blocks for 20 pipelines against 25 for the same data read once: three allocations per pipeline after round P5 made the Filtered stage a record instead of a box and round P6 made the outermost cursor one, and per element two indirect calls and three Option round trips. The ratio against the fused loop is 21.77x.

Why the three that are left. Iterate.map and Iterate.filter are reached with Self bound to the trait type, so their one instance builds a Mapped/Filtered record around a trait-typed self - a value in a field, which the devirtualization may not follow, and the source of a stage's iterator is a field of the same shape. So the stage that is answered to the caller is peeled, and what sits inside it is not.

The fix. Not finding 5 any more, which is done: what is left is the one place the devirtualization may not go at all. Boxing at the use instead of at the class - a TraitValue inserted in front of the one field that needs it, which finding 2 names as the first thing to try - is what would reach it, and it is the same rewrite rows.add cells in benchmarks/nested-write wants. What stays even then is the Option per stage per element, which an Iterator that answers "is there one" and "the value" separately would remove - a standard library question and not a back end one.

The gain. From about twenty times a hand-written loop to whatever the Option round trip leaves.

The risk. None beyond finding 2.

The test. benchmarks/pipeline as a budget, and its allocation column, which is exact.

F10. A map read-modify-write is two probes, and a write through map[key] is four#

Pattern. const seen = counts.get(word) ?? 0 then counts.set word, seen + 1 - the word counter every program has. And byName[key].count = 5, which round P7 left here on purpose: an Element step reaches the contiguous list and nothing else, so a write through a map is still the take-out and the put-back of two members, with the value copied in each direction. The interior pointer a map needs is torb_map_slot, and that is this round.

What is generated. The map is a concrete Map(Key, Value) since round P5 and both probes are direct calls of the runtime's own functions, so what is left is that there are two of them:

%11 = call n_std_x2f_collections_map_TrieMap_get__String_Int64(%1 borrowed, %7 borrowed)
...
makeUnique %1
call n_std_x2f_collections_map_TrieMap_set__String_Int64(&%1 borrowed, %7 borrowed, %14 borrowed)

The cost. benchmarks/map-count is 6.39x against one probe of an open addressing table, and allocates 50 108 blocks against 50 004. Round P5 took 20% of its time off - both probes are direct calls of torb_map_get and torb_map_set now - and what is left is that there are two probes and two hashes.

The fix. Instruction.TakeOut / PutBack with RuntimeKind.Map - the two instructions exist in the IR for exactly this and are reached by nothing - plus a torb_map_slot in runtime/map.c that answers an interior pointer valid until the next write to the table. The receiver is concrete now, which is what the instructions needed. For the read-modify-write, a Map member that reaches the same mechanism (getOrInsert, or update(key) { }), so that a user who writes the two-step form keeps it and a user who writes the one-step form gets one probe.

What round P7 leaves for it. The shape is written down now: ir/elements.trb recognizes the take-out and the put-back of an index path and replaces them with a place, and it refuses a map because a key is not an index and PathStep.Element steps into contiguous storage. A map wants its own step or the two instructions, and the pass that finds the round trip is the same walk either way.

The gain. Half the probes of a map-heavy program, and the copy of the value in each direction.

The risk. An interior pointer into a table that rehashes is the classic bug; the pointer may not survive a write, and exclusivity is what says no write can happen in between.

The test. An IR snapshot showing one takeOut and one putBack instead of two callWitness, and benchmarks/map-count as a budget.

What round P9 built. ir/maps.trb, right after ir/elements.trb: where the container is the runtime's own table (RuntimeKind.MapStorage) and a whole slot, the take-out through Index.at, the change and the torb_map_set of map[key].field = value are one TakeOut and one PutBack. torb_map_slot(map, key) makes the table unique, probes once and answers the address of the value's slot, valid until the next write to the table, or NULL. The value is moved into the frame at the take-out and stored through the same address at the put-back, so a counted value is not copied: after a copy on write the table's block holds a count of two and the first makeUnique of the value copies it once, which the put-back stores. A missing key is the Index.at the round trip began with, called where the probe finds nothing (MapMiss), so the message and the site are the ones of the unrewritten program; the conformance suite pins it (map-take-out-missing), next to the nested path and a counted value (map-take-out). The C back end keeps the address in a void * local, the VM in a register behind the kernel operation map.slot.

What it refuses, and why that is the exclusivity rule's. A container that is a field (holder.points[key].y = v) or a box keeps its round trip: the call of at for a missing key needs the map as a value. So does an access in which anything else names the map between the two instructions, because a read keeps a copy that the change in place would reach. The write that would rehash the table while the address is held can only come from a closure of a var call on the value, which is a write to a path the call is changing, and exclusivity.test.trb pins that it is rejected; a closure that captures a var parameter is not supported by the native back end at all, and a captured local is a box.

Measured. tools/map-cost.sh at the end of tier B (CI run 1397 of the head, the linux-x64 runner, gcc 13.3.0 -O2, the fastest of nine runs, microseconds net of the floor of nothing.trb), the compiler of the merge base against the compiler of the branch on the same machine in the same job:

The path write is about 1 % faster, map-count about 1 %: both inside what two runs of the same compiler differ by on a shared runner, and the allocations do not change, as the take-out saves a probe and not a block. So the second probe was not where the time of map-write goes (6.0 times the C program before, 6.1 after); what the pass buys is the single probe and the same message and site for a missing key, and the number to move is the next round's.

F11. A static value is never counted, so a literal costs no call#

Pattern. numbers[index], and every expect and panic whose message is a literal.

What is generated.

%2 = callWitness value %0 bound 0 member 9(%1 borrowed)
%3 = constant s_literal__String_Key_x20_does_x20_not_x20_exist
%4 = call t_std_x2f_core_option_Option_expect__Int64(%2 borrowed, %3 borrowed)
return %4 borrowed

No retain and no release of %3.

Why. A slot whose every definition is a Constant holds a static value of the program, and a static is emitted with TORB_IMMORTAL_HEADER: its count is the sentinel that torb_retain, torb_release and torb_make_unique all answer with "never counted, never freed". Such a slot is left out of the counted set (immortalSlotsOf in compiler/src/ir/liveness.trb), so liveness has nothing to say about it, the edges carry no release of it, and the extended verifier asks nothing about a value that nothing owns. A position that keeps it still says owned, because that is the contract of the position; it just needs no retain to satisfy it.

Three exclusions make it exact: a parameter holds whatever the caller handed over; a slot a write, a MakeUnique, a TakeOut, a PutBack or a var argument reaches stops being the static, because making an immortal value unique copies it and the copy is an ordinary counted block; and a slot some other instruction defines on another path holds that value there.

The cost it removed. One cross-unit call per list index read, per map index read and per expect anywhere - a call whose body is a comparison and a return, which gcc cannot see through because program.c and the runtime are separate translation units with no working LTO (finding 13).

What holds it. compiler/tests/ownership.test.trb pins a body where a static and a value the frame really owns stand side by side, and the extended verifier would report a leak if a slot that does own something were left out.

F12. A witness table instantiates every member, called or not#

Status: done, round P10.

Pattern. Every trait-typed value. Since round P5 a collection literal is not one any more, and the tables were emitted anyway - which made this the biggest single item left in the C of a small program.

What was generated. w_std_..._List__List_Int64_Int64 holds a slot for every member of List, among them filter, toList, forEach, count, insert, removeAt, reverse and compact. A program that only calls append and length got an instance and a thunk for all of them, because the table had to be filled.

What is generated now. A slot no CallWitness of the program can reach holds no function: the C back end writes NULL for it and a NULL members array for a table with no live slot at all, the bytecode writes -1, and torb ir prints -. The member behind such a slot is not emitted unless something else still calls it.

How. compiler/src/ir/called-members.trb computes, after dropListBoundsChecks and before trackCallerSites, a least fixpoint over what the program keeps: the keep set of the C back end (keptFunctions, whose roots and edges it shares), with every live CallWitness as an edge to the slot at its index in every table its witness source can name (reachableTables of ir/kept.trb), and to the member in that slot. A slot that only a dead member calls through is dead as well, in the same run. It is asked per table and per slot, not per trait and member index: a slot of a table the program keeps for one call is not a slot of every other table of the trait.

It only runs where the program is closed - lowerWorkspace, with no hosted function, no loadScript and every witness source nameable - because a REPL part, a loaded script and a script host call through tables that the program cannot see. There every slot stays filled, as before.

What was measured. Before is main at a183078a, after is the round; both are the CI artifacts of the commit.

The baseline had moved since this finding was written: the list program was 25 102 bytes with 24 thunks after round P5, and 39 904 with 16 when the round started. The bootstrap times are one run each on a shared runner and read as a direction, not a figure. The bytecode row compiles this round's sources with both compilers, so it is the pass alone and not the pass plus its own source. Every table is still emitted - a table the program builds is a value that has to exist - so what went is the thunks and the members, not the tables.

What holds it.

• The IR verifier: deadSlotProblems holds every program to the same fixpoint - no witness call of a function the program keeps lands on an empty slot, and none whose tables cannot be named stands in a program that has one - and a trait-typed value now has to carry, at each bound, a table that implements that bound.
• compiler/tests/witness-dead.test.trb: which slots stay (a call through a narrowed value, a supertrait member called on a subtrait value, a member only a dead member calls), which go, the programs it leaves alone, and the verifier rejecting a call onto an empty slot.
• compiler/tests/emit-c.test.trb, "The size of a small program": the list program has no thunk and stays under a budget of its measured size plus 2%. It is compiled against the test prelude there, so its numbers (2 thunks before, none after, 7 086 bytes) are not the ones in the table above.

A second ledger belongs to the same round, and it is done. Round P6 copies a frozen member for the direct call sites that can peel it, and when it landed 334 of the 1 021 copies in the compiler's own program gained nothing - 0.5 MB of C for a signature that came out of the second run exactly as it went in. dropIdleCopies now takes such a copy back right after the second run: a copy is idle when every parameter and the result have the type of the original's, its calls name the original again, the copies after it move down, and the verifier catches an id that was left behind. It is a remap of a contiguous tail of FunctionIds and not a new analysis (finding 5). Measured on the stage-2 C of the compiler itself, main 6f9d340b against the same sources with the drop, one CI bootstrap each:

The ledger on main was far smaller than the one on record: 42 idle copies, not 334, holding 60 155 bytes of definitions and 11 755 bytes of prototypes. The pass itself is 28 305 bytes of the compiler's C, so program.c is 43 605 bytes smaller. The 16 _x24_direct_x24_site copies all collapse into _x24_site copies of their originals that the program already had; no name is new. The build time did not move: 0.04% of the C is below the noise of one run on a shared runner, so the 87 s of gcc on record below is still the number to beat. The run-time check is the first nightly benchmarks.yml table after the merge; the copies that were dropped had the original's signature, so the calls are the same calls.

F13. Reference counts across units: the fast path is inline, and on the code P5 to P7 leave behind it pays#

Pattern. Every counted value, everywhere. torb_retain, torb_release and torb_make_unique were calls into runtime/memory.c, and BACKEND 6.3 measured that -flto does not work with this toolchain at all ("the assembler refuses the object, too many sections").

The first measurement (before P5 to P7): a copy of runtime/ whose three fast paths are static inline in torb.h, linked against the same program.c the suite built, fastest of five runs each:

The finding was the spread: up to 14% faster and up to 9% slower, depending on whether the extra code in the hot loop was worth the call it saved, with the indirect calls and the copies (findings 2 to 5) in the way. It stayed "a measurement to redo once findings 2 to 5 have removed them", which is round P12.

The measurement redone (round P12, on a main that has P5 to P7 and the VM). One job of the forge CI, one runner (Linux 6.8, AMD EPYC Genoa, 16 processors, gcc 13.3.0, -std=c11 -O2 -g0 -Wall -Wextra), four builds of the runtime side by side, benchmarks/run.sh --allocations with nine runs each, twice, in the order A B C D and then D C B A so a slow moment of the machine does not fall on one variant; a row is the fastest of the eighteen runs, microseconds net of the process floor (binary-trees of the Benchmarks Game at depth 17 is the whole run, nine rounds with the variants taking turns). The variants are header-only over main's memory.c, and the inline code holds only the common case:

• A as it was: three calls.
• B torb_retain inline: a block that is not NULL, not immortal and not shared is one increment.
• C B and the unique test of torb_make_unique: NULL or a count of one, shared bit aside.
• D C and torb_release: a count above one that is not shared is one decrement.

Every other case calls torb_retain_slow, torb_release_slow or torb_make_unique_slow: the panic on a zero count, the immortal rule, the atomic path while the pool runs threads, the last count (drop, free and the bound on how deep drops nest) and the copy.

The allocation column of run.sh --allocations is the same in all four variants for every row, as it must be: the change moves no allocation.

The rule, set before the numbers (issue #59): a variant lands if it is at least 5% faster on at least two of the named rows (list-iterate, pipeline, record-write, list-index, map-count, binary-trees), no named row is more than 3% slower, and both back ends pass the conformance suite.

The verdict: D lands. The three fast paths are static inline in torb.h, the rest is out of line in memory.c under the names torb_retain_slow, torb_release_slow and torb_make_unique_slow; the VM's kernel keeps calling torb_retain, torb_release and torb_make_unique, which are now the inline functions, and reaches the same slow paths. The step from C to D is the largest on the rows that release the most (list-iterate -14% to -26%, chain-walk -25% to -51%, bankers-queue -12% to -24%): a release is the call that stays when only the retain and the unique test are inline. The two named rows that did not gain, list-index (+2.4%) and record-write (+1.9%), are inside the band of the rows that hold no counted block (arithmetic, call-depth, closure, wrapper), which moved by -0.1% to +2.0% for the same builds.

What it costs: code size. The -O2 object of the program.c of list-iterate is 1 378 bytes of text in all four variants (+0), of pipeline 3 937 bytes in A and 4 677 in D (+740, +19%), of record-write, list-index and map-count the same in all four. The text of the runtime's -O2 objects, summed, is 440 971 bytes in A and 443 539 in D (+2 568, +0.6%); of that task.c is +1 544, text.c +328, list.c +248, decimal.c +160, machine.c +128 (the kernel of the VM), map.c +112 and memory.c +48.

-flto. Not tried in this round and not part of it (BACKEND 6.3 still stands).

F14. A module const of a collection is rebuilt where it is read#

Already found, already fixed, and recorded here because it is the shape that keeps coming back. BACKEND 6.3 measured punctuationTable in the lexer at 1.43 microseconds per read against 0.83 for the walk alone before the value became one immortal block. The rule that follows from it is in section 6: a const whose initializer is not static data is built once and read with a retain, in both back ends.

F15. A recursion that is too deep is a panic, for one comparison per call#

Pattern. Every function that calls program code - a function of the program, a closure, a member of a witness table - begins with TORB_CHECK_STACK(TORB_LOCATION(...)): the address of a local against torb_stack_limit, which torb_process_start works out once from the real bounds of the main thread's stack plus a reserve of 128 KiB for the panic itself. A leaf, and the self-recursion in tail position that is a jump, pay nothing.

What it costs. On benchmarks/call-depth, a recursion whose whole body is a comparison, two subtractions and a checked addition, which is the worst case there is. The same C built four ways, nine runs each, wall time with the process start included (fastest, then median):

The check is four instructions - two loads, a lea and a compare - and a branch nothing takes, and it is inside this machine's band; run.sh put the binary at 373-394 ms without it and 393-413 ms with it over four sessions. The static copy saves nothing, so the check reads the runtime's global. A counter is 1.74x on the same program: it writes memory twice per call and has to be undone on every way out of a function.

Why not the counter the design first asked for (decided gap 8 of BACKEND.md): besides the cost, a count cannot keep a C stack from overflowing. The same probe (tests/conformance/stack-overflow.trb) panics between 20 000 and 40 000 frames of a two-slot function on this machine's 2 MiB main thread stack, so a limit of 100 000 frames would never have been reached - the program crashed on the guard page first, with no message and an exit code of the operating system. The comparison with the real limit is what turns that crash into a panic with exit code 101.

What it risks. A leaf or a function of the runtime below the last check that needs more than the reserve still reaches the guard page, and so does a recursion inside the runtime itself (a D_ drop function over a very deep value). A thread other than the main one needs its own limit when tasks get threads of their own.

F16. A range of a trait-typed list reaches the list's own slice#

Done (2026-09-27). The findings below were written before; what was done, and what it measured:

• A member that answers exactly Self gets a slot of the table once the program calls it on a trait-typed value, behind the fixed members, the way a member with type parameters of its own does (docs/BACKEND.md 1.4). The slot points at t_answer__<member>_<table>, which calls the implementation's member - ArrayList.slice - and boxes its answer with that very table: on a trait-typed receiver Self is the receiver's own trait type, and the answer is a payload of the receiver's type again. A receiver of several bounds gets its own tables put around the payload at the call site. Where the devirtualization knows the payload, the call is the direct one.
• Lazy, because the fixed slot was measured first. A slice in every table of List and of its supertrait Slice instantiated ArrayList.slice and two functions around it for every item type of a program, sliced or not: the compiler's C grew by 5.5% (69.97 to 73.81 MB). The lazy slot grows it by 0.1% (70.03 MB), for the sixteen item types the compiler really slices.
• benchmarks/binary-formats.trb (section 4.1), the same std/ built by the compiler before and after: the allocation count of the whole program went from 20 587 650 to 19 298 507 (1 289 143 fewer, 6.3%), the bytes allocated from 689.8 to 652.9 MB, and the DNS decoding - the ranges of ByteReader.bytes and of every text a record holds - from 2.065 to 1.957 seconds (fastest of 21 alternating runs, pinned to one core at high priority) and from 2.272 to 2.084 (median), and 1.983 to 1.889 and 2.166 to 2.061 in a second sweep. gzip and SHA-256 did not move. tests/conformance/list-slice-override.trb pins the behaviour in both back ends.

What follows is the finding as it was written.

Pattern. bytes[from..to] where bytes: Bytes - at the time List<UInt8>, a trait (Bytes is a Buffer<UInt8> since docs/design/COLLECTIONS.md section 6e, whose range is a copy). Every binary format reads a run of bytes this way, and std/dns did for every label and every record's data before std/binary (docs/design/BINARY.md section 4).

What is generated. A call of the default member List.slice: it copies the receiver, clear()s the copy and appends the items of the range one by one, each an indirect call and a torb_make_unique. ArrayList.slice - an offset and a length over the same storage, torb_list_slice, O(1) and no allocation - is never reached: the C of benchmarks/binary-formats.trb has no call of ArrayList.sliceBetween at all. A default member is not a slot of the witness table (BACKEND.md, "Witness tables"), and the override in ArrayList does not make it one here.

What it costs. The first ByteReader.limited took a range of its input for every DNS record: 412 432 allocations more than the hand-written reader over the benchmark's 72 000 records, all of them the copied data. A reader that holds the same input and a window of it brought the count back to within 32 of the hand-written one.

Where the fix goes. The witness table of List for ArrayList (and TrieList) carries the override of slice, or the devirtualization of F2 turns the call into the direct one where the payload is known. Worth: every range of Bytes in the standard library, O(n) copies to O(1). Risk: a range then keeps its whole storage alive, which is what torb_list_compact is for.

F17. The return trace of ? costs nothing in release and a load per ? in dev#

Pattern. In the dev profile every ? takes part in the return trace (docs/language/errors/top-level-errors.md, rules 5 and 6): a mark before its operand, a rewind when the operand succeeded, a record when it hands a failure on. The C names TORB_RETURN_TRACE_* macros that only TORB_PROFILE_DEV makes code of; a function that has a ? looks the trace of its thread up once, at its entry, so the mark and the rewind are a load and a comparison and only the lookup is a call - MinGW's _Thread_local is emulated TLS, one call per access. The VM writes the four operations as kernel calls, and only for a run in the dev profile.

What it costs. Windows, gcc 13, a machine with other builds running, so the minimum of the runs counts:

The first version called a function for every mark and every rewind and doubled the dev loop (1520 ms against 637 ms): two emulated TLS accesses per ?. Looking the trace up at the entry of the function is what made it a load.

What it risks. A program that does nothing but ? in the VM pays about 160 ns per ?; an interpreter that kept the counter in a register of its own would pay nothing, at the price of an operation the interpreter handles apart from the kernel.

4. The benchmark table#

benchmarks/ holds one program per pattern and the C a careful C programmer would write for the same work. sh benchmarks/run.sh --allocations produces this; benchmarks/README.md says how to read it.

Whole programs are measured beside the patterns: six of the Computer Language Benchmarks Game in benchmarks/game/, each against the Benchmarks Game's own C, Python and JavaScript, measured by sh benchmarks/game.sh on the forge's Linux runner after every nightly and shown on the website's benchmarks page. Section 4.3 says what they found.

Windows 11, 16 cores, gcc 13.2.0 (MinGW-W64 x86_64-ucrt-posix-seh), -std=c11 -O2 -g0 -Wall -Wextra. Both sides are built by a torb binary directly (TORB_COMPILER=), before by the compiler of the previous commit and after by the compiler round P7 produced. Times are the fastest of nine runs, in microseconds, net of the process floor that nothing.trb measures.

Round P7 re-measured the six programs a place, an element or a collection is in; the six that hold none - the whole top half of the table - were left at what the P6/P8 sweep measured, because nothing this round changed can reach them. A row whose before and after come from different sweeps says so in the last column.

The c column is the after sweep's; the before sweep measured the same binaries and got numbers between 0.8x and 1.3x of these, which is what one machine does to itself between two sweeps. Read the torb column and the allocation column; the ratio says where a row stands today and not how it moved.

What round P7 moved, in the column that is a property of the program and not of the machine:

The C twin of nested-write measured 1 627 microseconds in this sweep against 9 005 in the before sweep, which is the noise the section below warns about; the torb column and the allocation column are what this row says.

What rounds P6 and P8 moved, in the column that is a property of the program and not of the machine:

What round P5 had moved:

What rounds P1 to P4 had moved, against the audit's own first run of the same suite:

Four things this table does not say on its own:

• A ratio with a > in front of it is a lower bound. The C twin of that row does a few hundred microseconds of work, which is inside the noise of the process floor, so the runner computes against two milliseconds instead. Both sides of accumulate are that small, which is what round P1 left of it; the allocation column is the exact statement there.
• The C twins of list-index, list-iterate and pipeline vectorize. gcc turns a sum over an array into a vector reduction, and no program whose elements come back from a call can do that. Part of those three ratios is the vectorization and not the dispatch; what stands between the loop and a reduction now is the bounds check and the Option of get and next (finding 8's open half and a standard library question).
• The ratios are steadier than the absolute times, and the allocation column is exact. Three sweeps of the suite in one session moved the C twin of nested-write between 1 and 4 114 microseconds with nothing about it changing, and the C twin of call-depth between 139 756 and 155 650. A run that shares the machine with another build moves both sides and moves them by different amounts. Read the allocation column first; the microseconds are there so a later run can be compared against the same shape of number, measured the same way.
• Nothing here is a gate. Section 6 says which of these numbers should become one and in which shape.

4.1 The standard library against itself: binary formats#

benchmarks/binary-formats.trb has no C twin: it measures the migration of std/dns, std/compression, std/archive and std/digest onto std/binary (docs/design/BINARY.md) by building the same program against the std/ before and after it. The two binaries run alternately, pinned to one core at high priority; seconds, the fastest of the runs and their median.

Windows 11, 16 cores, gcc 13.2.0, torb build (release, -O2), 21 runs per sweep, on a machine that other gate runs shared: the same binary moved by 10 to 20% between sweeps, and no row separates before from after - the sign of the difference flips between the fastest and the median and between the sweeps, from -3% to +8% on the DNS and from -6% to +6% on gzip. The column that does not move, the allocation count of the whole program, is 20 587 696 before and 20 587 652 after, and the bytes allocated went from 691.6 to 689.8 MB. SHA-256 still reads its blocks straight from the list (decision 9 of docs/design/BINARY.md), so its rows measure the writes of finished and the machine.

4.2 std/compression: inflate and deflate rewritten for speed#

gunzipped decoded one bit per call - BitReader.bits(1), a Result, a walk of the canonical code per symbol - and appended to a trait-typed List<UInt8> (Bytes then), so every byte of the output went through a witness table; gunzipped then copied each member into the result with appendAll, one call through the table per byte again, and crcValue read the member through an iterator. deflated read the input, its hash chains and its BitWriter through witness tables too. What changed, with the same API, the same answers and the same errors at the same offsets:

• Inflating: a buffer of up to 56 bits refilled a byte at a time, one refill per symbol; a table of the next ten bits for each code (Array<Int, 1024>, an entry symbol << 4 | length), and puff.c's walk only for a longer code; the last 32 KiB in an Array<UInt8, 32768> on the stack, which a match reads and writes inline; every member appended to one concrete ArrayList<UInt8>, and its checksum read from a slice of it with the bounds check dropped (section 1, finding 8).
• Deflating: the chains and the output in concrete ArrayLists, the fixed codes reversed ahead of time, the hash of three bytes rolled from the one before, and a candidate compared only where it matches the byte just past the best match so far - the only way it could become longer, so the output is byte for byte what it was.

The machine was shared with other gate runs, and the same binary moved by up to 60% between runs (the first run of the old gunzipped took 5.8 s). The differential check: 14 members - gzip -1 to -9 of text and of a binary, random bytes (stored blocks), zeros, an empty and a one-byte input, a name in the header, three members in a row - each cut at 40 points and changed at 40 bytes, 1 162 lines of results, the same with the std/ before and after; the gzip members the two write are the same bytes. In the VM nothing got slower (a 300 KB member: 1.86 s before, 1.59 s after).

What is left is the runtime: an append to an ArrayList is a call of torb_list_add (about 13 ns, measured by appending a constant 30 million times), which is 0.39 s of the 0.60, and a read of a list whose index is not proven inside is a call of torb_list_get. The search of deflated reads the input and the chains that way for every candidate, up to 64 of them per position; the input is a trait-typed Bytes, which a copy into a concrete list made slower rather than faster (7.4 s against 4.7 s). A bulk append of a range of the list itself - what a match is - or an inline fast path of torb_list_add for a unique list with room would be the next step, and both are the runtime's.

The inline fast path (2026-09-28). torb_list_add, torb_list_get, torb_list_at, torb_list_length and where the elements of a storage begin are static inline in torb.h now, and no native changed: the declarations torb_natives.h writes after them take their internal linkage, as torb_machine_load's does. An append to a storage only this list holds, whole and with room, is a comparison of the count, a store and two increments, and a byte is copied inline; everything else goes through torb_list_add_prepared in list.c as before. What it was: a call, a second call to torb_is_unique in memory.c, a third for where the elements begin - which divided by the alignment - and a memcpy of a size the compiler did not know. A copy of a larger constant size is out of line (torb_element_copy_sized): inlined where the value is a local of one known type, GCC sees it run past that local on a path that never runs, and says so under -Werror at the link of a program optimized across its units, where no pragma reaches. The same 30 MB of C, torb build, the compiler of the same commit, fastest of three on a machine other gate runs shared:

Deflating is faster because every read of the input and of the chains is torb_list_get inlined behind one call of the witness table; reading the trait-typed input into a concrete ArrayList<UInt8> first made it no faster (2.4 to 3.8 s in the same runs), so the input stays as it is. What is left of deflating is that one indirect call per byte read.

4.3 The Benchmarks Game#

benchmarks/game/ holds binary-trees, fannkuch-redux, n-body, spectral-norm, mandelbrot and fasta: the Benchmarks Game's plain single-threaded C programs (its "naive transliteration" family, #8, and #1 for binary-trees), and TorbScript written statement for statement after them. Unlike the patterns above, nobody chose these programs to show a cost: they are what everybody compares languages with, and the website shows them (site/benchmarks.md, benchmarks/README.md). The numbers the website shows are the forge's; these are the first ones, from the machine this document is measured on - loaded by other builds, so the processor time of each process, the fastest of three, rather than the wall time:

Windows 11, gcc 13.2.0 (MinGW-W64 UCRT), both sides -O2, torb build in its release profile. The outputs of all twelve binaries agree with each other, and with the Python and the JavaScript.

n-body. A Body is seven Floats, 56 bytes, above inlineSizeLimit (32, compiler/src/ir/layout.trb), so the list holds a pointer to a counted block per planet, and the Element step of round P7 - which steps into a record stored inline - does not apply. What bodies[i].velocityX = bodies[i].velocityX - dx * pullOfJ becomes is the round trip finding 4 removed for inline records, with a copy in it:

s36 = t_std_..._ArrayList_at__T_..._Body_x24_site(*s0_bodies, s3_i, &TORB_LOCATION(...));
s37 = s36->f_velocityX;
torb_release(s36, NULL);
...
s41 = t_std_..._ArrayList_at__T_..._Body_x24_site(s40, s3_i, &TORB_LOCATION(...));
s41 = (T_..._Body *)torb_make_unique(s41, sizeof(T_..._Body), NULL, NULL);
s41->f_velocityX = s39;
torb_list_make_unique(&*s0_bodies);
n_std_x2f_collections_list_ArrayList_set__T_..._Body_x24_site(s0_bodies, s3_i, s41, &TORB_LOCATION(...));

at hands out the element retained, so the block is shared when torb_make_unique asks - and it copies all 56 bytes into a new block for every one of the six velocity writes and three position writes of a pair, which the set then stores over the old one. Every read of a field is an at, a retain and a release. An Element step into a boxed record - write through the pointer the list holds once the list and the block are unique - would make this loop what the C is; that is the next round this program asks for.

fannkuch-redux and spectral-norm. list[i] = value on a concrete List<Int> or List<Float> is the direct call of the devirtualization (finding 2), but the callee is the native ArrayList.set, which gcc cannot see into: the bounds check, the write and the call itself stay in the innermost loop, preceded by a call of torb_list_make_unique. The read list[i] is TorbScript and inlines, with its bounds check (finding 8's open half). A store as inline as the read - set written over torb_list_element_reference, and one makeUnique hoisted out of a loop that writes the same list - is what these two ask for.

The VM. The same programs in the VM, on inputs a tenth to a hundredth of these, took 3 to 30 times as long as CPython (python/, the Benchmarks Game's programs) - n-body and fannkuch-redux the slowest, for the reason docs/design/VM.md section 10 names: a place such as bodies[i].velocityX is a record of path steps the interpreter reads step by step per load. The website shows both, measured by the forge every night.

5. The plan#

Each round is one agent's work, in this order. A round names the files it touches and the gate it has to leave green.

Before milestone 7 are P1 to P8: each of them is a property of the IR or of the runtime that the VM will read the same way, so doing them first means the VM is written against the shape that stays. All eight are done, and the rows they moved are in section 4. After are P9 to P12: P9 and P11 change what a construct lowers to and were better decided once there are two back ends to answer to (there are two now, and section 5.1 gives P11's answer to both), P10's whole-program dead-member scan is a code-size fix that both back ends now take (it is done: the C loses a thunk and the bytecode a chunk for every slot it empties), and P12 is a measurement whose answer P7 had changed - the copies it removed are what finding 13 was waiting on (it is done, and the answer is yes: finding 13).

Finding 9 (the pipeline) has no round of its own: what is left of it is a trait-typed value in a field, which is the one place the devirtualization may not go, and benchmarks/pipeline is how it is read.

What P7 built. A new pass, compiler/src/ir/elements.trb, between the devirtualization and the ownership pass: it finds the take-out and the put-back of an index path on a concrete list and replaces them with one PathStep.Element, which the C back end now emits as torb_list_element_reference. The step carries the static and the site of the panic Index.at would have produced, read out of that body, so the message stays the one std/core decides. Two things came with it: the value of an assignment is lowered before its path is formed (BACKEND 2.3's own rule for when an access begins), and a function nothing in the translation unit names is emitted with external linkage, because a pass that removes the last call of one would otherwise make the C stop compiling. A map keeps the round trip: an Element step steps into contiguous storage, and the interior pointer a table needs is P9's torb_map_slot.

What is left of P8. The bounds check half. The interval facts are there and the analysis is written down; what is missing is a second path through Index.at, because the check of a[index] is an Option the standard library builds and not an Intrinsic with a flag on it. Finding 8 says what such a round would have to build.

5.1 What P11 builds#

Round P11 is not a change of lowerForIterate, which is the one file the table of this section used to name. This subsection is the specification of its implementing step, which is built (compiler/src/ir/counted.trb); its result is at the end of decision 5. Every excerpt is from finding 5, from section 4 or from a file of the repository, and the loop in decision 3 is marked as the shape the pass writes and not as output of torb ir.

The loop that matters. benchmarks/list-iterate writes for value in numbers with numbers: List<Int>. The lowering sees the trait, not the list: lowerForIterate dispatches iterate and next through the trait before devirtualizeProgram has run, so at that point an ArrayList and any other List are the same type. What finding 5 shows after the devirtualization is the cursor as a record on the frame, a direct next and an Option per turn:

%2 = call t_std_x2f_collections_list_ArrayList_iterator__Int64_x24_direct(%0 owned last)
b1:
  %4 = call t_std_x2f_collections_list_ListIterator_next__Int64(&%2 borrowed)
  %5 = tag %4
  switch %5 case 0 b2, otherwise b4

1. Where: an IR pass in finishLowering, between rewriteElementPlaces and dropProvableChecks. A new file, compiler/src/ir/counted.trb, with one wiring line in ir/lower/lower.trb, which is the only caller of devirtualizeProgram and so the only place both back ends pass through. Reason: the concrete cursor exists only after the devirtualization, which is also why P7's rewriteElementPlaces is a peephole over the IR and not a branch of the lowering (the header of ir/elements.trb). The pass runs before insertOwnership, so it writes no count; the ownership pass sees an ordinary Read of an element. It runs before dropProvableChecks, so that pass reads the finished loop; the increment is written unchecked already (decision 3), so it has nothing to prove. After it, dropUncalledMembers finds the direct next without a caller where nothing else dispatches it, and takes its thunk back (finding 12).

2. Which lists: a cursor of the flat runtime list, found by its shape, and no other. The pass takes a loop whose cursor is a Record of std/collections' ListIterator or TrieListIterator, or of std/core's BufferIterator, and whose next is the next of that very type. Reason: all three are the same twenty lines (get, then index + 1) over a field of the IR type Runtime(ListStorage, Item), and ArrayList, TrieList and Buffer are that one type today (compiler/src/ir/instantiate.trb registers all three as PrimitiveKind.Runtime(RuntimeKind.ListStorage)). TrieList is a native type of its own with its own TrieListIterator, not a name for ArrayList, so the pass has to name both cursors; it stops matching by itself on the day a trie is a different storage, because the field is no longer a ListStorage. The function is recognised as the next of a standard package type (standardFunctionsOf, as listMembersOf recognises at and length), never by a user type that happens to have the same fields. Everything else keeps its cursor and its Option:

• RingList: its iterate is a pipeline over a range ((0..lengthValue).filterMap { ... }.iterate()), not a ListIterator, and its storage is a ring, so there is no contiguous run to count over.
• Array: an ArrayIterator over inline slots, which is a different storage and a different step, and no part of this round.
• A map, a set, String.chars(), a pipeline stage, and every user Iterate or user List: a user List may answer at in O(n), and an indexed read of it inside a counted loop would make the loop quadratic. The pass never asks a type what its at costs; it only accepts the three cursors above.
• ConsStack and BankersQueue are a Stack and a Queue, not a List, with cursors of their own (ConsStackIterator, ...). They are named here only because the sibling issues name them: they never were a ListIterator, so nothing can reach them.
• A cursor that stayed boxed (two implementations meet in the subject) keeps its dispatch, its box and its makeUnique, exactly as finding 5's test pins.

3. What the loop becomes. The head keeps its place, and so do the edges into it, because continue jumps to the head and break to the block after the loop. What changes is what stands in the head and what happens when the head says "one more":

# the shape the pass writes, not the output of torb ir
%7 = call <length>(%2.items borrowed)            # once, before the head
%8 = constant 0                                   # the counter, a slot of its own
b1:
  %9 = intrinsic less.i64 %8, %7
  branch %9 b2, b4
b2:
  %4 = read %2.items[%8 unchecked]                # the item, where next answered an Option
  %8 = intrinsic add.i64.unchecked %8, %10        # the increment, here and not in a step block
  ...the body, unchanged

• The subject is held for the whole loop. lowerForIterate's own comment says it: the cursor holds the list by value, and a write to the original while the body runs copies the shared storage (MakeUnique), so the storage the cursor holds keeps its length. Nothing in the body can name the cursor, and the pass only accepts a cursor whose uses are its one construction and its one next call. Hence length is read once, and the counter stays below it.
• No bounds panic can occur, so the site of Index.at is not needed. The step is formed with checked: false, as ir/bounds.trb forms it for for index in 0..list.length(); the at the step must carry (PathStep.Element asks for a LocationId) is the location of the loop head, and it is never reached. ir/bounds.trb itself is not involved: its proof needs a Branch on a length() slot of a list the function does not write, and here the pass is the one that wrote both.
• The increment is at the top of the body, not at a step block. A continue re-enters the head and a break leaves; neither needs to know about a counter. The increment cannot overflow, as the head has just said counter < length.
• break and continue are therefore unchanged edges. An empty list fails the first comparison and runs nothing, as next answering None did; the cursor is still built, as it is now. A tuple pattern reads the item into its slot and lowerPatternBinding takes it apart from there, as it does after the Read of the Some now.
• An item that is a counted value (a String, a list, a boxed record) is copied out of the list by the Read, and insertOwnership retains it there and releases it at the end of the scope of the turn, which closeScope already ends. Today's next pays the same retain inside get (torb_list_get answers a retained copy the caller owns), so the count of retains per turn does not change. tests/conformance/list-bounds-proven.trb (joinedLengths, over a List<String>) already holds an unchecked element read of a counted item.
• The pass refuses a loop it does not recognise whole - the head is exactly the next call, its tag and the Switch; the Option is read only by that tag and the one Read of its Some - and leaves it as it is.

4. Both back ends. The pass works on the IR, so the C back end and the bytecode back end take the new loop without a line of their own. The C back end writes the unchecked step as torb_list_item(list, index), a static inline of torb.h (elementReferenceOf in backend/c/body.trb): an offset into the storage, with no comparison and no Option. The VM runs the same step as ListItemAddress, which keeps its comparison and drops the copy (finding 8): per turn a comparison, one kernel call and an add, where it ran a call frame for next, a kernel call for get that builds an Option, a tag and a switch. The section 4 table has no column for the VM, so no number says how much that is; the condition is that torb run of benchmarks/list-iterate does not get slower, which step 2 measures in the same CI job and records. The new conformance programs run under both back ends: tools/conformance.sh runs them natively, and tools/conformance.sh --vm runs the same programs by the VM against the same expectation files.

5. Measurement, and the two numbers that decide it. The "before" numbers are section 4's, and nobody re-runs them here: list-iterate 901 738 µs, 39.09x, 24 allocations; list-index 309 942 µs, 13.25x, 24 allocations. The implementing step runs benchmarks/run.sh --allocations in the forge CI once on main and once on its branch, in one job each, and records both tables as the runner prints them (fastest of several runs; a measurement, not a gate). Ratios are read inside one run, because the C twins move between runs (section 4).

• Done: the list-iterate ratio is at most 10% above the list-index ratio of the same run (13.25x is 14.6x on these numbers), and its allocations stay 24 (exact, not a threshold). The loop is the same size as the counted index loop and has less to do per item - list-index still pays the Option of at, which ir/bounds.trb does not remove there because its limit is a constant and not length() - so equal is the least to expect. The C twin vectorizes, and the new loop has no branch left for gcc to stop at, so a ratio below list-index's is possible and is not a goal.
• It did not help: the list-iterate time is above two thirds of its time on main in the same run (601 000 µs on section 4's numbers), or the allocations are not 24. Then the generated C is read before anything else is built: whether length was hoisted, and whether a retain stayed in the loop.
• Between the two: the round is kept, the numbers recorded, and the C read for what is left.

Result (round P11, forge CI run 1745, tools/collection-cost.sh at the end of tier B). One job builds the compiler of the merge base (44a359160d) and the one of the branch (51d38d87c7) and runs benchmarks/run.sh --allocations with both on the same machine, the fastest of nine runs in microseconds, as printed:

--- base                                         --- head
program              torb   c       ratio       program              torb   c       ratio
list-index         220065   34144    6.44x      list-index         218144   33924    6.43x
list-iterate       378156   35615   10.61x      list-iterate        55823   37733    1.47x
array-write        170193   25343    6.71x      array-write        165322   24430    6.76x
buffer-write       170178   25656    6.63x      buffer-write       166101   26277    6.32x
list-slice          13827    8173    1.69x      list-slice          14540    6224    2.33x
list-write-shared   93515   21020    4.44x      list-write-shared   84192   18941    4.44x
list-literal       313057   17964   17.42x      list-literal       301633   16992   17.75x

The allocation column is the same on both sides, row by row: list-index and list-iterate allocate 22 blocks (33 554 951 and 33 554 953 bytes), array-write, buffer-write and list-slice 21, list-write-shared 261, list-literal 8 000 001.

• Time: done. list-iterate is 1.47x against list-index's 6.43x of the same run, so far inside the bound of "at most 10% above" (7.07x); against main it fell from 378 156 to 55 823 µs, 0.15 of its time, where "did not help" starts at two thirds. The loop is now cheaper than the counted index loop, because it has no Option of at left (the list-index row did not move: 6.44x to 6.43x).
• Allocations: unchanged, and not 24. The decision wrote 24, the number of section 4's run. Since then main moved to 22 for both programs, and the pass changes none of them: list-iterate allocates what list-index allocates, which is the property the decision meant ("the same as list-index").
• The other rows are inside the run-to-run noise of the C twins, the way section 4 reads them (list-slice moved with its twin: 13 827 and 14 540 µs, the twin 8 173 and 6 224).
• The VM: not as hoped. collection-cost.sh ran torb run --vm three times per program and took the fastest: list-index 23 215 ms on base and 23 513 ms on the branch, list-iterate 20 828 ms on base and 62 526 ms on the branch. The condition "does not get slower" does not hold in that run, and the cause is not found: the step the VM runs for the new read is ListItemAddress, one kernel call like the ElementAddress of list-index, which did not move. Whether it reproduces and where the time goes is #482; the fix belongs to the emitter or the VM, not to the pass.

6. Seed: none expected. No syntax, no native, no flag of the driver and no name the seed looks up. The pass is new compiler code that reads three names of std (ListIterator, TrieListIterator, BufferIterator) at the time it runs, in the compiler the checkout builds, from the same checkout's std, as listMembersOf does for at and length; so it is one change and not the two commits of compiler/CONTRIBUTING.md. The cost of the names is silence: a rename of a cursor would switch the pass off without an error. The IR snapshot of step 2 is what catches it, because it asserts that the loop of list-iterate has no next call left.

Related work: the collections design record (#413). It is on main now (docs/design/COLLECTION-STORAGE.md, Buffer is a List). Its decision 4 describes a cursor of a Buffer value, an index and the end of the window; that is a design, not code, and the cursors in std are still the ones decision 2 matched, re-read for this round: TrieListIterator (std/collections/src/list.trb:588), ListIterator (:610) and BufferIterator (std/core/src/buffer.trb:249) each hold the list or buffer by value in items and a var index, and their next is get, then index + 1; compiler/src/ir/instantiate.trb still registers ArrayList, TrieList and Buffer as Runtime(ListStorage). So decisions 2 to 5 stand as written. The day the cursor gets an end field, the match of counted.trb stops recognising it and the loop keeps its Option silently; the IR snapshot of compiler/tests/counted.test.trb (the loop of list-iterate has no next call) is what fails then, and the match is adjusted, not decisions 3 to 5.

Step 2, outline. Sized for one PR of two Conventional Commits:

1. perf(ir): count a for over a flat list - compiler/src/ir/counted.trb, the wiring in finishLowering, an IR snapshot in compiler/tests/ (the loop of list-iterate has no next, a less, a [... unchecked] read and an unchecked add; a RingList and a user Iterate keep their next), and conformance programs in tests/conformance/ for break, continue, a tuple pattern, a counted item, an empty list and a write to the original inside the body, each with its .allocations budget.
2. docs(performance): record round P11 - the before and after tables of decision 5, section 2's row, finding 5's "what is left", this section's status.

If it grows past that, the cut is by cursor: the first commit takes ListIterator alone (the loop the benchmark measures), and TrieListIterator and BufferIterator follow as a PR of their own with their conformance programs. The benchmarks/list-iterate budget is not a .allocations file - a benchmark is not a conformance program - but the --allocations column of benchmarks/run.sh.

6. What makes it permanent#

A number that nobody measures again goes back. Four of these belong in the gates, and one is a feature.

An IR snapshot for each finding, in compiler/tests/. The IR text form is deterministic and readable (BACKEND 1.7), so a snapshot is the cheapest possible regression test and it fails far earlier than any C-level test. The three that matter most:

• x = f(x) at the last use shows owned last and no retain (compiler/tests/ownership.test.trb).
• A value whose payload the program decides holds no traitValue and no callWitness, and one that escapes as the trait holds both (compiler/tests/devirtualize.test.trb).
• No makeUnique stands on a container the surrounding frame still holds - the "no copy on a shared row" rule.
• No loop head holds a makeUnique.

An allocation budget per conformance program. tests/conformance/ already runs every program a second time with TORB_REPORT_LEAKS=1 and asserts that the live block count is zero. A second number in the same report - how many blocks the program allocated in total - turns the same run into a budget: a program that starts allocating per element where it used to allocate per loop fails the suite instead of being noticed a year later. It is one counter in runtime/memory.c and one line in the report, and it is the only measurement in this document that does not move with the machine.

Built that way: the report's third line, allocated blocks at exit: N, counts every block torb_allocate and torb_raw_allocate made, live or immortal, once (a worker's count is folded into worker 0's when the pool stops). Each program with a leak run holds its budget in a <program>.allocations file beside its .expected, and the native leg of tools/conformance.sh in tier B compares it with the count of a run with one worker. The rule:

• Exact. A count above the budget fails; there is no tolerance. With one worker, a fixed profile and nothing timed, the number of blocks is a function of the emitted C, and a percentage would let one block per loop in unseen exactly where it matters, in a small program (the benchmark list-iterate allocates 24 blocks in all).
• A gain is kept by hand. A count below the budget passes and the run's closing note names it with the command that lowers it, sh tools/conformance.sh --update-budgets --filter <program>, so one round's improvement never turns another round red. Raising a budget is a change of its own, one visible line, and its commit message says why; --update leaves the budgets alone. A program with a leak run and no budget fails and prints its count.
• Unbudgeted with a reason. A program whose count differs from one run to the next (it is driven by time, by a child process or by what the system answers) holds unbudgeted: <reason> instead, as .leaks holds its reason. --update-budgets counts three runs and writes nothing where they differ.
• Linux x86_64 enforces, the other platforms report. The raw blocks of the runtime's platform layer (wide buffers on Windows, path conversions) are not the same number everywhere, so the portable runs print the counts that differ from the budget and compare nothing; TORB_ALLOCATION_BUDGET=enforce|report says otherwise. The VM legs read no budget: whether the VM allocates as the native binary does is a comparison for later.

A size budget for the emitted C. The three-line list program of finding 2 is the canary for findings 2 and 12; the compiler's own program.c is the canary for everything. One line in CI that asserts both are under a number, with the number in the file, so a change that makes it bigger has to say so. Half of it is built: round P10 pinned the list program's thunk count and a byte budget in compiler/tests/emit-c.test.trb; the compiler's program.c has no budget yet.

A benchmark ratio budget. benchmarks/run.sh is not a gate today and should not become one as it is - it is wall time on one machine, and the two lower-bound rows show how far that can be pushed. What can be a gate is the allocation column, which is exact, and a ratio with a wide band (list-iterate under 2x rather than under 1.1x) run on one known machine.

torb build --explain-copies. The one real weakness of copy on write is that the copy is invisible: nothing in grid[row][column] = value says that it copies a row. The IR knows - a MakeUnique on a reference whose base is live afterwards is exactly a copy that will happen - so the compiler can say so at the source position:

note: this write copies a shared value
 --> src/main.trb:12:3
  |
12 |     rows[row][column] = rows[row][column] + 1
  |     ^^^^^^^^^^^^^^^^^
  = `rows` still holds the row, so the row is not unique and the write copies it (O(length of the row))
  = the copy goes away when `rows[row]` is taken out and put back: `var cells = rows.removeAt(row)` ... `rows.insert row, cells`

It is a flag and not a warning, because a copy is not a mistake - it is the semantics working. What it gives a user is the one thing value semantics otherwise hides.

Built (torb-build.md, compiler/src/ir/explain-copies.trb): a write through an owner another slot of the function still holds after it, or a parameter holds, is one note with the reason as its first line. Where the write goes into an element of a list that a variable holds, a second line says how to avoid the copy in the program's own names: take the element out and put it back. A field, a deeper path or an array has the reason alone.

7. What is not measured here#

• The VM, but for the six programs of section 4.3. Everything else above is the C back end. The model of section 1 and the instance counts carry over; code size does not, because bytecode has no 139-byte names.
• Peak memory, but for the programs of section 4.3 on the forge's Linux runner, where GNU time reports it. The suite counts allocations and bytes asked for, which is exact and portable; peak resident set is not obtainable from a POSIX shell on Windows and is left out rather than guessed.
• The build time of the compiler itself. BACKEND 6.3 measures where the C comes from; section 8 measures what compiling it costs, and section 9 what the front end costs before the C exists.
• Threads and tasks. Milestone 7.3 and 7.7.

8. The build time of a large program#

A C compiler compiles one translation unit on one core, and the compiler's C was one unit of 60 MB, its test suite's one of 87 MB. BACKEND 4.1 cuts such a program into a unit of data and up to sixteen units of code that compile at the same time, optimizes them across each other at the link with gcc's -flto, and keeps every object and the binary in a cache. Measured on the machine of this document (16 threads, 32 GB, gcc 13.2.0), with other work running beside it, so a number is good to about ten percent.

So the C compile of a large program is four times as fast with -flto and seven times without it, and -flto is what keeps the binary as fast as the one-unit binary was: sixteen plain units lose every inlining between two of them, and the compiler's own front end ran a fifth slower. A small program is faster because the runtime is compiled once per flag set and cached, where it used to be compiled into every binary.

What did not change: program.c is the same bytes as before, a program with less than 4 MB of code - every program of the conformance suite and every example - is still one unit, and the front end (checking, lowering, emitting) is the same 180 to 250 seconds of the compiler's own build it was. That part is now most of a bootstrap, and it is the next lever: a faster C compile cannot make a bootstrap more than twice as fast.

9. The front end of a build#

Section 8 left the front end - reading, checking, lowering and emitting the C - as most of a bootstrap, and it is all of a small build: a conformance program took twelve seconds before its C compile started. This section measures where that time went and records what took it away. torb build --timings prints the wall time of every step, the passes of the checker first, and a sampling profiler over the release binary said which functions the time went to: every few milliseconds it suspended the process, walked its stack with the unwind tables of the binary and counted every function on it.

Measured on the machine of section 8 while it was fully loaded - five processes of another checkout spinning since the day before, two gate runs, a landing and other agents' builds beside it - with the two binaries run alternately, one right after the other. A number is good to about twenty percent; a ratio between two neighbouring runs is better.

9.1 What the time was spent on#

Whether a value may hold a Close object is asked for every temporary the lowering ends (endTemporaries) and every binding it declares (declareScoped, ir/lower/scope.trb). The walk over a type's fields remembered every true, and a false only where it had not come back to a type it was still answering - and in a recursive family of types, the syntax tree of the compiler, it always had. So every temporary of a type of that family walked the whole family again, with a linear contains on the path: 66% of the samples of torb build ./compiler, and its lowering took about 240 seconds. A false at the top of a walk is final for every type the walk entered - each of them reached only types that answered false, or the top would have answered true - so all of them keep it now, and the lowering takes 30.

A write through a trait-typed list in a field copied what the element held. checker.tables was a List<Tables>, and tables[module.value].expressionTypes.set(at, id) through the trait is the round trip of finding 3 - Index.at, the change, MutableIndex.set - which the element step cannot take away from a field, because the devirtualization poisons what is stored in one. The element had a second owner while it changed, so torb_make_unique copied the record, and the map inside it, now held twice, was copied and rehashed by torb_map_prepare: the whole expression table of the module, once for every expression the checker typed. tables, typePositions and diagnostics of the checker are an ArrayList now, which the element step writes in place. The same shape is anywhere a field is a List of records or of collections and one element is written through it; the checker's was the one that cost.

torb build checked every body of its program before it lowered anything. check with checksEveryBody checked every module of every package the program touches, and the program of a conformance program is its whole package: each of the 237 programs checked all 250 files of tests/conformance/ and every module of std any of them imports. torb run has checked on demand since docs/design/VM.md section 8 - the bodies of what was named, and every other module the first time the lowering enters it (enterModule) - and torb build does the same now, with the fallback torb run has: a program the lowering refuses is checked whole and lowered again, so what it is told does not change. The bodies of a small build went from 7 seconds to 5 milliseconds.

The lexer started an iterator per character. textStartsAt compares a text through text.chars(), a boxed iterator, and the lexer asked it for each of the 38 entries of the punctuation table at every punctuation character, for every character of every block comment - every doc comment of std/ and of the compiler - and for every character of every string literal. Each entry of the table carries its first character now, and the comment and the string compare the star and the quote first; the parse of a small build went from 3.8 to 1.9 seconds, and the compiler's own from 11 to 6.

closeHelperDemand copied both flag lists and compared them whole for every field of every layout, which is quadratic in the layouts. A mark only turns a flag on, so a round changed something exactly when more flags are on after it: two counts per round, the same fixpoint in the same rounds.

What did not change is the C. The compiler's own C for windows-x64 and for linux-x64 (70 MB each, and different from each other because an arm of std for Windows reaches one more instance), a conformance program's and tools/release-sync's are the same bytes from the binary before these changes and from the one after, and a build reports what torb check of the same paths reports.

9.2 Before and after#

The suite gained least, because the front end is now the smaller part of a program's turn: its C compile, its run and the leak check are the rest, and the two runs shared a machine that was loaded twice over - the run after finished eleven minutes earlier, and the run before had the machine more to itself for those minutes. A bootstrap builds the compiler twice, so it saves the difference of the last row but two twice once the seed is one of these binaries; until then its first step is the seed's, as slow as before.

9.3 What is next#

The parse. A small build is four fifths parsing now: the whole workspace of the program, 2.7 MB for a conformance program (the 250 files of its package and all of std), at about a megabyte per second - one Char and one offset per character of SourceText, every token appended to a list that is copied once more without its insignificant line breaks, the text of every interpolation lexed a second time. A lexer over the bytes of the text, or the parsed std kept across runs, is the next lever of every small build and of the conformance suite.

The compiler's own build is five steps of one size now - the lowering with the bodies of std it checks on the way, emitting the C, the checker's bodies, verifying, ownership - and the profile already names a first finding in three of them: the verifier's definedness is a List<Bool> per block, compared whole per round (a quarter of verifying); a dispatched call builds the members of its witness table again (tableMembersOf, a fifth of the lowering); and settleEscapes walks every escape check of the program again after each module the lowering checks on demand, which is quadratic in the modules it enters. The C compile of section 8 is the larger half of a bootstrap again.

9.4 The second round: what the time was spent on#

The list of 9.3, taken in order, on the same machine, which was loaded more heavily still - other agents' bootstraps and gate runs, and a C compile of the compiler that took three times its usual minute. So this round reads the processor time of each run next to its wall time (user and kernel, from GetProcessTimes): a loaded machine stretches the wall time of a run by whatever else runs beside it, and its processor time far less. The two binaries still alternate run by run, and a ratio is taken between neighbours. The profiler of round one gained an unwinder of its own - it copies the image of the process once and walks each stack with the image's unwind tables itself - which takes a sample in microseconds where StackWalk64 took milliseconds.

The lexer read a decoded copy of the file, one character at a time, through a trait. SourceText.of decoded every character of a file into a List<Char> and wrote the byte offset of each into a List<Int> - a quarter of lexing, and twelve bytes per character held for as long as the module lives - and every peek read that list through a List field, which is a call through its witness table with two counts taken and dropped around it. The lexer reads the text itself now: a position is a byte offset, peek is String.charAtByte, and a comment is skipped with one search for */ or for the line break over the bytes; no byte of a character past its first is ASCII, so the search cannot stop inside one. A string literal keeps its String reading as slices of the source between the escape sequences, the interpolations and the indentation it loses, where it appended every character to a List<Char> and made a String of that with one show() per character; its verbatim reading, which only writtenTextOf asks for, is not built for any other literal. The line breaks that end no statement are dropped as the token after them arrives, instead of in a second pass over a copy of the list, and the punctuation is a match on its first character, where it was a walk over a list of 38 tuples. The parser reads its tokens from an ArrayList, keeps the one it stands on in a field that bump moves, and answers its questions of the form "is it one of these" with a match instead of a list literal built per question.

Every token and every tree of the 933 .trb files of the repository, and of 800 generated snippets of broken strings, comments, escapes and characters of every width, is the same from both lexers (torb tokens, torb ast). The snippets found the one mistake the rewrite made before any file did: a character that is no punctuation and wider than a byte, whose second byte the punctuation looked at.

taskProblemOf was mayHoldClose again. Whether a closure may cross into a task asks whether each capture may hold an object (unseenInside, containsShared), and both kept an answer only where the walk had not come back to a type it was still answering. In the syntax tree of the compiler it always had, so every closure body walked the whole family of the tree again. Round one's argument holds for both: nothing found at the top of a walk is final for every type the walk found nothing in, because anything found below it would have been found at the top.

The definedness was nine tenths of verifying, not a quarter. It was a List<Bool> per block, intersected over the predecessors slot by slot and compared whole every round - and List.equals is indexed().all { ... }, an iterator and a closure per slot. A BitSet (compiler/src/ir/bit-set.trb) keeps 64 slots to an Int and compares word by word, and what leaves a block is kept beside what arrives in it instead of being joined again for each successor. The liveness of the ownership pass joins and compares the same way and turns its sets into the flags the pass reads once they settle; the ownership check merges a state and says whether it changed, and its rounds that report nothing build no location and list no reads.

The range analysis asked every block whether it precedes. entryOf walked all blocks of the function for every block of every round of its fixpoint and asked each of them for its successors: quadratic in the blocks of a function. The predecessors are a list per block now, in the order the join took them, the natural loop of a back edge walks them instead of every block, and the entries of two rounds are compared field by field.

tableMembersOf is a question with one answer per program: a signature, the supertraits of a bound, and which defaults the closed world overrides, which is collected once. It is kept per bound and subject. settleEscapes re-walked no escape check: what cost was traitMembersOf, which walks every implementation of the program for a call through a witness table and was asked again for every such call site each time the lowering checked a module on demand. It is kept per member and bound with the number of implementations it saw, so a derived implementation - which the checker adds when somebody first asks for it - makes it stale. normalizePath split and joined every path it was handed, and spelling the name of a symbol asks it for the path of the symbol's module three times (moduleComponentOf); a path that is normalized already is answered as it is.

What did not change is the C, and what a check reports. The compiler's own C for windows-x64 and for linux-x64, and the C of five conformance programs and of tools/release-sync, are the same bytes from the binary before this round and from the one after, and so is every token and every tree of the repository.

Measured and not taken: the counts inline. torb_retain and torb_release are calls into runtime/memory.c, and a fifth of the samples of the compiler's own build are in them. A fast path of each, static inline in torb.h - a block no other thread can see is one increment or decrement, everything else the call - took 5 to 10% of the processor time of every case below. Finding 13 measured the same change on the benchmarks at up to 14% faster and up to 9% slower depending on the loop, so it stayed a measurement to redo against the benchmarks rather than a change of this round; round P12 redid it and took the change.

9.5 Before and after, the second round#

The processor time of each case, the mean of three runs (two for the compiler's own), with the binary of round one and the binary of round two alternating:

The steps of one pair of torb build --emit-c ./compiler from the same runs, in wall time on the loaded machine - which is why they add up to more than the processor time above, and why the step nobody touched, emitting the C, is the one to read them against:

At a quieter moment the build of round two took 45 s of wall time: checking 8.1 (parsing 1.6, bodies 5.7), lowering 13.3, ownership 4.5, verifying 3.5, emitting the C 13.1, writing it 2.0. A small build is about a second, of which the parse is still two thirds.

9.6 What is next#

The parse, still. It is two thirds of a small build: 2.7 MB at two and a half megabytes a second, where round one read one. What is left of it is how the parser handles tokens and trees, not how the lexer reads characters - every token is a counted record and every look at its kind takes a count and drops it, every node an allocation. Two levers do not depend on any of that: the files of a program are independent, so they can be parsed in parallel and handed back in order (std/parallel does exactly that, if the tree may cross back as the copy it makes), and the parsed std could be kept between runs.

List.equals is an iterator and a closure per item (done, 9.7). The verifier, the range analysis and the ownership check no longer ask it; a loop in std/collections would take the cost away from every program that compares lists - a change of std, and so of the C of every program that does.

The compiler's own build is now emitting the C, the lowering and the checker's bodies, a third each of what remains, with ownership and verifying at a tenth. The profile names Iterate.joined over the lines of the program - 70 MB of C joined twice, once for program.c and once more per unit, pairwise in log n passes - at 4% of it, which one copy into a buffer of the right size would take (sixteen at a time, 9.9); and the range analysis at 6%, most of it reading and appending the List<Interval> of each block through its witness table.

A write through a trait-typed list - self.tables[module].types.set(at, id) where tables is a List field - is still the round trip of finding 3: Index.at, the change, MutableIndex.set, all through the witness table, with the element owned twice while it changes, so that the change copies it. Round one fixed the one that cost by making that field an ArrayList. The whole class can go in the IR instead of field by field: List.update(index, change) already exists with a default that is the round trip; ArrayList answers it itself, making its storage unique and running the change through the element's address as PathStep.Element does (done, 9.10 - without a native, so without a seed); and the lowering would write a nested write through a container that stayed boxed as a call of update whose closure is the rest of the path (done, 9.11). What makes it more than a peephole: the closure may evaluate nothing the assignment has not evaluated before the access (BACKEND 2.3: the keys, then the value, then the access), a key out of range must panic at the site of at as the element step reads it, and the VM needs the same member. A plain take-out and put-back is no answer: a generic container has no value of Item to leave behind, and removeAt and insert would shift the list twice.

9.7 List.equals as a loop#

List.equals compared two lists with indexed().all { ... }: an iterator and a closure per item. It now checks the lengths and walks the slots in a while loop, stopping at the first difference. The processor time of each case, the mean of three runs, with the main binary and the binary of this change alternating (measured in the forge CI, whose machines are noisy, so the ratio counts):

The ratios are within the noise of the machine (the three runs of one case differ by up to 30%), and none is meaningfully below one: the change is not slower anywhere. It is no speed-up the front end shows either, which is what the profile of 9.4 said: the checker, the range analysis and the ownership check no longer ask List.equals. What the loop takes away is the iterator and the closure in the C of every program that compares lists - the benefit is in those programs, not in the compiler's own build.

9.8 The files of a program, parsed in parallel#

torb parse, torb check and torb build read the files of a program in order and parse them in parallel with std/parallel; the trees come back in input order, so the diagnostics keep theirs (SourceTree.parsedInParallel, parsedAhead). Run, test, the language server and format still parse one file after the other. The commands are tasks the top level does not wait for, because await() needs a function that returns a Task and the VM of torb run and torb test refuses to run its scheduler from inside one.

Measured in the forge CI (job measure-206, throwaway branch loop/206-measure, run 326 of torbscript/language: https://git.torb.dev/torbscript/language/actions/runs/326). The runner has 16 cores (AMD EPYC-Genoa). main (6374a3f0) and this change (578a581b) are both bootstrapped there and run alternately, 3 runs each, mean, as in 9.5; wall time is the point of the change, processor time (user and system) is the cost:

The parse of the 1014 files is four times faster, and the tree crossing back as a copy does not eat the gain. The small check and the small build are faster, not slower. The build of the compiler itself is level within the noise (the runs of one case differ by up to 4%), because there the parse is a small part of 29 s and the rest runs on one thread. The price is processor time: the work is the same and the copy of the trees, the tasks and the idle workers add 6% to 66% of it, which is what a build on a machine with free cores trades for the wall time. The commands do not look at the core count; a one-core machine was not measured.

Equivalence, from the same job: torb tokens and torb ast over every .trb file of the repository (1145 files) print the same bytes on main and on this change (sha256 74ccb5ef86b5d27b both); torb parse std compiler tests (60 problems in 2 of 1014 files, exit 1), torb check tests/conformance/adts.trb (exit 0) and parse and check of a directory with a broken file between two good ones (2 problems in 1 of 3 files, the same order, exit 1) are identical down to the byte; tools/agree.sh emit gives the same hash for all nine targets from both binaries (linux-x64 -8265447926582893297, browser-wasm64 -8005578685030488383).

9.9 The lines of the C, sixteen at a time#

emittedText (the one-unit C) and textOf (each unit's) joined the lines with lines.joined(separator: "\n") + "\n": concatenated merges neighbours pairwise in log2 n levels - about 21 for the compiler's own C - and the + "\n" copies the whole text once more. Both call linesText of the C back end now: sixteen lines, each followed by its newline, go into one piece through one """ interpolation (one TextConcat, one allocation), then sixteen pieces at a time through one interpolation, so every byte is copied once per level of log16 n levels - about 6. It needs no new native and no change to std, so no seed step, and the emitted C of every program is the same bytes (compared for the compiler on linux-x64 and windows-x64, five conformance programs and tools/release-sync, 52 files, main's binary against this one over main's source). compiler/tests/lines-text.test.trb pins the bytes against the old expression at 0, 1, 15, 16, 17, 255, 256, 257, 4095, 4096, 4097 and 5000 lines. The processor time of each case, the mean of three runs, with the main binary and the binary of this change alternating (measured in the forge CI, whose machines are noisy, so the ratio counts):

The two small cases and torb check do not emit C of any size, and their differences (3 to 5%) are inside the noise of the machine (the three runs of one case differ by up to 10%). torb build --emit-c ./compiler is 9% faster, and in all three alternating pairs: 29.65 -> 27.18, 29.69 -> 27.01, 29.20 -> 27.01 s. That is more than the 4% the profile of 9.6 named for Iterate.joined; why is not measured here.

9.10 List.update through the element's address#

List.update(index, change) was the trait's default alone: at takes the element out, change runs on it, set puts it back, so the list still holds the element while it changes and a counted element is copied first. ArrayList and TrieList now answer it with a member of their own, whose body is the same line, change self[index] - and that line compiles differently once self is an ArrayList: the element step of finding 3 (ir/elements.trb) rewrites the round trip into one makeUnique of the list and callClosure change(&self[index]), the element's own address. A trait-typed List reaches the member through its witness table, so a list in a field is changed in place too; an index out of range panics with the message of ArrayList.at, at the site of the call, before change runs. No native was needed - the step already exists in both back ends - so this change is plain TorbScript and waits on no seed.

The processor time of each case, the mean of three runs, with the main binary and the binary of this change alternating in the forge CI:

The ratios are within the noise of the machine, and the C emitted for adts.trb is the same bytes: nothing the front end does calls update on a trait-typed list yet, so the change costs a build nothing and takes nothing away. What it takes away is the copy of the element in every program that changes one through a List it cannot unbox.

One thing does move: the instance-count tripwires of the real-code tests (lower.test.trb, ownership.test.trb). A default is a slot of a witness table only where an implementation of its trait overrides it, and ArrayList.update and TrieList.update are such overrides, so List.update is now in the table of every list the two files build: 45 declarations (43 before) and 97 functions (93 before), the 20 tables and 2 elements unchanged.

The other half of #207 is the lowering: a nested write through a container that is still boxed after the devirtualization, written as a call of update whose closure is the rest of the path (9.6). It has to be decided after the devirtualization - written at lowering time it would turn the containers the devirtualization unboxes into closures and undo finding 3 - so it is a pass over the IR, and again no native and no seed.

9.11 A nested write through a boxed list as List.update#

ir/updates.trb is that pass. It runs after the element steps, so it sees only the round trips through a list the devirtualization left trait-typed, and before ownership, so it sees no count. Where one block reads the list, takes the element out with at, changes it and puts it back with set, it writes one update(key, change) on the list instead, whose closure takes the element by reference and holds the rest of the path. The closure holds only what the statement evaluates after the access; the key and everything before it stay outside and are captured as values, so the order of BACKEND 2.3 holds and an index out of range still panics with the message of at before the rest of the path runs (tests/conformance/list-update-bounds.trb). Only the standard library's update is trusted, and a window it cannot move as a whole - a branch, a debug statement, a var parameter, a dispatch on a generic parameter, a value used after the put-back - stays the round trip. compiler/tests/boxed-updates.test.trb pins the lowered function and its closure.

The processor time of each case, the mean of three runs, with the main binary (91c009ff) and the binary of this change alternating in the forge CI (job measure-207, throwaway branch loop/207-measure):

All three are within the noise of the machine (the runs of one case differ by up to 9%, and the build of the compiler is faster in one of the three pairs and slower in two). The front end gains nothing measurable because round one already made the one write that cost an ArrayList field (finding 3), and the pass itself is one walk over the instructions of each block. What the pass takes away is the copy of a counted element in every program that changes one through a List it cannot unbox; the same job ran both new conformance programs on the new binary with the output and exit code of main.

9.12 A retain and a release of one pointer without the kernel#

The bytecode VM counts through its kernel: kernel retain r, s is a C call of Machine.operate - the machine's allocation counting switched on and off, the operation's switch, the shape's table - for one torb_retain, and a release the same for one torb_release (docs/design/VM.md sections 6 and 7). Where the shape of the value is a single counted pointer - a String, a list, a map, a set, a closure, a boxed record or variant - the count is the first word of the block it points at, and the loop can change it itself: one count more, or one count less that is not the last, of a block of this thread. Everything else still goes to the kernel - a shared block, the last count with its destructor and its free, a count of zero and its panic.

Two forms of that were measured against main (91c009ff), bootstrapped in the same forge CI job and run alternately, processor time (user and system), the mean of three runs:

• TorbScript (throwaway branch loop/164-prototype): the loop reads the header with Machine.load and writes it with Machine.store. No native, no seed.
• Natives (throwaway branch loop/164-measure2): the same in C, Machine.countUp and Machine.countDown, static inline in torb.h. Built with the torb of the natives' first commit as its seed.

Run 419 of torbscript/language (https://git.torb.dev/torbscript/language/actions/runs/419), all three binaries:

Run 406 (https://git.torb.dev/torbscript/language/actions/runs/406), main against the TorbScript form only: chain-walk 3.26 -> 2.82 s (1.16x), list-iterate 33.39 -> 29.31 s (1.14x), map-count 2.84 -> 2.61 s (1.09x), fibonacci(32) 0.96 -> 0.96 s. Every program printed the same line on all binaries, and tools/conformance.sh --vm passed on both forms (279 programs).

• The chain walk is 15% faster, in every alternating pair of both runs: the kernel call was about a seventh of a loop whose step is a match, an add and two counts. list-iterate (6 and 14%) and map-count (3 and 9%) count less per step and gain less; cons-stack is a third of a second, inside the noise (one natives run took 0.40 s).
• What counts nothing pays nothing measurable. A kernel instruction tests one more operand before it calls the kernel, and fibonacci(32) stays level.
• The closures do not move, because they are shared when the list literal takes them (kernel share), and a shared block's count is a worker's too, so it stays the kernel's.
• The two forms are equal. The cost was the call, not the arithmetic around it, so the choice between them is not one of speed. The natives win on the rest: the header's layout (the count in the low half of the first word, the shared bit, the immortal count) stays in C instead of becoming numbers in the interpreter, and the native sees an open sandbox, whose every kernel operation checks the script's memory budget first - it leaves every count to the kernel then, so a script that runs out of memory stops at the same instruction as before. Their price is the two commits of a new native with a seed refresh between them (docs/design/VM.md section 10).
• Taken: the natives. The first commit taught Machine.countUp and Machine.countDown (d43017cd); the second, once the published seed knew them, is the emitter's mark in the head of a kernel retain or kernel release and the loop's test of it, the code the natives row above measured (docs/design/VM.md sections 7 and 10).