1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
# 024 — 묶음 실행기: 기계어 없이 루프를 C 가까이
작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 1단계를 만들었다([126](../research/126-batch-executor-stage-one.md): knapsack이 실행기에서 1,041 ms → 13.6 ms, 안쪽 루프는 계층의 1.17배로 기준 미달). 2단계(중첩 루프를 함께, 모으기)를 만들었다([127](../research/127-batch-executor-stage-two.md): roots 9.13 ms로 계층 9.57보다 빠름, matmul 50 ms). 4단계의 앞 절반(덧붙이기), 5단계(점화식), 칸에 더하기, 걷기를 만들었다([128](../research/128-batch-executor-tables-and-costs.md): join이 실행기의 423에서 161 ms, 계층 74). 남은 값은 덧붙이기 하나 약 100 ns, join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). 그 셋을 줄였다([129](../research/129-batch-executor-costs-cut.md): 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기; knapsack 10.8, matmul 36.4, join 118 ms, roots 8.87로 계층 9.57보다 빠름). BFS를 셈하니 차례대로 할 꼬리가 간선의 약 10%라, 꼬리를 묶음의 C로 하고 간선을 레인으로 펼치면 계층과 겨룰 만하다(약 6–7 ms 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다.
[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 |
|---|---:|---:|---:|---:|---:|
| roots | 6.87 ms | — | 6.79 (0.99)¹ | | 1.39 |
| knapsack | 6.37 | 1.96 (묶음의 블록, −O3) | 4.55 (0.71) | 2.70 (0.42) | 1.20 |
| matmul (j 레인) | 7.11 | 4.90 (j·k 바꿈, 4바이트, −O3) | 17.75 (2.50) | 6.68 (0.94) | 1.90 |
| join | 32.6 | — | 57.8 (1.77)² | 48.4 (1.49)³ | 2.46 |
| BFS | 9.97 | 7.04 (미리 읽기) | 10.30 (1.03)¹ | | 1.61 |
¹ 디스패치 없이 연산마다 레인을 한 번 도는 꼴이다. roots에 디스패치를 더해도 묶음 391개 × 걸음 64 × 연산 4로 10만 번 아래다.
² 점화식은 레인마다 해석하고(역수 준비), 회차의 나머지는 연산 11개를 하나씩 해석한다. ³ 회차의 나머지를 한 줄씩의 C 루프로
합쳤다. 점화식까지 C로 하면 39.9 ms(1.22)다.
- 일곱 가지 일의 기하 평균은 계층이 1.92다. sort 1.37과 words 5.58은 그대로 두었다. 연산 따로로 하면 **1.58**이고, 합친 꼴로 하면
**1.24**다. words를 빼면(보류) 1.28과 0.97이다. 재구성을 받은 C와 견주면 2.07과 1.63이다.
- 배낭의 0.71과 0.42는 C를 이긴 것이 아니다. gcc가 자연스러운 배낭 루프를 벡터로 만들지 못한 것이다(거꾸로 가는 루프라, −O3와
ivdep를 줘도 9.5 ms였다). 같은 블록으로 쓴 C는 1.96 ms다. 묶음이 앞서는 것은 실행 시간에 확인한 독립(아래) 덕이다.
- 행렬 곱의 C는 하네스마다 다르다. `suite-run`에서는 7.44 ms다(칸 만들기 포함, n은 실행 시간). 처음의 시제품은 n=200이 상수로
인라인돼 4.9 ms였다. 위 표는 n을 실행 시간에 읽는다.
- 같은 일에서 연산을 따로 두는 값: 배낭은 4바이트 레인으로 1.7배, 8바이트 레인과 거꾸로 가는 적재로는 4.2배(11.2 ms)다. 행렬
곱은 2.7배다(k 레인으로는 22.1 ms). join은 1.19배다.
**시제품은 천장이다.** 묶음 프로그램은 손으로 짰다(컴파일러가 낼 순서대로). 작업량을 세지 않았고, 적재의 꼴 검사(열의 폭, DENSE의
빈틈)도 하지 않았다. 실패 뒤 다시 도는 길도 돌려 보지 않았다. 지난번에 손으로 쓴 바닥(124)은 C의 0.90배였지만, 계층은 일마다
1.2–2.5배(텍스트 5.6배)에 닿았다. 디스패치를 넣고 잰 것은 knapsack(4.55, 11.2), matmul(17.75, 22.1), join(57.8)이다. 합친
꼴의 값은 합친 연산의 표가 그 꼴을 덮을 때만 나온다.
## 왜 되는가
1. **디스패치가 256으로 나뉜다.** 실행기의 값은 명령마다 내는 디스패치와 값 꺼내기였다. 묶음에서는 연산 하나가 레인 256개를 돈다.
2. **검사가 분기가 아니라 깃발이다.** `forms.c`에서 적재마다 앞에 둔 분기(한 번도 타지 않아도)가 1.34배였다. 2^53 검사는 거의
공짜였다. 묶음에서는 검사가 OR로 깃발에 모이고, 적재 앞에 분기가 없다.
3. **레인이 좁고 메모리의 차례다.** Pure의 열은 4바이트다. 4바이트 레인은 NEON에 넷이 들어간다. 배낭을 8바이트 레인과 거꾸로 가는
적재로 하면 11.2 ms, 4바이트 레인과 메모리 차례로 하면 4.55 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처럼 묶음을 열 때 실행 시간의 값으로 한다. 이 규칙은 읽기와 쓰기의 보폭이 같을 때만이다. 보폭이 다르면(예: `2l`에서 읽고 `l`에 쓰기) 일반의 판정은 열린 문제여서, 그런 루프는 처음에는 묶지 않는다.
- **커지기만 하는 걸러내기.** 루프가 리스트에 더하기만 하면(빼지 않으면) `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만에 약 13 ms였다
(52.7 대 39.9). 그 3분의 1은 상수로 나누는 정수 나눗셈의 지연이다. 프로그램을 만들 때 상수의 역수를 준비하면 4 ms를 던다(48.4).
나머지는 디스패치와 연산 다섯의 사슬이다. 기계어 없이 더 줄이려면, 자주 나오는 점화식의 꼴을 합친 연산으로 둔다(아래).
### 연산
- **레인 레지스터**는 타입이 있다: u32, i64(2^53 아래의 정수), f64. 폭은 023의 사실(열의 폭, 범위)에서 고른다.
- **연산의 종류**: 검사하는 원소별 산수, 비교와 마스크, 고르기, 아핀 적재와 저장(보폭 ±1, k), 키로 모으기(DENSE는 키 자리,
HASHED는 탐사, FLAT은 위치), 차례대로 흩어 더하기, 모으기, 살아 있는 레인 모으기와 펼치기.
- **합친 연산**은 빌드 때 스크립트가 꼴의 표에서 C 루프로 만든다(곱해 더하기, 더하고 최대로 저장, 읽고 비교해 고르기 같은 것).
묶음 컴파일러는 꼴이 맞으면 합친 연산을 쓰고, 아니면 따로 둔다. 재어 보니 합치면 배낭이 1.7배, 행렬 곱이 2.7배, join이 1.19배 빨랐다. 연산을
따로 두면 레인 배열(L1 안)을 연산마다 읽고 쓰기 때문이다. 기계어를 만드는 것과 달리 표는 유한하다. 그래서 어떤 꼴을 둘지는
묶음과 앱에서 나오는 프로그램을 세어 정한다.
### 뜻
- **같은 답.** 레인마다 자기 값을 검사한다. 묶음의 깃발이 서면 묶음을 시작한 상태에서 실행기가 회차마다 다시 돈다. 그래서
실패와 오류가 회차마다 돈 것과 같은 회차에서 난다. 이를 위해 묶음의 검사가 다 지나기 전에는 보이는 효과가 없다. 저장은
프로그램의 끝으로 내리거나 묶음의 버퍼에 두고, 깃발이 비었을 때만 쓴다. 더하기와 덧붙이기는 차례대로 도는 끝 부분에서 한다.
- **같은 작업량.** 실행기는 회차마다 작업량을 센다. 묶음은 열 때 m 회차의 몫을 한꺼번에 내고, 예산이 모자라면 m을 줄인다.
`module_tier`처럼 작은 예산으로 답과 작업량을 회차마다 돈 것과 견준다.
- **수의 차례.** 수의 합은 차례대로 한다(다시 묶지 않는다). 같은 수가 나온다.
### 메모리
레인 레지스터 16개 × 256 × 8바이트 = 32 KB를 이벤트 스레드 하나가 쓴다(L1 64 KB 안). 펼친 레인(BFS의 간선)도 256씩 끊어 같은
자리를 쓴다. 묶음 프로그램은 루프마다 연산 수십 개 × 32바이트다. 실행 가능한 페이지도, 코드 캐시도 없다.
1단계는 묶음을 1024 레인으로 했다(126). 묶음마다 명령을 해석하는 고정 값(약 500 ns)을 나누기 위해서다. 2단계에서 레인 버퍼를
24개로 늘렸다(중첩 루프의 상태와 모으기가 버퍼를 쥔다). 그래서 레인 자리가 24개 × (1024 + 24) × 8바이트 = 약 200 KB다. 스레드의
정적 TLS에 있고, 묶음을 도는 스레드만 그 페이지를 쓴다.
### JIT와의 관계
022의 JIT(copy 0/1)와 023의 계층은 기계어를 쓴다. 묶음 실행기는 C 컴파일러가 가는 곳 어디서나 같은 코드로 돈다. copy-and-patch도 빌드 때 C로 만든 조각을 쓰지만, 실행 시간에 그 조각을 복사하고 고쳐 실행 가능한 페이지에 쓰고, 기계마다 조각과 고치기가 따로다. 묶음 실행기는 빌드 때 만든 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.77, 합친 꼴 1.49). 계층(2.46)보다는
빠르다. sort(런타임의 정렬)와 words(보류)는 이 설계로 바뀌지 않는다. 합친 연산의 표가 꼴을 덮지 못하면 행렬 곱은 2.5배로
남는다(계층 1.90보다 느리다). 그래서 행렬 곱에는 합친 연산(곱해 더하기)이 첫 표에 있어야 한다.
|
