1 files changed, 124 insertions, 0 deletions
diff --git a/docs/research/129-batch-executor-costs-cut.md b/docs/research/129-batch-executor-costs-cut.md
new file mode 100644
index 0000000..c807df1
--- /dev/null
+++ b/docs/research/129-batch-executor-costs-cut.md
@@ -0,0 +1,124 @@
+# 129 — 묶음 실행기의 값 줄이기: 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기, 그리고 BFS의 산수
+
+2026-10-06. [128](128-batch-executor-tables-and-costs.md)이 잰 값 가운데 셋을 줄였다. 덧붙이기 하나 약 100 ns, 점화식 한 회차 약
+60 ns, 모으기의 끝 회차당 4–9 ns다. 코드는 `4791c42`(덧붙이기), `9f0498b`와 `e8558e7`(점화식), `f9e3d22`(모으기)다. 128과 같은
+방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b5` = `f9e3d22`, `b6` = `e8558e7`, 11번의 중앙값; 작은 모듈은 `costs/`). 그리고 BFS를
+묶는 설계가 기준을 넘을 수 있는지 먼저 셈했다(`041-batches/frontier.c`).
+
+## 쉬운 말로
+
+- **기계어 없이 넷이 빨라졌다.** knapsack 15.1 → 10.8 ms, matmul 46.1 → 36.4, join 161 → 118, sort 74 → 55.5다. roots는 8.87 ms로
+  기계어(9.57)보다 빠르다. 기계어와의 차이는 knapsack 2.9 ms, matmul 22 ms, join 40 ms, BFS 89 ms로 줄었다.
+- **바꾼 것은 셋이다.** 묶음의 덧붙이기를 항목마다 실행기의 걸음으로 하지 않고 리스트의 한 호출로 한다. 점화식의 걸음은 스택이
+  아니라 번호 붙은 값 사이의 연산이다. 모으기의 끝은 차례가 답을 바꾸지 않는 곳(`min`, `max`, 2^53 안의 정수 합)에서 차례 없이
+  벡터로 합친다.
+- **BFS는 셈해 보니 가능성이 있다.** 프런티어를 묶음으로 돌면, 묶음을 열 때 `has`가 거짓이라 차례대로 다시 물어야 하는 간선이 100만
+  개 가운데 약 10만 5천 개다. 이 꼬리를 실행기가 아니라 묶음의 C로 하면 1 ms 안팎이다. 다만 레인마다 간선 수가 달라, 간선을 레인으로
+  펼쳐야 한다(함께 돌면 2.17배를 돈다). 아직 만들지 않았다.
+
+## 묶음
+
+| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만¹ |
+|---|---:|---:|---:|---:|---:|
+| roots | 9.57 ms | **8.87** | 130.4 | 6.86 | 1.67억 / 27.56억 |
+| knapsack | 7.93 | 10.84 | 1,042.9 | 6.24 | 3.76억 / 216.88억 |
+| matmul | 14.20 | 36.41 | 912.0 | 7.55 | 9.24억 / 214.37억 |
+| join | 78.7 | 118.3 | 422.2 | 30.9 | 19.07억 / 76.70억 |
+| sort | 35.6 | 55.5 | 77.3 | 26.9 | 10.13억 / 15.03억 |
+| BFS | 7.66 | 96.9 | 92.9 | 9.93 | 46.93억 / 47.16억² |
+| words | 215.6 | 215.2 | 207.0 | 37.8 | 39.76억 / 39.34억² |
+
+¹ `suite-run` 세 바퀴의 사용자 모드 명령(C와 읽기 포함, 126과 같다). ² `b5`.
+
+- `b4`(128)에서 `b6`으로 묶음의 시간: knapsack 15.07 → 10.84, matmul 46.07 → 36.41, join 161.2 → 118.3, sort 74.3 → 55.5, roots
+  9.22 → 8.87 ms. 명령은 knapsack 4.72억 → 3.76억, matmul 11.18억 → 9.24억, join 28.77억 → 19.07억, sort 14.09억 → 10.13억이다.
+- 실행기만의 명령은 그대로다(roots 27.56억, knapsack 216.88억, `b4`부터 `b6`까지). 바꾼 것은 묶음과 리스트의 코드뿐이다.
+- knapsack은 `b5`에서 10.17 ms였다. 명령이 같고(3.76억) 사이클이 3% 많아, 놓인 자리로 본다. 기계어의 join은 빌드가 같은 코드인데
+  72.3–78.7 ms로 오간다.
+
+## 바꾼 것
+
+- **한꺼번에 덧붙이기**(`4791c42`). 묶음의 끝에서, 모든 덧붙이기가 이벤트의 리스트에 하나씩이고(색인 없이), 리스트가 그 꼴을
+  지키며 받을 수 있으면(`pure_list_takes`: 키 없는 FLAT은 끝에, DENSE는 지금의 개수로 담을 수 있는 키로, HASHED는 수 키로; 배열의
+  한계를 넘지 않게) 128개씩 한 번에 넣는다(`pure_list_add_many`). 메모리 몫은 넣기 전에 끝의 모습으로 셈한다. 항목 하나는 몫이 세는
+  것을 늘리기만 하므로, 끝이 몫 안이면 그 사이의 어느 회차도 넘지 않는다. 넘으면 지금처럼 회차대로 해서 그 회차에서 결함이 난다.
+  열은 한 번 늘리고 한 번 넓힌다. 이미 있는 키를 만나면 그 회차의 `EXISTS`다. 리스트의 꼴을 바꾼 회차(키 있는 리스트의 첫 항목이
+  DENSE나 HASHED를 만든다) 뒤에는 다시 한 번에 넣기를 시도한다. DENSE에 5만 개: 5.18 → 0.65 ms(기계어 0.28).
+- **점화식을 레지스터 꼴로**(`9f0498b`, `e8558e7`). 걸음은 스택에 넣고 빼는 대신, 한 회차가 쥐는 수(걸음의 결과, 점화식의 값, 루프의
+  값, 그대로인 수)에 번호를 매기고 그 두 번호의 연산이다. 한 문장 안에서 두 번 계산하는 연산은 한 번만 한다(문장이 끝나기 전에는
+  x가 그대로다). 한 회차는 묶음마다 한 번 깔아 둔 동작들을 도는 루프 하나이고, 갱신의 마지막 걸음이 x에 바로 쓴다. 그 사이에 x를
+  읽는 자리(기록)는 x가 바뀌지 않았으면 레인 배열 하나를 함께 쓴다(join의 네 자리가 한 번 저장). MINSTD 100만 회차: 44.4 → 21.8
+  ms(기계어 18.5, 실행기만 73.0). x를 네 번 읽어 합하면 50.4 → 36.0 ms(기계어 19.9).
+- **차례 없는 모으기**(`f9e3d22`). `min`과 `max`의 합치기는 차례가 답을 바꾸지 않는다(−0이 +0 아래). 정수의 합도 크기의 합이 2^53
+  아래면 그렇다. 그런 끝은 레인 순서로 넷씩 합친다. 레인마다의 `min`, `max` 걸음과 그 끝은 수를 그 차례의 정수로 바꿔 비교하는
+  루프라 벡터가 된다. 레인을 비우는 루프는 개수를 지역 변수로 두어 벡터가 됐다. 100만 회차의 `max`: 9.80 → 4.00 ms(기계어
+  4.27), 회차를 세는 합: 4.51 → 1.61 ms.
+
+## 무엇에 값을 내는가
+
+`costs/time.c`, 세 길, 세 번의 중앙값(`2026-10-06-costs.jsonl`의 `b5`, 점화식은 `b6`; 괄호는 `b4`).
+
+| 모듈 | 기계어 | 묶음 | 실행기만 |
+|---|---:|---:|---:|
+| `ops` (`max` 모으기) | 4.27 ms | **4.00** (9.81) | 156.3 |
+| `nest` | 23.1 | **10.17** (10.20) | 653.0 |
+| `adds` | 0.28 | 0.65 (5.18) | 5.17 |
+| `probes` | 56.1 | 73.0 (85.1) | 259.7 |
+| `recur` | 18.45 | 21.8 | 73.0 |
+| `recur4` | 19.9 | 36.0 | 181.4 |
+
+`b6`의 표본(묶음, Pure의 몫 가운데, 대략):
+
+- **join (118 ms)**: 점화식 약 35 ms(회차당 약 33 ns: 연산의 사슬에 나누기가 있고, 값이 메모리를 거쳐 다음 걸음으로 간다), 레인의
+  산수와 칸 읽기 약 32 ms, HASHED 찾기 약 24 ms, 칸에 더하기와 끝 정리 약 20 ms, 덧붙이기 약 6 ms.
+- **matmul (36 ms)**: 중첩 몸체 약 32 ms(안쪽 회차마다 명령 15개를 레인 200개에), 표를 만드는 루프 약 4 ms. 기계어는 전체가 14 ms다.
+- **knapsack (11 ms, `b5`)**: 안쪽 루프 약 7 ms, 미룬 쓰기의 정리 약 2 ms, 덧붙이기 1 ms 아래.
+- **sort**: 묶음 밖이다. 실행기, 정렬(`make_ordered`), 라이브러리의 몫이 대부분이다.
+
+## BFS의 산수
+
+`frontier.c`는 스위트의 그래프(노드 10만, 간선 100만)로 BFS를 프런티어 묶음처럼 돈다. 회차 `i`부터 묶음을 열 때 큐의 개수까지(최대
+B개), 각 간선의 `has`는 묶음을 열 때 묻는다. 거짓이라 한 간선이 후보이고, 후보는 회차 차례대로 다시 물어 더하거나(처음 보는 노드)
+버린다(같은 묶음의 앞 회차가 더했다).
+
+| B | 간선 | 후보 | 더하기 | 묶음 | 함께 돌 때의 레인-회차 |
+|---:|---:|---:|---:|---:|---:|
+| 1024 | 999,913 | 105,232 | 99,997 | 101 | 217만 (간선의 2.17배) |
+| 256 | 999,913 | 101,243 | 99,997 | 394 | 200만 (2.00배) |
+| 64 | 999,913 | 100,296 | 99,997 | 1,565 | 181만 (1.81배) |
+
+- **꼬리는 작다.** 차례대로 해야 하는 후보가 간선의 약 10%다. 후보 하나에 DENSE 비트를 다시 묻고, 부모의 깊이를 읽고(부모는 묶음을
+  열 때 이미 있다), 비트와 깊이를 쓰고, 큐에 덧붙인다. 묶음의 C로 하면 하나에 약 10 ns, 1 ms 남짓이다. 실행기의 걸음으로 하면
+  10만 × 100 ns 이상이라 그것만으로 기계어 전체(7.7 ms)를 넘는다. 그래서 꼬리는 `at_once`처럼 묶음 쪽 C여야 한다.
+- **간선은 펼친다.** 레인마다 간선 수가 다르다(평균 10). 중첩 루프처럼 함께 돌면 가장 긴 레인만큼 돌아 2.17배다. 묶음의 노드마다
+  간선 행의 범위를 구해 간선을 레인으로 이어 붙이면(024가 적은 "펼치기") 간선 하나에 레인 하나다.
+- **예상.** 간선 하나에 레인의 일 몇 가지(행의 `to` 읽기, 비트 묻기, 고르기) 약 3–4 ns로 3.5 ms, 노드 하나에 간선 범위 찾기(묶은
+  리스트의 색인) 약 15–20 ns로 2 ms, 꼬리 1 ms, 해석 값은 묶음 101개라 무시할 만하다. 합해 약 6–7 ms로, 기계어의 7.7 ms(C 9.9)와
+  겨룰 수 있다. 캐시 미스(간선 열 4 MB)는 C와 기계어도 내는 값이고, 묶음은 레인이 서로 떨어져 있어 미스가 겹친다.
+- **필요한 셋.** (1) `if i >= L.count { break }`이고 몸체가 L에 덧붙이기만 하면, 묶음은 열 때의 개수까지다. (2) 레인마다 다른 걷기를
+  레인으로 펼친다. (3) 커지기만 하는 걸러내기: `if !L.has(k) { … }`이고 L이 몸체에서 더해지기만 하면, 열 때 참인 레인은 건너뛰고,
+  거짓인 레인은 끝에서 차례대로 다시 묻고 몸체의 덧붙이기를 한다. 몸체가 읽는 것은 열 때 있던 것이어야 한다(BFS의
+  `seen[q.node]`는 프런티어의 노드라 열 때 있다; 계획이 이것을 알아볼 규칙이 필요하다). (1)과 (2)는 (3) 없이도 시험할 수 있다
+  (프런티어를 돌며 간선 수를 합하는 루프). 그것부터 만들고 잰다.
+
+## 뜻과 맞음
+
+- `APPEND_SOURCE`: DENSE 리스트에서 회차 q에, HASHED 리스트에서 회차 p에 이미 있는 키(그 회차의 결함), 회차 p부터 DENSE가 담지
+  못하는 키(그 회차부터 꼴이 바뀐다), 한 리스트에 회차마다 두 번 덧붙이기(회차대로), 넓어지는 열, 덧붙이기 한가운데에서 다하는
+  메모리 몫 셋. 세 길(묶음, 실행기만, 기계어)이 같고, `exists`, `memory`, `work` 결함이 다 난다.
+- 시드 1, 2, 3, 5, 23의 무작위 프로그램(665개)이 커밋마다 다섯 길에서 같았다. 시드 23의 프로그램에서 한꺼번에 덧붙이기가 31,402번
+  (항목 400만 개) 돌았고, 메모리 몫 때문에 회차대로 간 것이 292번, 이미 있는 키의 결함이 4번이었다.
+- 단위 시험이 세 JIT 모드와 ASan(실행기 모드)에서, aup의 검사가 두 모드에서 통과했다. sanitized `pure-run`으로 시드 1, 5, 23의
+  프로그램과 고정 소스 넷(410개)을 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다.
+- Pure의 `make check`가 새벽에 다섯 번 연속 `server_view_workers`(모듈을 바꾼 뒤 스트림이 10초 안에 새 값을 주지 않음)에서
+  실패했다. 묶음을 꺼도, 바꾸기 전 커밋에서도 실패했고, 같은 코드가 09:50에는 세 번 다 통과했다. 따로 돌리면 늘 통과한다. 다른
+  세션이 기기를 쓰던 때의 타이밍 문제로 본다(이 시험은 10-05에도 같은 꼴로 한 번 실패했다).
+
+## 다음
+
+- **모으기 인식의 빈틈.** `total = total + A + B`는 `(total + A) + B`라서 지금의 `x = x op e` 인식에 맞지 않고, 루프 전체가
+  계획에서 빠진다(같은 계산을 `total + (A + B)`로 쓰면 묶인다: 181 → 36 ms). 정수의 합에서는 둘이 같으니, 한 회차에 여러 번 더하는
+  모으기로 받을 수 있다.
+- **BFS**: 위의 (1)과 (2)를 만들고 재고, 그다음 (3).
+- **join**: HASHED 찾기를 레인에 대고 바로 하기(약 24 ms), 레인의 산수.
+- **matmul**: 레인이 적은 중첩 몸체의 명령당 값(미리 풀어 둔 몸체, 곱해 더하기).