Design 024: a batch executor, loops run 256 rounds at a time by operations the C compiler makes at build time (no code made at run time, 32 KB of lanes), checks as a batch's flag and a failed batch run again round by round; which loops batch (sums, affine keys at a nonnegative distance, filters that only grow, a count that only grows), sections run round by round interpreted, fused operations from a table, the JIT retired if it is not slower; 041's prototypes against C: roots 0.99, knapsack 0.71, matmul 0.94, BFS 1.03, join 1.59 (the tier 1.20-2.46); CHECKPOINT says so

1 files changed, 136 insertions, 0 deletions

diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md
new file mode 100644
index 0000000..233241c
--- /dev/null
+++ b/docs/design/024-batch-executor.md
@@ -0,0 +1,136 @@
+# 024 — 묶음 실행기: 기계어 없이 루프를 C 가까이
+
+작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 구현 전.
+
+[023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을
+C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만
+돈다. 사용자는 새 JIT를 원하지 않는다. Pure의 생각대로 메모리를 적게 쓰고, 지금의 JIT도 더 나은 길이 없을 때만 둔다(2026-10-05).
+
+이 설계는 해석의 값을 **회차마다가 아니라 묶음마다** 낸다. 루프의 몸체를 연산 몇 개의 프로그램으로 만들고, 연산 하나를 회차
+256개(레인)에 한 번에 한다. 연산 하나하나는 빌드 때 C 컴파일러가 만든 루프다(NEON으로 벡터화된다). 실행 시간에는 코드를 만들지
+않는다. 뜻의 검사(2^53 아래의 정수, 유한한 수, 열에 맞는 칸)는 묶음 전체의 깃발 하나로 모은다. 검사가 하나라도 실패하면 그 묶음을
+실행기가 처음부터 회차마다 다시 돈다. 실행기만으로는 roots가 131 ms, 배낭이 1,058 ms, 행렬 곱이 916 ms였다. 같은 일을 묶음의
+연산으로 하면 C와 비슷해진다.
+
+## 산수: 시제품 (041)
+
+모두 Pi 5(Cortex-A76 2.4 GHz), 조용한 기기, 한 프로세스에서 번갈아 11번 돈 중앙값을 세 번(`2026-10-05-batches.jsonl`)이다. 답은
+매번 C와 같다. 견주는 C는 두 가지다. 하나는 `natural.h`의 C를 크기가 상수가 아닌 채로 돈 것이고(칸은 미리 만든다), 다른 하나는
+묶음이 받은 재구성(루프 바꾸기, 4바이트 칸, 벡터화)을 C에도 준 것이다. 계층은 `e01dae9`의 `suite-run`이다(C는 칸 만들기를 포함).
+
+| 일 | C | 재구성을 받은 C | 묶음 | 묶음 / C | 계층 / C |
+|---|---:|---:|---:|---:|---:|
+| roots | 6.86 ms | — | 6.79 | **0.99** | 1.39 |
+| knapsack, 연산 따로 (4바이트 레인) | 6.38 | 1.97 (묶음의 블록, −O3) | 4.54 | **0.71** | 1.20 |
+| knapsack, 합친 연산 | | | 2.71 | 0.42 | |
+| matmul, 합친 연산 (j 레인) | 7.09 | 4.89 (j·k 바꿈, 4바이트, −O3) | 6.68 | **0.94** | 1.90 |
+| matmul, 연산 따로 (j 레인 / k 레인) | | | 17.7 / 22.1 | 2.50 / 3.11 | |
+| join, 점화식을 C로 | 28.8 | — | 36.5 | 1.27 | 2.46 |
+| join, 점화식을 해석 (역수 준비) | | | 45.7 | **1.59** | |
+| BFS | 9.97 | 7.02 (미리 읽기) | 10.28 | **1.03** | 1.61 |
+
+- 굵은 값(배낭은 연산 따로, 행렬 곱은 합친 연산)에 sort 1.37과 words 5.58을 그대로 두면 기하 평균이 **1.35**다. 계층은 1.92다.
+  배낭도 합치면 1.26이고, 합친 연산이 하나도 없으면(matmul 2.50) 1.56이다. 재구성을 받은 C와 견주면 1.65–1.77이다. words를
+  빼면(보류) 1.07이다.
+- 023의 기준(일마다 1.25배 안)을 넘는 것은 join(1.59), sort(1.37), words(5.58)다. sort는 런타임의 기수 정렬이고 words는 보류라,
+  묶음의 몫이 아니다. join의 남은 몫은 아래 "회차마다 도는 부분"에 있다.
+- 배낭의 0.71과 0.42는 C를 이긴 것이 아니다. gcc가 자연스러운 배낭 루프를 벡터로 만들지 못한 것이다(거꾸로 가는 루프, −O3와
+  ivdep를 줘도 9.5 ms). 같은 블록으로 쓴 C는 1.97 ms다. 묶음이 이기는 것은 실행 시간에 확인한 독립(아래)이다.
+- 행렬 곱의 C는 하네스마다 다르다. `suite-run`은 7.44 ms이고(칸 만들기 포함, n은 실행 시간), 처음의 시제품은 n=200이 상수로
+  인라인돼 4.9 ms였다. 위 표는 n을 실행 시간에 읽는다.
+
+**시제품은 천장이다.** 묶음 프로그램은 손으로 짰다(컴파일러가 낼 순서). 작업량을 세지 않고, 적재의 꼴 검사(열의 폭, DENSE의
+빈틈)를 하지 않으며, 실패 뒤 다시 도는 길을 돌려 보지 않았다. roots는 해석기의 디스패치 없이 연산마다 살아 있는 레인을 도는
+루프다. 디스패치를 더해도 묶음 391개 × 걸음 64 × 연산 4로 10만 번 아래다. knapsack의 두 묶음과 matmul의 k·j 레인은 해석기가
+연산마다 디스패치한다.
+
+## 왜 되는가
+
+1. **디스패치가 256으로 나뉜다.** 실행기의 값은 명령마다 내는 디스패치와 값 꺼내기였다. 묶음에서는 연산 하나가 레인 256개를 돈다.
+2. **검사가 분기가 아니라 깃발이다.** `forms.c`에서 적재마다 앞에 둔 분기(한 번도 타지 않아도)가 1.34배였다. 2^53 검사는 거의
+   공짜였다. 묶음에서는 검사가 OR로 깃발에 모이고, 적재 앞에 분기가 없다.
+3. **레인이 좁고 메모리의 차례다.** Pure의 열은 4바이트다. 4바이트 레인은 NEON에 넷이 들어간다. 배낭을 8바이트 레인과 거꾸로 가는
+   적재로 하면 11.2 ms, 4바이트 레인과 메모리 차례로 하면 4.54 ms다. 묶음 안의 회차가 서로 독립이면 레인의 차례는 자유다.
+4. **회차 사이의 병렬.** roots는 i마다 나눗셈의 사슬이다. C는 사슬 하나씩 돌아 나눗셈의 지연을 기다린다. 묶음은 사슬 256개를 섞어
+   지연을 겹친다. 같은 산수, i마다 같은 차례, 같은 검사다.
+5. **메모리 미스가 겹친다.** join의 탐사와 BFS의 비트 읽기는 레인마다 독립이라 미스가 함께 나간다.
+
+## 설계
+
+### 어떤 루프를 묶는가
+
+묶음 루프는 세는 루프(또는 리스트의 항목 루프)로, 회차의 쓰기가 같은 묶음의 뒤 회차의 읽기로 가지 않는 것이다. 다음은 허락한다.
+
+- **모으기.** 정수의 합은 정확해서 차례가 답을 바꾸지 않는다(넘치면 검사가 묶음을 다시 돌린다). 수(실수)의 합과 같은 키로의
+  흩어 더하기는 차례대로 하는 연산으로 한다.
+- **아핀 키의 읽기와 쓰기.** 같은 열을 레인 l이 `r0 + s·l`에서 읽고 `w0 + s·l`에 쓰면, 앞선 레인 l' < l의 쓰기를 읽는 것은
+  `l' = l + (r0 − w0)/s`일 때다. 그래서 거리 `d = (r0 − w0)/s`가 0 이상이거나 정수가 아니면 묶음 안에서 안전하다. 거리가 음수면
+  묶음의 크기를 |d| 아래로 한다. 배낭(용량을 거꾸로, `s = −1`, `r0 − w0 = −w`)은 거리가 무게 w ≥ 0이라 안전하다. 같은 배낭을 앞으로
+  돌면(무한 배낭) 거리가 −w여서 묶음이 w 회차로 줄어든다. 이 판정은 023의 BCE처럼 묶음을 열 때 실행 시간의 값으로 한다.
+- **커지기만 하는 걸러내기.** 루프가 리스트에 더하기만 하면(빼지 않으면) `has`는 한 번 참이면 계속 참이다. 그래서 묶음 전체에
+  `has`를 먼저 묻고, 거짓인 레인만 차례대로 다시 물어 더하고 덧붙인다(BFS).
+- **바뀌는 개수.** `if i >= queue.count { break }`처럼 회차의 시험이 커지기만 하는 값에 달려 있으면, 묶음을 열 때 시험이 서는 회차까지만
+  묶는다. 023의 계층이 하지 못한 BFS의 덧붙이기(개수를 바뀌는 SSA 값으로 다뤄야 했다)가 여기서는 묶음의 크기가 된다.
+
+묶음 루프 안의 루프는 레인이 함께 돈다. 횟수가 같으면 그대로 돈다(matmul의 k, 레인은 j). 횟수가 다르면 살아 있는 레인만
+모아 돈다(roots의 뉴턴 걸음과 `break`). 레인마다 항목이 다르게 나오면 그 항목을 자기 레인으로 펼친다(BFS의 간선). 묶음의 크기는
+`min(256, 남은 회차, 시험이 서는 회차, 의존 거리, 작업량이 덮는 회차)`다.
+
+### 회차마다 도는 부분
+
+`x = x * 48271 mod (2^31 − 1)`처럼 회차가 앞 회차의 값을 받는 점화식은 묶을 수 없다. 이 부분은 같은 연산 집합을 레인마다 차례로
+해석한다(계산된 goto). 결과는 레인마다 하나씩 남고, 나머지 몸체는 묶음으로 돈다. join에서 이 부분이 회차 110만에 9–14 ms였다.
+그 대부분은 상수로 나누는 정수 나눗셈의 지연이다. 프로그램을 만들 때 상수의 역수를 준비하면 4 ms를 던다. 이 부분이 C에 남은
+차이의 대부분이다(36.5 대 45.7). 기계어 없이 더 줄이려면, 자주 나오는 점화식의 꼴을 합친 연산으로 둔다(아래).
+
+### 연산
+
+- **레인 레지스터**는 타입이 있다: u32, i64(2^53 아래의 정수), f64. 폭은 023의 사실(열의 폭, 범위)에서 고른다.
+- **연산의 종류**: 검사하는 원소별 산수, 비교와 마스크, 고르기, 아핀 적재와 저장(보폭 ±1, k), 키로 모으기(DENSE는 키 자리,
+  HASHED는 탐사, FLAT은 위치), 차례대로 흩어 더하기, 모으기, 살아 있는 레인 모으기와 펼치기.
+- **합친 연산**은 빌드 때 스크립트가 꼴의 표에서 C 루프로 만든다(곱해 더하기, 더하고 최대로 저장, 읽고 비교해 고르기 같은 것).
+  묶음 컴파일러는 꼴이 맞으면 합친 연산을 쓰고, 아니면 따로 둔다. 재어 보니 합치면 배낭이 1.7배, 행렬 곱이 2.7배 빨랐다. 연산을
+  따로 두면 레인 배열(L1 안)을 연산마다 읽고 쓰기 때문이다. 기계어를 만드는 것과 달리 표는 유한하다. 그래서 어떤 꼴을 둘지는
+  묶음과 앱에서 나오는 프로그램을 세어 정한다.
+
+### 뜻
+
+- **같은 답.** 레인마다 자기 값을 검사한다. 묶음의 깃발이 서면 묶음을 시작한 상태에서 실행기가 회차마다 다시 돈다. 그래서
+  실패와 오류가 회차마다 돈 것과 같은 회차에서 난다. 이를 위해 묶음의 검사가 다 지나기 전에는 보이는 효과가 없다. 저장은
+  프로그램의 끝으로 내리거나 묶음의 버퍼에 두고, 깃발이 비었을 때만 쓴다. 더하기와 덧붙이기는 차례대로 도는 끝 부분에서 한다.
+- **같은 작업량.** 실행기는 회차마다 작업량을 센다. 묶음은 열 때 m 회차의 몫을 한꺼번에 내고, 예산이 모자라면 m을 줄인다.
+  `module_tier`처럼 작은 예산으로 답과 작업량을 회차마다 돈 것과 견준다.
+- **수의 차례.** 수의 합은 차례대로 한다(다시 묶지 않는다). 같은 수가 나온다.
+
+### 메모리
+
+레인 레지스터 16개 × 256 × 8바이트 = 32 KB를 이벤트 스레드 하나가 쓴다(L1 64 KB 안). 펼친 레인(BFS의 간선)도 256씩 끊어 같은
+자리를 쓴다. 묶음 프로그램은 루프마다 연산 수십 개 × 32바이트다. 실행 가능한 페이지도, 코드 캐시도 없다.
+
+### JIT와의 관계
+
+022의 JIT(copy 0/1)와 023의 계층은 기계어를 쓴다. 묶음 실행기는 C 컴파일러가 가는 곳 어디서나 같은 코드로 돈다. Mac과 WSL의
+x86에서도 연산은 그 기계의 벡터로 빌드된다. 023의 앞 절반(SSA, 사실, 아핀 키, 루프를 열 때의 검사)은 그대로 쓰고, 뒤 절반(레지스터
+할당과 기계어 내기)은 쓰지 않는다. 묶음 실행기가 묶음의 일과 앱에서 계층보다 느리지 않으면 JIT를 걷어낸다(022의 장부, 023의 내기).
+느린 곳이 남으면 그곳과 값을 적고 사용자에게 묻는다.
+
+## 단계
+
+1. 묶음 프로그램과 연산 모음(빌드 때 C), 실행기의 걸이. 023의 SSA에서 안쪽 세는 루프 중 아핀 적재·저장과 모으기만 있는 것을
+   묶는다(배낭의 꼴). 레인은 u32, i64, f64.
+2. 바깥 루프의 레인과 함께 도는 안쪽 루프(matmul의 j 레인, roots의 살아 있는 레인).
+3. 키로 모으기(DENSE, HASHED, FLAT)와 차례대로 흩어 더하기(join).
+4. 차례대로 도는 끝 부분: 더하기와 덧붙이기, 커지기만 하는 걸러내기, 열 때의 개수로 정하는 묶음의 크기(BFS).
+5. 회차마다 도는 부분의 해석과 준비한 역수(점화식).
+6. 묶음의 일과 앱(TPC-C, 은행 질의)을 계층과 견주고 JIT를 걷어낼지 정한다.
+
+단계마다 무작위 프로그램(`module_tier`의 생성기)으로 답과 작업량을 회차마다 돈 것과 견주고, 묶음 한가운데에서 실패하는 값을 섞는다.
+
+## 착수 기준
+
+- roots, knapsack, matmul, join, BFS 각각 계층(`e01dae9`)보다 느리지 않다. 목표는 C의 1.25배 안이다.
+- 무작위 시험에서 답과 작업량이 회차마다 돈 것과 같다(작은 예산과 묶음 한가운데의 실패를 섞어).
+- 이벤트 스레드 하나의 레인 자리가 64 KB 안이다.
+- TPC-C와 은행 질의가 잡음 안에서 그대로다.
+- **미리 밝히는 미달**: 시제품으로 보면 join은 점화식을 해석하는 한 1.25배를 넘는다(1.59). sort(런타임의 정렬)와 words(보류)는 이
+  설계로 바뀌지 않는다. 합친 연산의 표가 꼴을 덮지 못하면 행렬 곱 같은 일은 2.5배로 남는다.