# 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배로 남는다.