Research 126: the batch executor's first stage (024) as built and measured: knapsack 1,041 to 13.6 ms in the executor (the compiled code 7.5; its inner loop 1.17x the tier's, the stage's criterion missed; the table's adds left to stage 4), the executor without batch loops unchanged; what measuring overturned (a call among the steps cost 20% of the instructions, so two copies; run aligned to 64 for its cycles; results apart from operands for vector code); tests; 1024 lanes, 134 KB a thread; 024 and CHECKPOINT say so

1 files changed, 100 insertions, 0 deletions

diff --git a/docs/research/126-batch-executor-stage-one.md b/docs/research/126-batch-executor-stage-one.md
new file mode 100644
index 0000000..f51b050
--- /dev/null
+++ b/docs/research/126-batch-executor-stage-one.md
@@ -0,0 +1,100 @@
+# 126 — 묶음 실행기 1단계: 기계어 없이 세는 루프를 회차 1024개씩
+
+2026-10-05. [024](../design/024-batch-executor.md)의 1단계를 만들고 잰 것. 코드는 `core/module-batch.c`이고(`1513463`), 측정 스크립트와
+원시 결과는 [041-batches](../../research/experiments/041-batches/)에 있다(`runs.sh`, `2026-10-05-suite.jsonl`,
+`2026-10-05-counts.jsonl`). 묶음은 `suite-run` 11번의 중앙값이다. 같은 빌드를 세 가지로 돌렸다. 하나는 기계어(JIT), 하나는 묶음을 쓰는
+실행기(`PURE_JIT=0`), 하나는 실행기만(`PURE_BATCH=0`까지)이다.
+
+## 쉬운 말로
+
+- **실행기가 세는 루프를 회차 1024개씩 돈다.** 루프의 몸체를 회차마다 해석하지 않는다. 명령 하나를 회차 1024개(레인)에 한 번에 한다.
+  연산은 빌드 때 C 컴파일러가 만든 루프이고, 실행 시간에 만드는 코드는 없다. knapsack이 실행기만으로 1,041 ms였는데 묶음으로 13.6 ms가
+  된다(77배). 기계어(023의 계층)는 7.5 ms, C는 6.2 ms다.
+- **1단계의 기준은 아직 못 맞췄다.** 기준은 "계층보다 느리지 않다"였다. 안쪽 루프만 보면 묶음이 약 8.5 ms, 계층이 약 7.2 ms로 1.17배다
+  (둘 다 바깥 부분을 뺀 값이다). knapsack 전체로는 1.8배다. 차이의 대부분은 표를 만드는 바깥 루프다. `table.add`를 5만 번 하는 이
+  루프는 묶을 수 없어서(덧붙이기는 4단계) 실행기에서 5.1 ms가 든다. 계층에서는 0.3 ms다.
+- **묶음이 없는 모듈의 실행기는 그대로다.** 명령 수와 사이클이 `e01dae9`와 같거나 조금 적다(roots 27.56억 대 27.60억 명령, 사이클은
+  같다). 여기까지 오는 데 측정이 세 번 짐작을 뒤집었다(아래).
+- **어떤 루프를 묶는가.** 몸체의 명령이 모두 레인 꼴을 가진 세는 루프를 묶는다. 레인 꼴은 fold가 쓰는 `has_lanes`와 같다. 그 밖에
+  허락하는 것은 회차마다 먼저 쓰고 읽는 지역 변수, `if`와 `else`, 수 칸에 쓰기다. 합 같은 누적, 점화식, 중첩 루프, `break`, 덧붙이기,
+  텍스트, i64가 있으면 묶지 않는다. 그래서 일곱 가지 일 가운데 지금은 knapsack만 묶인다. roots(`break`), matmul(합), join(점화식),
+  BFS(덧붙이기)는 2–5단계의 몫이다.
+
+## 묶음
+
+| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C |
+|---|---:|---:|---:|---:|
+| knapsack | 7.52 ms | **13.57** | 1,040.9 | 6.23 |
+| roots | 9.58 | 130.6 | 130.5 | 6.86 |
+| matmul | 14.23 | 914.8 | 914.8 | 7.50 |
+| join | 74.2 | 428.4 | 427.2 | 28.6 |
+| sort | 36.9 | 78.2 | 82.5 | 26.9 |
+
+`suite-run` 세 바퀴의 사용자 모드 명령 수(`icount.c`, perf_event_open):
+
+| 일 | `e01dae9` 실행기 | `1513463` 실행기만 | `1513463` 묶음 |
+|---|---:|---:|---:|
+| roots | 27.60억 | 27.56억 | 27.56억 |
+| knapsack | 219.05억 | 216.88억 | **4.60억** |
+| matmul | 214.62억 | 214.36억 | 214.36억 |
+| join | 77.15억 | 76.69억 | 76.69억 |
+| sort | 15.13억 | 15.02억 | 15.02억 |
+
+knapsack의 안쪽 루프 하나(500만 회차)에 묶음이 쓰는 시간은 회차당 약 1.7 ns다. 레인을 한 번 도는 일 여섯 가지가 대부분을 차지한다.
+거꾸로 읽기 둘, 덧셈과 넘침 검사, 비교, 마스크의 개수 세기, 마스크를 단 저장이다. 그 밖에 묶음마다 명령을 해석하는 고정 값이
+약 500 ns다. 묶음을 256 레인으로 하면 21.6 ms, 512면 16.4, 1024면 13.7 ms였다.
+
+## 만들며 정한 것
+
+- **값의 꼴.** 값은 세 가지 꼴로 든다. 모든 회차에 같은 값(균일), 회차마다 정수 보폭으로 움직이는 정수(아핀), 회차마다의 값(레인)이다.
+  레인은 수(8바이트)이거나, 2^32 아래의 정수(4바이트)다. 아핀 값의 덧셈, 뺄셈, 양수 곱셈은 O(1)이다. 아핀 키로 DENSE 리스트를 찾으면
+  양 끝만 검사하고, 그 칸을 읽는 것은 열을 보폭으로 읽는 것이 된다. 아핀 값은 정수이고 2^52 안이며 −0이 아니어야 한다. 그래야 레인마다의
+  값이 회차마다 계산한 값과 비트까지 같다(−0의 부호 포함). 음수를 곱하거나 부호를 바꾸면 레인으로 계산한다.
+- **분기.** 레인 조건의 `if`는 두 길을 다 돈다. 각 길은 제 레인(마스크)으로만 돈다. 마스크는 갈라진 부모와 짝을 알아서, 두 길이 다시
+  만나면 계산 없이 부모로 돌아간다. 비교의 0/1 레인이 그대로 마스크가 된다. 돌지 않는 레인의 결함은 결함이 아니다.
+- **쓰기는 끝에.** `ITEM_SET`은 묶음의 끝까지 미룬다. 묶음의 어떤 회차도 앞선 회차가 쓴 칸을 읽지 않을 때만 쓴다. 아핀 행끼리는 보폭이
+  같으면 O(1)로, 다르면 O(n)으로 검사한다. 같은 열에 두 번 쓰면 두 쓰기의 차례가 회차와 엇갈리는지도 본다. 열이 좁으면 먼저 넓히고 쓴다.
+  넓히는 것은 항목을 바꾸지 않는다.
+- **실패하면 그 회차들을 실행기에.** 결함, 꼴이 없는 값, 읽기와 쓰기의 겹침이 있으면 묶음은 아무것도 바꾸지 않았다. 그 회차들은 실행기가
+  하나씩 돌아서 결함이 제 회차에서 난다. 그 뒤 묶음을 다시 시도하고, 한 루프에서 세 번 실패하면 그만둔다. 남은 작업량이 두 회차를 덮지
+  못할 때도 한 회차를 실행기에 넘긴다. 처음에는 넘기지 않아서 작은 예산의 시험에서 무한 루프가 됐다.
+- **레인의 방향.** 거꾸로 가는 접근이 더 많으면 다음 묶음부터 레인을 거꾸로 번호 매긴다. 그러면 읽기와 쓰기가 메모리의 차례가 된다.
+  의존 검사와 쓰기의 차례는 레인이 아니라 회차로 센다.
+- **로드 때 거르기.** 회차를 넘어 이어지는 지역 변수(쓰기 전에 읽는 것)가 있는 루프는 로드 때 계획에서 뺀다. 처음에는 실행 중에만
+  알아서, 무작위 프로그램에서 묶음 실패의 99.9%(3만 5,752번)가 이것이었다.
+
+## 측정이 뒤집은 것
+
+1. **실행기 루프에 호출 하나가 명령 20%였다.** `step`의 LOOP 케이스에 묶음으로 가는 호출을 두자 roots의 명령이 27.6억에서 33.1억이
+   됐다. 묶음은 쓰이지도 않았다. 원인은 `run`의 레지스터 할당이었다. `&frame`이 인라인되지 않는 함수로 넘어가면 Frame의 필드가 모두
+   메모리로 가고, 디스패치마다 스택 기준을 다시 읽고 `pc`를 메모리에 쓴다. 그래서 실행기를 두 벌로 나눴다. 묶음 루프가 없는 모듈은
+   지금과 같은 코드를 돈다(`step`의 묶음 인자가 상수 false로 접힌다). 묶음 루프가 있는 모듈만 사본 `run_batches`를 돈다. 사본은 묶음
+   경로에 Frame의 복사본을 넘긴다. 사본에서 묶음이 아닌 코드는 명령 +2%다.
+2. **같은 명령 수, 사이클 +10%.** 두 벌로 나누자 명령 수는 같아졌는데 사이클이 10% 많았다. `run`의 시작 주소가 64바이트 경계에서
+   8바이트 경계로 밀렸기 때문이다. `run`을 64바이트에 맞추자 사이클도 같아졌다.
+3. **벡터화된 루프의 값.** 산술 루프가 느린 것을 처음에는 벡터화가 안 된 탓으로 봤다. 실제로는 결과를 입력 레인에 다시 쓰게 해서 gcc의
+   실행 시간 별칭 검사가 스칼라 경로로 떨어진 것이었다. 결과를 늘 새 레인에 쓰고(`restrict`), 다 쓴 레인을 빈 목록으로 돌려쓰게 했다.
+   레인 버퍼의 캐시 연관도 충돌도 의심했지만, 버퍼 사이를 엇갈리게 해도 같아서 원인이 아니었다.
+
+## 뜻과 맞음
+
+- `module_tier`가 `PURE_JIT=0`(묶음)과 `PURE_BATCH=0`(실행기만)도 견준다. 상태, 결함, 오류, 작업량이 바이트까지 같아야 하고, 작은 예산
+  넷도 돈다. 생성기에 회차가 서로 떨어진 루프(`lanes`)를 더했다. 몸체 안의 `let`, 아핀 키로 `t`에 쓰기, 조건과 `else`를 섞는다. 시드
+  1, 2, 3, 23의 프로그램 553개가 같았다. 시드 23에서는 139개 중 19개 모듈에서 묶음 884개(53,924 회차)가 돌았다.
+- `module_assumptions`에 `BATCH_SOURCE`를 더했다. 넓어지는 열(1바이트 → 4 → 8), 묶음 한가운데의 분수와 −0, 회차 q에서의 0 나누기,
+  앞 회차의 쓰기를 읽는 루프(묶음이 실패하고 실행기가 돈다), 거꾸로 가는 키와 `if`/`else`, 한 열에 두 번 쓰기를 담았다. 세 길(묶음,
+  실행기만, 기계어)이 같다.
+- 단위 시험은 세 JIT 모드와 ASan(실행기 모드)에서 통과했고, aup의 검사는 실행기와 기본 모드에서 통과했다. sanitized `pure-run`으로
+  무작위 프로그램 139개와 `BATCH_SOURCE`를 돌려도 오류가 없었고, 출력은 실행기만으로 돈 것과 같았다.
+
+## 메모리
+
+레인 버퍼는 16개 × 1024 × 8바이트 = 약 134 KB다. 스레드의 정적 TLS에 있고, 묶음을 도는 스레드만 그 페이지를 쓴다. 024가 적은
+32 KB(256 레인)보다 크다. 묶음마다의 고정 값을 나누려고 고른 크기다.
+
+## 다음
+
+- **2단계: 중첩 루프와 모으기.** matmul과 roots는 바깥 루프의 회차를 레인으로 삼고 안쪽 루프를 함께 돌아야 한다. matmul은 횟수가 같고,
+  roots는 `break`로 레인이 빠진다. 합(`total = total + s`, `count = count + 1`)은 회차의 차례대로 모은다.
+- **합친 연산.** knapsack 안쪽의 1.17배는 레인을 여섯 번 도는 값이다. 041의 시제품에서는 합친 연산이 1.7배였다.
+- **덧붙이기(4단계).** knapsack 전체의 1.8배는 대부분 실행기에서 도는 `table.add` 루프다.