Design 025: batch programs (132's A), the block's facts once at load and only values each batch: knapsack's per-batch cost measured at 0.90 us, 38% of its 11.5 ms (BATCH 1024 against 256 under a sampled profile: re-reading the block about 39%, value kinds 26%, list facts and dependence 22%, dispatch 14%), sum0's 0.33 us, matmul's inner-round dispatch about 13 ms and float-checked arithmetic about 22; five stages (facts at load, static kinds and list facts once a batch, typed kernels, fewer passes, the tails) with bars from those shares; 041 batch-costs data

1 files changed, 179 insertions, 0 deletions

diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md
new file mode 100644
index 0000000..ce8fe6f
--- /dev/null
+++ b/docs/design/025-batch-programs.md
@@ -0,0 +1,179 @@
+# 025 — 묶음 프로그램: 블록은 로드 때 한 번 읽고, 묶음마다는 값만 본다
+
+작성일: 2026-10-08. 상태: 설계. [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번
+만든다")이고, [132](../research/132-batch-executor-floor-and-the-way-past.md)의 A, [133](../research/133-register-tiles-measured.md)이
+정한 길이다. 사용자의 방향: 범용 장치로, 합친 연산의 표 없이, 기계어 없이, 메모리를 적게(2026-10-05, 2026-10-08).
+
+## 쉬운 말로
+
+- 묶음 실행기는 묶음 하나를 열 때마다 루프의 블록을 처음부터 다시 읽는다. 어느 지역 변수를 쓰는지, 점화식과 칸에 더하기가
+  어디 있는지, 이 `LOCAL_LOAD`가 모으기의 앞인지, 같은 코드의 값이 어디서 오는지를 다시 찾고, 명령마다 값의 꼴(균일·아핀·레인)을
+  다시 묻는다. 블록은 바뀌지 않으니 답도 매번 같다.
+- 배낭에서 이 값이 묶음 하나에 0.90 µs, 시간의 38%다(11.5 ms 가운데 4.4). matmul은 같은 일을 묶음이 아니라 안쪽 회차(k)마다
+  한다(메시지 하나에 4만 번). 132는 이 값을 "묶음마다 6,500 명령"이라 적었는데, 세 번 돈 수를 한 번의 묶음 수로 나눈 것이었다.
+  고쳤다: 작은 블록에서 약 2,300 명령(0.33 µs)이다.
+- 그래서 사실을 둘로 가른다. **블록의 모양에서 나오는 것**은 로드 때 루프마다 한 번 셈해 둔다(묶음 프로그램). **값에서 나오는
+  것**(레인이 4바이트에 드는지, 열의 폭, 경계, 의존 거리, 고를 레인)만 묶음마다 본다.
+- 그 위에서 연산을 꼴과 폭에 맞춘 루프로 돌리고(예: 균일한 값을 더하는 모으기는 레인을 돌지 않고 `v × n`, 4바이트 곱하기),
+  읽기를 피연산자로 받아 훑기의 수를 줄인다(배낭 6에서 3).
+- 합친 연산의 표, 레지스터 타일, 기계어는 쓰지 않는다. 메모리는 루프마다 블록 길이쯤의 표가 는다.
+
+## 잰 것: 값이 어디에 있는가
+
+방법. `b9`의 코어(`735ba81`; 그 뒤의 커밋은 문서와 헤더 하나)를 묶음 레인 1024와 256으로 빌드해(gcc `-O2 -g`, `module-batch.c`는
+`-O3`), `suite-run`을 `PURE_JIT=0`으로 돌리며 2 kHz로 표본을 떴다. 줄마다의 표본을 같은 프로세스에서 도는 C(6.24 ms)의 표본으로
+ms로 바꾸고, 두 빌드의 차를 묶음 수의 차로 나눴다. 원본은 `041-batches/2026-10-08-batch-costs.jsonl`이다.
+
+### 배낭: 묶음마다 0.90 µs, 시간의 38%
+
+배낭은 메시지 하나에 회차 4,949,075개를 레인 1024로 4,886 묶음, 256으로 19,376 묶음에 돈다. 시간은 11.49와 24.56 ms다.
+(24.56 − 11.49) / 14,490 = **0.90 µs**가 묶음마다이고, 1024 레인에서 4,886 × 0.90 = 4.4 ms다. 그 13.6 ms(표본의 합)를 나누면:
+
+| 갈래 | 무엇 | 몫 |
+|---|---|---:|
+| 블록 다시 읽기 | `recurrences` 1.58, `sums` 0.82, `batch_run`의 쓰는 지역 변수 훑기와 앞뒤 약 1.1, `pass`의 명령마다 찾기(칸에 더하기·점화식·같은 코드의 값·기록) 1.34, `local_load`의 모으기 앞 검사 0.12, 걸러내기 버퍼 놓기 0.30 (`batch_run`의 몫 가운데 일부는 남는다) | **약 39%** |
+| 값의 꼴 | `whole`·`whole32` 0.75(`floor`를 PLT로 부른다), `word_op`·`binary`·`affine_op` 1.15, `local_load`·`local_store` 1.0, `item_get` 0.37, `branch`·`arrive` 0.35 | 약 26% |
+| 리스트의 사실과 의존 | 리스트 쪽(`pure_list_cells`, 키 찾기) 0.80, `rows_in` 0.57, `find` 0.53, `read_of` 0.47, `settle` 0.39, `reads_set`·`cells_at` 0.28 | 약 22% |
+| 명령 디스패치 | `pass`의 나머지 1.40, 그 밖 | 약 14% |
+
+하나하나는 작고, 다 "블록을 읽어 정해진 사실을 다시 셈하기"이거나 "묶음에 한 번이면 될 것을 명령마다 하기"다. 배낭의 요소마다
+(훑기 여섯)는 회차당 약 2.9 사이클로 이미 꽉 짠 루프에 가깝다(나머지 7.1 ms 가운데 약 1 ms는 항목과 표를 만드는 일).
+
+### sum0: 묶음마다 0.33 µs
+
+`costs/sum0`(`total = total + 1`, `let` 둘)을 4M 회차로 돌리면 1024와 256 레인이 8.63과 12.54 ms다. 묶음 11,718개의 차로 나누면
+0.33 µs다(`icount`로는 2,330 명령, 805 사이클). 블록 다시 읽기(`recurrences` 훑기, 쓰는 지역 변수 훑기, `pass`의 찾기, 모으기 앞
+검사)가 약 34%, `whole`이 8%다. 점화식이 없는 블록도 점화식을 찾느라 블록을 두 번 훑는다.
+
+같은 프로파일이 다른 것도 보인다. 이 루프 시간의 약 80%가 모으기다. `total = total + 1`에 레인마다 부분합을 놓고(`reduction`),
+더하고(`reduce_step`), 크기와 함께 접는다(`fold`). 훑기 셋이다. 기계어는 더하기 하나다.
+
+### matmul: 안쪽 회차마다의 디스패치와 실수 검사
+
+matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 200개뿐이지만 `pass`가 안쪽 회차마다 몸체를 다시 해석한다(4만 번).
+표본으로 `pass` 16%, `sweep` 4.6%, `find` 2.7%, `affine_of` 2.2%, 리스트의 사실 1.5%, `nested` 1.3%, 합 약 13 ms(안쪽 회차마다
+약 0.3 µs)다. 나머지 큰 몫은 연산이다. 1바이트 열에서 읽은 값을 곱하고 더하는데, `words_op`에 곱하기가 없어 8바이트 실수로
+바꾸고(`numbers` 3 ms) 유한 검사를 하는 실수 연산으로 간다(`binary` 약 17 ms).
+
+### 다른 일
+
+- **BFS**(24.0 ms): 묶음마다의 값이 작다((26.0 − 24.3)/3 = 0.6 ms). 간선당 112 명령은 레인 훑기 약 45, 노드마다 약 20, 후보마다
+  약 26이다(131).
+- **roots**(8.97): 묶음마다 약 0.6 ms((10.8 − 8.97)/3).
+- **join**(117): 묶음마다 약 3 ms. 점화식 `x`를 회차마다 해석하는 값이 약 20%(차례가 있는 사슬이라 바닥에 가깝다), 칸에 더하기의
+  꼬리가 약 10%(회차마다 열의 폭을 가른다), 키로 찾기(리스트 쪽)가 약 13%다.
+- **sort**와 **words**는 리스트 쪽 정렬과 텍스트라 이 설계 밖이다.
+
+## 사실의 두 갈래
+
+| 블록의 모양에서 (로드 때 한 번) | 값에서 (묶음마다) |
+|---|---|
+| 블록이 쓰는 지역 변수와 쓰는 자리, 항목을 쓰는지 | 레인 값이 4바이트에 드는지(넘치면 8바이트로, 지금처럼 커널이 알린다) |
+| 점화식: 갱신과 걸음, 걸음의 피연산자가 어디서 오는지, 기록과 그 짝 | 점화식의 처음 값, LOAD·필드·바깥 지역 변수의 값 |
+| 칸에 더하기의 자리(again, add, set) | 열의 폭(묶음 끝에서 넓어질 수 있다), DENSE인지, 개수 |
+| 모으기: 어느 `LOCAL_LOAD`가 `x = x op e`의 앞인지 | 균일 값의 부호(아핀 곱), 경계 안인지, 읽기와 쓰기의 의존 거리 |
+| 같은 코드의 값(다시 쓰기, 쥐기), 걸러내기, 가드, 펼치기 | 고를 레인(¼ 아래인지), 가드가 허락하는 회차 |
+| 명령마다 결과의 꼴: 균일·아핀·레인 (값이 정하는 자리는 "아핀 또는 레인") | 그 꼴에서 고를 커널(꼴 × 폭) |
+
+## 설계
+
+### 1단계: 블록의 사실을 로드 때 (`PureBatchPlan`)
+
+모듈을 읽을 때 `plan_folds`가 묶음 루프(`PLAN_BATCH`)를 정한 뒤 루프마다 계획 하나를 만든다. 계획은 모듈에 있고(루프의 `LOOP`
+명령의 pc로 찾는다), 만든 뒤에는 읽기만 하므로 보기의 스레드들이 함께 쓴다.
+
+- 블록이 쓰는 지역 변수(비트 256개)와 항목을 쓰는지. `batch_run`의 훑기가 없어진다.
+- 점화식: 갱신마다 (from, set, x)와 걸음 (op, a, c). 걸음의 피연산자는 "자리"로 적는다: 상수(값까지 로드 때), 필드, LOAD, 블록이
+  쓰지 않는 지역 변수, 루프 변수, x, 앞 걸음. 묶음을 열 때는 자리에 값만 채운다. `recur`의 `actions[]`도 계획에 있다. 점화식의
+  다른 읽기(기록)의 pc와 함께 쓰는 짝도.
+- 칸에 더하기: (again, add, set, 리스트, 필드).
+- **블록의 pc마다 몫 한 바이트**: 보통, 칸에 더하기의 again·add·set, 점화식의 from, 기록, 같은 코드의 값(다시 쓰기·쥐기), 모으기의
+  앞(`pure_batch_reduces`의 답은 따로 pc 하나). `pass`는 선형 찾기 넷 대신 이 바이트 하나를 본다.
+- 작은 손질: `whole`이 `floor`를 부르지 않게(같은 뜻을 정수 변환으로), 걸러내기 버퍼는 쓴 묶음만 놓는다.
+
+묶음마다 남는 일: 값 채우기, 버퍼와 마스크, 미룬 효과, 검사. 메모리는 루프마다 블록 길이의 바이트와 점화식 걸음(최대 96개) 등
+수 KB 아래다.
+
+**맞음.** 1단계는 같은 사실을 다른 때 셈할 뿐이다. 만드는 동안 시험 빌드에서 묶음을 열 때 옛 셈을 함께 하고 계획과 견줘 다르면
+멈추게 한다(`PURE_BATCH_CHECK`). 무작위 시험과 고정 소스가 이 견줌을 다 지나면 옛 셈을 지운다. 두 길을 남기지 않는다.
+
+### 2단계: 값의 꼴을 로드 때, 리스트의 사실은 묶음에 한 번
+
+- **정적 꼴.** 블록의 pc마다 결과가 균일·아핀·레인 가운데 무엇인지 로드 때 셈한다. 루프 변수는 아핀, 블록이 쓰지 않는 지역
+  변수와 LOAD·필드·상수는 균일, 균일과 아핀의 더하기·빼기는 아핀, 양수 균일과 아핀의 곱은 아핀(부호는 값이라 묶음을 열 때
+  확인하고, 아니면 지금처럼 레인), 레인에서 읽은 것은 레인. 지금 `pass`가 묶음마다 하는 꼴의 셈과 같은 규칙이다.
+- **균일과 아핀의 조각은 스칼라 걸음으로.** 키의 셈(`c - it.weight`, `i * go.n + k`)처럼 균일과 아핀만으로 된 조각을 점화식의
+  걸음처럼 스칼라 목록으로 만들어 묶음마다 한 번 돈다. 명령마다 `Val`을 만들고 꼴을 묻는 일이 없어진다.
+- **리스트의 사실은 묶음에 한 번.** 칸의 자리와 폭, DENSE인지, 개수, 키의 첫 행은 묶음을 열 때 리스트마다 한 번 가져온다. 읽기의
+  기록(`read_of`, 의존 검사에 쓰는 것)도 계획에 자리가 있다.
+- **커널은 묶음을 열 때 고른다.** 레인 연산은 지금의 커널을 쓰되, 어느 것인지는 (정적 꼴 × 그 묶음의 폭)으로 정한다. 4바이트
+  커널이 넘침을 알리면 지금처럼 8바이트로 다시 한다.
+- **버퍼.** 값마다의 버퍼 자리를 로드 때 정해 `fresh`·`release`·`sweep`이 빈 버퍼를 찾지 않게 한다. 고르기와 같은 코드의 값이
+  버퍼를 쥐는 규칙과 맞물리므로 1단계를 잰 뒤에 정한다.
+
+### 3단계: 꼴과 폭에 맞춘 커널
+
+표가 아니라 연산 하나하나의 타입 변형이다.
+
+- **4바이트 곱하기.** `words_op`에 곱하기(64비트 곱으로 넘침 검사). matmul의 곱과 더하기가 4바이트 레인에 머문다.
+- **모으기.** 균일한 e를 모든 레인에서 더하면 `result += e × n`(e가 정수이고 크기가 2^53 아래일 때. 아니면 지금처럼 레인마다).
+  4바이트 레인의 e는 64비트 정수로 더한다(크기 검사 없이 정확).
+- **좁은 열.** 1·2바이트 열을 4바이트 레인으로 바로 읽는다(8바이트로 거치지 않는다).
+- 점화식은 차례가 있는 사슬이라 그대로 둔다.
+
+### 4단계: 훑기의 수
+
+- **보폭 읽기를 피연산자로.** 열(시작, 보폭, 폭)을 값의 꼴 하나로 두고, 그것을 받는 연산이 열에서 바로 읽는다. 레인 배열로
+  옮기는 훑기가 없어진다.
+- **비교가 레인을 센다.** 가르기 앞의 비교가 가는 레인의 수를 같은 루프에서 센다(`branch`의 세는 훑기가 없어진다).
+- 배낭은 훑기 6에서 3이다(더하기, 비교와 세기, 마스크 쓰기). 컴파일러가 합친 2(1.87 ms, `042-tiles`)는 천장으로 둔다.
+
+### 5단계: 꼬리 (132의 E)
+
+- 걸러내기 후보의 꼬리(후보당 약 250 명령: 기록 50, 결정 90, 넣기 110)를 리스트 쪽에서 한 번에 한다(폭 검사 한 번, 비트와 칸을 함께).
+- 칸에 더하기의 꼬리(join): 열의 폭을 묶음에 한 번 정하고 회차마다의 폭 가르기를 뺀다.
+
+## 하지 않는 것
+
+- 합친 연산의 표(사용자, 2026-10-08), 레지스터 타일(133: 모으기가 있는 몸체에서 진다), 기계어.
+- **레인 늘리기.** 묶음마다의 값을 레인 수로 나누는 쉬운 길이지만, 레인 버퍼가 스레드마다 24 × 1,048 × 8 B = 201 KB이고 4096이면
+  805 KB다. 메모리를 적게 쓰는 Pure의 생각과 맞지 않고, 묶음마다의 값을 없애면 필요 없다.
+
+## 막대
+
+단계마다 같은 방법으로 잰다(`041-batches/runs.sh`, 11번의 중앙값, 세 길과 명령 수). 묶음마다의 값은 레인 1024와 256 빌드의 차로 잰다.
+막대는 위의 몫에서 셈한 것이다.
+
+| 일 | 지금 (`b9`) | 1단계 | 2단계 | 3–4단계 | 5단계 | 천장 (041) | 기계어 | C |
+|---|---:|---:|---:|---:|---:|---:|---:|---:|
+| knapsack | 11.5 ms | ≤ 10.3 | ≤ 8.0 | ≤ 6.0 | | 4.55 (꽉 짠 두 훑기 1.87) | 7.9 | 6.25 |
+| matmul | 40.0 | ≤ 39 | ≤ 30 | ≤ 17.75 | | 17.75 | 14.2 | 7.6 |
+| BFS | 24.0 | ≤ 24 | ≤ 22 | ≤ 21 | ≤ 18 | 10.3 (꽉 짠 9.8) | 7.7 | 9.9 |
+| roots | 8.97 | ≤ 9.0 | ≤ 8.6 | | | 6.8 | 9.57 | 6.86 |
+| join | 117 | ≤ 116 | ≤ 115 | | ≤ 110 | 57.8 | 84.6 | 31.7 |
+| 묶음마다 (배낭) | 0.90 µs | ≤ 0.60 | ≤ 0.15 | | | | | |
+| 묶음마다 (sum0, `icount`) | 2,330 명령 | ≤ 1,550 | ≤ 600 | | | | | |
+
+- **knapsack.** 1단계는 블록 다시 읽기(묶음마다의 3분의 1 남짓, 약 1.5 ms)를 없애 약 10.0 ms다. 2단계는 묶음마다를 0.15 µs(0.7 ms)로 해서
+  11.5 − 4.4 + 0.7 = 7.8 ms다. 4단계의 훑기 셋은 요소마다 약 6 ms를 약 3.5로 줄여 약 5.3 ms다. 막대는 그보다 조금 느슨하다.
+  131에서 생긴 10%(b7 10.32)는 1단계에서 되찾는다.
+- **matmul.** 안쪽 회차마다의 디스패치 약 13 ms 가운데 1단계는 찾기(`pass`의 몫 일부)만, 2단계가 꼴과 리스트의 사실을 없애 약
+  3 ms로 한다(≤ 30). 3단계는 곱과 더하기를 4바이트로 해서 연산 약 22 ms를 약 9 ms로 한다(요소 8M × 약 2.5 사이클). 막대는 041의
+  천장이다.
+- **BFS.** 간선당 112 명령에서 노드마다 20을 약 10으로(1–2단계), 비교와 세기를 합쳐 약 5를(4단계), 후보의 26을 약 10으로(5단계)
+  줄이면 약 80 명령, 약 17 ms다.
+- **roots, join**은 묶음마다의 몫(0.6, 3 ms)과 join의 칸 꼬리(약 12 ms의 절반)만큼이다. join의 점화식(약 23 ms)은 그대로다.
+- **지키는 것.** 묶음 루프가 없는 모듈의 실행기는 명령 수가 그대로(`rounds` 길), TPC-C와 은행 질의는 기준(3%, 1%) 안.
+
+## 맞음과 단계마다의 시험
+
+단계마다 같은 묶음을 돈다: 무작위 프로그램 시드 1, 2, 3, 5, 23(기본과 `PURE_SELECT=all`), 고정 소스 여섯(`BATCH`, `NESTED`,
+`RECUR`, `APPEND`, `FRONT`, `GRAPH`)의 세 길, 단위 시험 세 모드와 ASan, sanitized `pure-run`, aup의 검사 두 모드, `make check`,
+스위트의 세 길과 명령 수. 1단계는 `PURE_BATCH_CHECK`의 견줌을 더한다. 2단계는 정적 꼴이 지금의 동적 꼴과 같은지를 같은 방법으로
+견준다(시험 빌드에서 둘 다 셈하고, 다르면 멈춘다). 견줌은 단계가 끝나면 지운다.
+
+## 단계의 차례
+
+1단계는 뜻을 바꾸지 않고 묶음마다의 3분의 1을 없앤다. 2단계가 이 설계의 몸통이고, 1단계의 계획 위에 선다. 3–4단계는 커널과
+값의 꼴을 늘리는 일이라 2단계의 정적 꼴이 있어야 깔끔하다. 5단계는 독립이라 언제든 할 수 있다. 1단계를 잰 뒤 2단계의 버퍼와
+조각의 자리를 다시 정하고, 이 문서에 적는다.