perf: P11 - a for over a concrete list is a counted loop #58
Loading…
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Context
F5 level 2;
list-iterateis 44x a pointer walk. Waits until there are two back ends to answer to.Source
Acceptance criteria
Dependencies
None known.
Moved from the planning lists of the docs; the design record stays the specification.
Steps (epic, no
readylabel on this issue)[loop:torbscript] intake: in scope (author orion, label loop), source PERFORMANCE.md round P11, not a duplicate. Touches the lowering in
compiler/src(opus/high when implemented); measured in forge CI (list-iterate). The precondition "two back ends" is checked in refine. next: refine, waiting (ready buffer full: #4, #163, #164, #223 are ready) until 2026-10-10T04:00:00ZTakeOut/PutBackon the map #56[loop:torbscript] claim refine by session:loop-torbscript-20261023 until 2026-10-23T06:51:00Z
forover a flat list in PERFORMANCE.md (step 1 of #58) #415[loop:torbscript] refine: epic, not
ready- the round cannot be one PR yet, so I filed its first step as #415 (docs only,ready), next: step 1 = #415, step 2 (the pass) is filed when #415 has landed.Findings.
forover a concrete ArrayList as COLLECTIONS gap 9 only as a point to decide).ir/lower/statement.trbas the only file. That does not fit the code:lowerForIterateruns beforedevirtualizeProgram, and the benchmark's subject is writtenList<Int>, so the lowering cannot tell the flatArrayListfrom aListwhoseatis not O(1) (ConsStack,BankersQueue), where a counted loop would become quadratic. The concrete type is known only after the devirtualization, which is where P7'sir/elements.trbworks for the same reason.Decided by the loop (no owner question; internal design and performance).
devirtualizeProgramandinsertOwnership, besiderewriteElementPlaces; it recognises the cursor of the flatArrayListiterator and replacesnext'sOptionround trip by a counter and anElementread. Other cursors keep theirs.benchmarks/list-iterateagainstbenchmarks/list-index(39.09x vs 13.25x in section 4), allocations stay 24, recorded before and after in forge CI.Size. Step 1 (#415): one PR, one commit, docs only. Step 2: new pass file, pipeline wiring, IR snapshot test, conformance programs, budget, PERFORMANCE.md status; sized for one PR of two commits, step 1's record says where to cut if not. The epic checklist is in the issue body.
[loop:torbscript] claim refine by session:loop-torbscript-20261024 until 2026-10-24T03:20Z
[loop:torbscript] release refine: already refined as an epic (step 1 is #415, step 2 is filed after #415 lands); claimed by mistake. next: waiting (epic steps, #415)
Buffer.holdsClose(step 2 of #55, commit 1 of 2) #468Buffer.holdsClose(step 2 of #55, commit 1 of 2) #468[loop:torbscript] claim refine by session:loop-torbscript-20261024 until 2026-10-24T11:15:00Z
forpass over a flat list (step 2 of #58) #470[loop:torbscript] decided by the loop: step 2 is one issue, #470, two commits (pass + tests, then the docs record), cut by cursor (
ListIteratoralone first) if it grows; no split up front. Measurement criteria are taken verbatim from PERFORMANCE.md 5.1 decision 5 (done:list-iteratewithin 10% oflist-index's ratio in the same run, 24 allocations; did not help: above two thirds ofmain's time). Rebase order with #468 (shares theforlowering): #468 first, then #470 re-reads the cursor shape; no blocker either way.[loop:torbscript] refine: step 2 filed as #470 and marked ready, next: waiting (epic waits on its steps, #470 next). Tokens used: about 60k
[loop:torbscript] refine: step 2 filed as #470 and marked ready (decision in the comment above), next: waiting (epic waits on its steps, #470 next). Rebase order: #468 and #470 both touch the
forlowering; whichever lands second rebases.[loop:torbscript] close: both steps landed (#415 specification, #470 the counted for pass via PR 475, merge commit
22cf1658f2on main, before/after in PERFORMANCE.md round P11 from the tier B run noted in #470), main CI green. Epic checklist ticked, closing. next: closed