1 files changed, 166 insertions, 0 deletions
diff --git a/docs/research/132-batch-executor-floor-and-the-way-past.md b/docs/research/132-batch-executor-floor-and-the-way-past.md
new file mode 100644
index 0000000..c526f05
--- /dev/null
+++ b/docs/research/132-batch-executor-floor-and-the-way-past.md
@@ -0,0 +1,166 @@
+# 132 — 묶음 실행기의 바닥과 그 너머: 비용의 세 자리, 문헌, 근본적인 길 (연구)
+
+2026-10-08. [131](131-batch-executor-general-cuts.md)까지 범용 장치로 깎아 BFS가 기계어의 약 3배에서 멈췄다. 사용자는
+더 깎기 전에 근본적인 해법을 Pure의 철학 위에서 묻고, 힘들면 연구를 먼저 하라고 했다. 이 글은 코드를 바꾸지 않는다. 비용이
+어디에 있는지를 재고, 같은 문제를 다룬 문헌을 읽고, 길을 셋으로 나누어 철학의 잣대로 재고, 결정할 실험 하나를 적는다.
+
+## 쉬운 말로
+
+- **문제는 "연산마다 레인을 한 번 훑는 꼴" 자체다.** 묶음 실행기는 명령 하나를 레인 1024개에 한 번에 하고, 그 결과를 메모리의
+  레인 배열에 쓴다. 다음 명령이 그것을 다시 읽는다. 기계어(JIT)는 같은 값을 레지스터에 두고 다음 연산으로 넘긴다. 요소당 명령이
+  묶음은 4–12개, 기계어는 1–2개다. 이것은 구현의 흠이 아니라 꼴의 값이고, 데이터베이스 쪽 문헌이 같은 수를 잰다(아래).
+- **비용의 자리는 셋이다.** 요소마다(레인 훑기), 묶음마다(묶음을 열 때마다 블록을 다시 읽고 꼴을 정하는 값, 약 6,500 명령),
+  후보마다(걸러내기 뒤 차례대로 하는 꼬리, 약 250 명령). 셋 가운데 범용으로 거의 다 없앨 수 있는 것이 둘째다. 셋째는 리스트 쪽
+  C라 줄일 수 있다. 첫째가 바닥이다.
+- **근본적인 길은 "레지스터 타일"이다.** 레인 1024개를 명령마다 훑는 대신, 레인 4–16개를 레지스터에 올려 두고 몸체의 명령을 그
+  타일에 차례로 다 적용한 뒤 다음 타일로 간다. 값이 메모리를 오가지 않는다. 명령마다 내는 디스패치는 타일마다 내므로 그 값이
+  관건이다(Ertl & Gregg가 잰 것). 실행 시간에 코드를 만들지 않고, C 컴파일러가 가는 곳 어디서나 같다. 실행기(타일 1)와
+  묶음 실행기(타일 N)가 한 기계가 된다. 그러나 C 컴파일러가 타일을 레지스터에 붙들어 두는지는 재 보기 전에는 모른다.
+- **그래서 결정할 실험 하나를 제안한다.** 041처럼 작은 C 시제품으로 세 몸체(배낭의 안쪽, BFS의 프런티어, roots의 뉴턴)를 타일로
+  돌려 요소당 사이클을 기계어와 견준다. 기준은 셋 모두 기계어의 1.3배 안이다. 넘지 못하면 이 길은 답이 아니다. 반나절이다.
+
+## 잰 것: 비용의 세 자리
+
+빌드 `b9`(`735ba81`), [131](131-batch-executor-general-cuts.md)과 같은 방법.
+
+### 요소마다
+
+BFS 간선당 112개 가운데 약 45개가 레인 훑기다(`to` 모으기 12, 비트로 묻기 11, 뒤집어 가르기와 고르기 7, 덩어리 만들기 7,
+나머지). 각각은 요소마다 적재, 검사, 저장을 하는 범용 루프다. 기계어는 간선당 38.5개로 몸체 전체를 한다. matmul의 안쪽 몸체는
+명령 15개를 레인 200개에 하는데, 명령마다 레인 배열을 읽고 쓰므로 15번 오간다. 기계어는 레지스터에서 한다(14 ms 대 40 ms).
+
+### 묶음마다
+
+같은 몸체를 레인 1024개와 256개로 돌려 명령의 차를 묶음 수의 차로 나눴다(`costs/sum0`, `ops0`: 회차 1,024,000, 묶음 1,000과
+4,000).
+
+| 모듈 | 1024 레인 | 256 레인 | 묶음마다 |
+|---|---:|---:|---:|
+| `sum0` (회차를 세는 합) | 4,789만 명령 / 1,621만 사이클 | 6,886만 / 2,345만 | **6,990 명령 / 2,410 사이클** |
+| `ops0` (`let` 하나와 `max`) | 6,641만 / 3,036만 | 8,534만 / 3,683만 | 6,310 / 2,160 |
+
+묶음 하나를 여는 데 약 6,500 명령, 약 1 µs다. 블록을 다시 읽어 지역 변수의 꼴을 정하고(`batch_run`의 앞머리, `recurrences`,
+`sums`), 명령마다 값의 꼴(균일·아핀·레인)을 물어 가르고(`pass`), 끝에서 검사하고 쓴다(`settle`). 024는 처음부터 "묶음 프로그램은
+루프마다 한 번 만든다"고 했는데, 그 단계를 만들지 않았다. 배낭에서는 이 값이 시간의 약 20%다(`batch_run` 10.7%, `pass` 8.5%).
+
+**레인을 줄이면 느려진다.** 024는 레인 자리를 L1(64 KB) 안에 두려고 256 레인을 적었고, 1단계에서 디스패치 값을 나누려고
+1024로 늘렸다. 지금 디스패치는 명령당 약 20 ns라 다시 256으로 줄여 봤다(`b9`의 코드, `BATCH`만 바꿈, 5번의 중앙값).
+
+| 일 | 1024 | 512 | 256 |
+|---|---:|---:|---:|
+| knapsack | 11.4 ms | 15.7 | 24.5 |
+| roots | 8.97 | 9.51 | 10.8 |
+| join | 117 | 121 | 126 |
+| matmul | 40.0 | 40.0 | 40.0 |
+| BFS | 24.3 | 24.7 | 26.0 |
+
+L1 가설은 틀렸다. 한 번의 훑기가 닿는 버퍼는 둘셋(24 KB)이라 어차피 L1 안이고, 느려지는 것은 묶음마다의 고정 값이 네 배가
+되기 때문이다. Kersten 등도 벡터 크기 1K–4K가 가장 좋고 64 아래와 64K 위가 많이 나쁘다고 잰다(아래).
+
+### 후보마다
+
+걸러내기 뒤 차례대로 하는 꼬리(모은 회차의 기록 50, 결정 90, 넣기 110)가 후보 하나에 약 250 명령이다. 기계어는 같은 일(비트
+묻기, DENSE에 더하기, 큐에 덧붙이기)을 약 100개로 한다. 리스트 쪽 C의 일이라 줄일 수 있지만, 간선당 26개 몫이다.
+
+### knapsack과 matmul의 10%
+
+131에서 두 일이 약 10% 느려진 것도 둘째 자리의 일이다. `pass`가 커져 인라인과 배치가 바뀌었다. 묶음 프로그램을 한 번 만들면
+`pass`의 꼴 묻기가 사라져 이 값도 같이 사라진다.
+
+## 문헌: 같은 문제를 다룬 곳
+
+묶음 실행기는 데이터베이스의 "벡터 단위 실행"(vector-at-a-time)과 같은 꼴이다. 그쪽은 20년을 쟀다.
+
+- **MonetDB/X100**(Boncz, Zukowski, Nes, CIDR 2005). 튜플 하나씩의 해석 값을 벡터(약 1,000개, 캐시 안)로 나누고, 연산마다
+  타입에 특화한 원시 루프를 돈다. 우리의 레인 배열은 그들의 벡터, 우리의 `binary`·`find`는 그들의 원시 루프다. 그들도 벡터가
+  캐시를 넘으면 느려진다고 적었다.
+- **Kersten, Leis, Kemper, Neumann, Pavlo, Boncz**(VLDB 2018, "Everything You Always Wanted to Know About Compiled and
+  Vectorized Queries"). 같은 시스템 안에 벡터 해석(Tectorwise)과 코드 생성(Typer, HyPer 꼴)을 둘 다 만들어 견줬다. TPC-H SF=1,
+  튜플당 사이클/명령: Q1 Typer 34/68 대 TW 59/162, Q6 11/20 대 11/15, Q3 25/21 대 24/42, Q9 74/42 대 56/76, Q18 30/46 대 48/102.
+  결론은 "둘 다 효율적이고 꽤 가깝다. 코드 생성은 계산이 많고 캐시에 드는 일에서 명령이 적다(중간값을 레지스터에 둔다). 벡터
+  해석은 캐시 미스를 숨기는 데 조금 낫다." 벡터 해석의 남는 명령은 "원시 루프의 결과를 벡터에 쓰고 읽는 적재·저장"이라고 명시한다.
+  우리 BFS의 112 대 38.5(2.9배)는 그들의 Q1(2.4배)과 같은 결이다. 벡터 크기는 1K–4K가 가장 좋다고 잰다.
+- **Sompolski, Zukowski, Boncz**(DaMoN 2011, "Vectorization vs. Compilation in Query Execution"). 루프 전체를 컴파일하는 쪽이
+  벡터 해석보다 못한 경우 셋을 들고, 둘을 섞으라고 한다. 컴파일한 조각을 벡터 처리의 벽돌로 쓰거나, 벡터의 원칙을 컴파일한
+  계획에 넣거나.
+- **Gubner, Boncz**(ADMS 2017, "Exploring Query Execution Strategies for JIT, Vectorization and SIMD"). 벡터 해석에서 집계를
+  메모리의 집계 표가 아니라 레지스터에서 하는 "in-register aggregation"으로 Q1에서 HyPer의 JIT보다 빨라졌다고 적는다. 값을
+  레지스터에 두는 것이 벡터 해석의 남은 길이라는 뜻이다.
+- **Photon**(Databricks, SIGMOD 2022). 코드 생성 대신 벡터 해석을 택했고, 묶음마다 데이터의 성질을 보고 특화한 길을 고른다
+  (우리의 값 꼴 균일·아핀·레인과 4바이트 열이 그것이다).
+- **Ertl, Gregg**(JILP 2003, "The Structure and Performance of Efficient Interpreters"). 해석기의 시간 절반 이상이 간접 분기의
+  예측에 달려 있고, 스레디드 코드(핸들러 끝마다 다음으로 뛰기)가 switch보다 거의 두 배 빠르다. 레지스터 타일 해석의 디스패치
+  값은 여기서 나온다.
+
+Pure가 그들과 다른 것: 회차 사이의 의존(쓰기를 끝으로 미루고 검사한다), 결함이 제 회차에서 나야 한다, 작업량을 회차마다 센다,
+질의 최적화기가 없다. 그래서 그들의 수를 그대로 가져올 수는 없지만, 꼴의 값(요소마다의 적재·저장)은 같다.
+
+## 길들과 철학의 잣대
+
+잣대는 둘이다. "어떤 관습적인 층을 없애는가"([000](000-working-method.md), 추상의 압축)와 "실행 시간에 코드를 만들지 않고,
+C 컴파일러가 가는 곳 어디서나 같고, 메모리를 적게 쓴다"([024](../design/024-batch-executor.md)).
+
+### A. 묶음 프로그램을 로드 때 한 번 (024의 못 만든 단계)
+
+루프마다 로드 때 한 번, 명령마다 피연산자의 꼴과 폭, 묶음마다 할 검사, 미룬 효과의 차례를 정해 둔다. 묶음을 열 때는 그 프로그램을
+돈다. 둘째 자리(묶음마다 약 6,500 명령)가 거의 사라지고 `pass`의 꼴 묻기도 사라진다. 범용이고, 아래 B의 전제이기도 하다
+(B도 프로그램이 있어야 한다). 바닥(첫째 자리)은 건드리지 않는다.
+
+### B. 레지스터 타일 해석 (근본적인 길)
+
+몸체의 명령을 레인 4–16개의 타일에 차례로 적용한다. 타일은 NEON 레지스터(4바이트 넷, 8바이트 둘)에 있고, 몸체의 임시 값은
+고정된 레지스터 더미(v0..v7)에 있다. 명령은 C의 레이블이고(계산된 goto), 레이블은 더미의 깊이마다 하나씩 빌드 때 스크립트가
+만든다(연산 40 × 깊이 8). 분기는 타일의 마스크다. 레인마다 다른 읽기(모으기, 비트 묻기, 찾기)는 타일 안에서 스칼라 넷이다.
+
+- 없애는 층: 실행기(회차마다 해석)와 묶음 실행기(명령마다 훑기)가 "타일 크기"의 차이로 한 기계가 된다. 기계어는 필요 없어진다.
+  024가 바란 그림이다.
+- 지키는 것: 실행 시간에 코드를 만들지 않는다. 메모리는 레인 배열 200 KB 대신 레지스터와 작은 타일 버퍼다.
+- 셈: 몸체 15 명령, 타일 8이면 디스패치 15 × 약 5 사이클(Ertl & Gregg, 잘 예측될 때) / 8 레인 ≈ 9 사이클/레인, 연산 15 × 약
+  1 = 15, 합 약 24 사이클/레인. 타일 16이면 약 20. 기계어의 BFS는 간선당 19 사이클, 지금 묶음은 57이다. 되면 기계어의
+  1.1–1.4배다. 안 되는 경우: C 컴파일러가 레이블 사이에서 더미를 레지스터에 두지 못하고 스택으로 내리면 요소마다 적재·저장이
+  돌아와 지금과 같아진다. 그래서 재 보기 전에는 모른다.
+- 뜻은 그대로다: 타일마다의 깃발(검사), 미룬 쓰기, 결함의 회차. 묶음 실행기의 규칙(의존 거리, 걸러내기, 고르기)은 타일에도
+  그대로 든다.
+
+### C. 합친 연산의 표
+
+자주 나오는 명령 짝을 빌드 때 C 루프 하나로 만든다. 바닥을 짝의 수만큼만 낮춘다. 사용자가 범용이 아니라고 했다. 제외한다.
+
+### D. 모듈을 C로 미리 컴파일
+
+`aup`가 C를 내고 기기의 C 컴파일러로 묶는다. 기계어를 싣는 셈이라 ".pmod 하나가 어디서나 같다"와 안전의 자리를 바꾼다. 제외한다.
+
+### E. 후보 꼬리의 C
+
+리스트 쪽에서 폭 검사를 한 번에 하고 비트와 칸을 함께 쓰면 후보당 250을 100 가까이로 줄일 수 있다. 범용이지만 간선당 26개의
+몫이다. A, B와 독립이다.
+
+## 결정할 실험
+
+기준을 먼저 적는다. **세 몸체 모두에서 요소당 사이클이 기계어의 1.3배 안이면 B를 만든다. 하나라도 넘으면 B는 답이 아니고,
+A와 E를 만들고 기계어를 남긴다.**
+
+`research/experiments/042-tiles/`에 041처럼 런타임을 건드리지 않는 C 시제품을 둔다.
+
+1. 몸체 셋: 배낭의 안쪽 루프(아핀 읽기, 비교, 마스크 쓰기), BFS의 프런티어(행 모으기, 비트 묻기, 가르기, 후보 모으기),
+   roots의 뉴턴 걸음(레인마다 다른 횟수, `break`).
+2. 타일 4, 8, 16. 디스패치는 계산된 goto. 더미는 고정 변수. 빈 연산만 돌려 디스패치의 바닥을 따로 잰다.
+3. 같은 프로세스에서 지금의 묶음 방식(연산마다 훑기)과 C 바닥을 함께 돌린다. 기계어의 수는 `search-run`과 스위트의 것이다.
+   요소당 명령과 사이클(`icount`).
+4. `objdump`로 더미가 레지스터에 있는지, 스택으로 내려가는지 본다. 내려가면 함수를 나누거나 더미를 줄여 다시 잰다.
+
+반나절이다. 결과가 기준을 넘으면 B의 설계(025)를 쓰고, 넘지 못하면 그 수를 적고 A와 E로 간다.
+
+## 추천
+
+A는 어느 길에서나 필요하고 범용이므로 먼저 만들어도 된다. B는 실험 뒤에 정한다. 지금 가진 수로 보면 B가 유일한 근본적인 길이고,
+문헌(Gubner & Boncz의 레지스터 집계, Sompolski의 "벽돌")은 값을 레지스터에 두는 것이 벡터 해석의 남은 길이라는 데 모인다.
+
+## 출처
+
+- [MonetDB/X100: Hyper-Pipelining Query Execution](https://www.cidrdb.org/cidr2005/papers/P19.pdf)
+- [Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask](https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf)
+- [Vectorization vs. Compilation in Query Execution](https://dl.acm.org/doi/10.1145/1995441.1995446)
+- [Exploring Query Execution Strategies for JIT, Vectorization and SIMD](https://t1mm3.github.io/assets/papers/adms17.pdf)
+- [Photon: A Fast Query Engine for Lakehouse Systems](https://people.eecs.berkeley.edu/~matei/papers/2022/sigmod_photon.pdf)
+- [The Structure and Performance of Efficient Interpreters](https://jilp.org/vol5/v5paper12.pdf)