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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
# 023 — 최적화 계층: 여러 종류의 일에서 깡연산으로 C를 넘기
작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전에 커밋한다). 같은 날 기준을 C에 가깝게로 고쳤다(사용자).
[022](022-arrays-and-registers.md)의 BFS는 C(`bfs.c`)보다 빨라졌지만, 그것은 C가 하지 않는 미리 읽기 덕이었다. 미리 읽기를 끄면
16 ms 대 9.9 ms로 1.6배 느리고, C에 같은 미리 읽기를 하면 다시 C가 앞선다. BFS 하나를 맞춰 넘는 것은 목표가 아니다. 목표는 같은
aup 코드, 같은 뜻, 같은 기계에서 **여러 종류의 일을 C에 가깝게** 계산하는 것이다. 메모리 안의 계산을 두루 C 가까이 하는 것이 뜻이고,
C를 완전히 제치는 것은 목표가 아니다(2026-10-05, 사용자). 그러려면 지금처럼 루프 묶음의
명령을 하나씩 기계어로 옮기는 것이 아니라, 블록 전체를 SSA로 올려 타입과 범위를 알고, 뜻을 지키는 검사를 루프 밖으로 끌어내고,
레지스터를 할당하는 계층이 모든 블록에 있어야 한다.
## 산수: 재어 본 것
모두 Pi 5(Cortex-A76 2.4 GHz), RAM, 조용한 기기. 원시 결과와 코드는 [040](../../research/experiments/040-against-c/)에 있다.
**묶음.** 일곱 가지 일을 각각 이벤트 하나로 한다. 입력은 프로그램이 MINSTD(`x * 48271 mod 2^31 − 1`, 씨앗 1)로 만들고, C도 같은
수열로 같은 입력을 만든다. C는 그 일을 하는 사람이 쓸 코드다: 같은 알고리즘, 자연스러운 타입(정수는 정수), `qsort`, 선형 탐사 해시표,
`snprintf`(`natural.h`). `suite-run`이 한 프로세스에서 Pure의 이벤트와 C를 번갈아 돌리고 답이 같은지 매번 본다.
| 일 | 무엇 | 크기 |
|---|---|---|
| roots | 1..n의 제곱근을 뉴턴 걸음으로, 그 합 (실수, 나눗셈) | n 10만 (걸음 약 200만) |
| knapsack | 배낭 DP: 항목마다 용량을 거꾸로 (정수, 표 읽고 쓰기) | 항목 100, 용량 5만 |
| sort | 수를 키로 둔 리스트에 넣고 차례로 읽기 | 20만 |
| join | 희소한 id로 둔 고객과 주문 100만을 id로 이어 지역별 합 | 고객 10만 |
| words | "w{n}" 단어를 텍스트 키 리스트로 세기 | 단어 30만, 어휘 5만 |
| matmul | n×n 행렬 곱 (키 `행 * n + 열`의 리스트) | 200 (곱셈-덧셈 800만) |
| bfs | 033의 BFS (노드 10만, 간선 100만) | |
**지금**(`5fffb63`, `2026-10-05-suite.jsonl`, 11번의 중앙값):
| 일 | Pure | C | Pure / C | 실행기만 |
|---|---:|---:|---:|---:|
| roots | 22.9 ms | 6.86 ms | 3.3 | 19.3 |
| knapsack | 1,880 ms | 6.27 ms | 300 | 298 |
| sort | 128 ms | 27.0 ms | 4.8 | 4.7 |
| join | 672 ms | 30.8 ms | 22 | 24 |
| words | 455 ms | 38.3 ms | 12 | 12 |
| matmul | 2,284 ms | 7.52 ms | 304 | 303 |
| bfs (미리 읽기 없이) | 15.7 ms | 10.0 ms | 1.57 | 9.4 |
roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거나(루프가 코드로 다 되지 않는 블록) 실행기다. knapsack의 시간 55%는
키로 둔 표를 찾는 `pure_list_seek`다.
**바닥과 뜻의 값**(`floor.c`, `2026-10-05-floor.jsonl`). 일마다 Pure가 할 수 있는 가장 좋은 코드를 손으로 C로 썼다. 표현은 Pure의
것이다: 이벤트의 리스트는 배열(FLAT은 차례로, DENSE는 키 자리에, 키 비트와 함께), 열은 값만큼 좁게, 희소한 키로 둔 리스트는 해시
색인(칸 하나에 키와 위치, 키도 좁게)이고 걸을 때 차례로 정렬한다(런타임의 정렬은 비교가 인라인). 뜻도 Pure의 것이다. 그 뜻이 드는
값을 셋으로 쟀다:
- **bare**: 검사 없음(표현만의 값).
- **hoisted**: 컴파일러가 남길 검사만. 범위로 증명되는 것은 없애고(2^53 안의 정수는 유한하고 −0이 되지 않는다), 루프가 할 일을
열 때 알 수 있는 것(작업량 예산 대비 회차, 메모리 몫 대비 덧붙이기, 꽉 찬 DENSE 리스트의 비트, 열의 폭)은 루프마다 한 번.
- **naive**: 수는 수(binary64, 범위 모름)로 두고 뜻이 놓는 자리마다 검사(결과마다 유한, 0으로 나누기, 키마다 정수·−0 아님·2^53 안·
비트 안, 위치마다 개수 안, 칸마다 폭 안, 회차마다 작업량, 덧붙이기마다 메모리 몫).
| 일 | bare / C | hoisted / C | naive / C |
|---|---:|---:|---:|
| roots | 0.99 | 1.02 | 1.77 |
| knapsack | 0.95 | 0.97 | 10.8 |
| sort | 0.61 | 0.64 | 0.83 |
| join | 0.95 | 0.91 | 1.57 |
| words | 0.92 | 0.90 | 0.91 |
| matmul | 0.96 | 0.95 | 12.1 |
| bfs | 1.09 | 0.96 | 1.23 |
| 기하 평균 | 0.91 | 0.90 | 2.6 |
- **뜻의 값은 빠른 길에서 0에 가깝게 만들 수 있다.** 검사를 그 자리마다 두면 1.2–12배이고, 범위와 끌어올리기로 남기면 0–3%다
(roots의 2%는 바깥 루프의 작업량). 그러니 뜻은 C를 넘지 못하는 이유가 아니다. 넘지 못하게 하는 것은 지금의 실행 계층이다.
- **sort의 0.64는 알고리즘 몫이다.** `qsort`는 비교마다 함수를 부르고, 런타임의 정렬은 수를 그 자리에서 견준다. 그렇게 적는다.
- join은 처음 쓴 바닥(키 8바이트, 색인과 위치가 따로)에서 1.8이었다. 칸에 키와 위치를 함께 두고 키를 4바이트로 좁혀 0.91이 됐다:
표현이 몫을 정한다.
**그래서:** 바닥의 기하 평균이 0.90이다. 계층이 내는 코드가 바닥의 1.22배 안이면 모아 보아 C의 1.1배 안이고, 일마다로도 바닥의 1.22배
안이면 C의 1.25배 안이다(roots 1.02 × 1.22). JIT의 코드는 C 컴파일러의 것보다 길기 쉬우니 그만큼의 여유다. 미달이면 미달로 적는다.
## 원칙
- **뜻은 그대로.** 수는 binary64이고 −0은 −0이다. 유한하지 않은 결과, 0으로 나누기, 없는 키, 넘친 예산은 이벤트를 실패시키고, 결함의
종류와 자리가 실행기와 같다. 바뀌는 것은 표현과 실행의 길뿐이다.
- **옮긴 검사는 났는지만 안다.** 이벤트는 실패하면 통째로 되돌려지고, 같은 상태와 입력에서 결정적이다(`now`는 호스트가 이벤트
전에 정한 `app->now`라 이벤트 안에서 그대로다). 그래서 계층이 루프 앞으로 옮기거나 하나로 묶은 검사는 "이 루프 어딘가에서 결함이
날 수 있다"만 정확하면 된다: 그 검사가 실패하면 그 루프를 검사가 제자리에 있는 코드로 돌고, 거기서도 결함이면 이벤트를 되돌리고
실행기가 처음부터 다시 돌아 같은 결함을 같은 자리에서 낸다. 제자리에 남은 검사(`require`, TPC-C의 거절 같은 뜻으로 실패하는
이벤트)는 지금처럼 그 자리에서 정확히 낸다. 다시 돌리는 값은 옮긴 검사가 실패할 때만 든다.
- **모든 블록.** 핸들러, 본문 있는 보기, 함수의 블록 모두를 계층이 맡는다. 코드로 하지 않는 명령(드문 텍스트 편집 같은)은 지금처럼
step을 부른다. 값 모형으로 블록을 거르지 않는다.
- **벤치마크의 모양을 넣지 않는다.** 묶음의 상수(`48271`, `1048576`)나 프로그램의 모양을 아는 코드는 없다. 미리 읽기 같은 기법은
남기되, 기준은 그것을 끄고 재고(`PURE_AHEAD=0`), 켤 때는 C에도 같은 기법을 해서 견준다.
- **실행기가 기준이다.** 계층의 답(상태, 보기, 결함, 실행량)은 실행기의 것과 바이트까지 같다.
## 모양
### 1. SSA로 올리기
- 블록(명령의 범위)을 기본 블록으로 나눈다: 분기(`JZ`, `JMP`), 루프(`EACH`, `LOOP`의 머리와 회차와 끝), `BREAK`.
- 스택과 지역 변수를 값으로 바꾼다: 기본 블록마다 스택의 높이는 검증기가 이미 정했으니, 추상 해석으로 스택 칸과 지역의 슬롯을
SSA 값에 대응시키고 합류점(루프 머리 포함)에 φ를 둔다.
- 상태, 리스트, 텍스트는 메모리다. 명령마다 무엇을 읽고 쓰는지(리스트별)를 이미 안다(`changes`). 이것으로 루프 불변을 가린다.
- step을 부르는 명령은 메모리 전체를 쓰는 것으로 본다(부르기 전에 장부와 걷기의 자리를 쓰고, 부른 뒤 다시 읽는다. 022의 규칙 그대로).
- 값 번호 매기기로 순수한 연산의 같은 값을 하나로 한다(같은 리스트의 같은 항목 읽기는 그 사이에 그 리스트를 바꾸는 것이 없을 때,
같은 수의 텍스트 쓰기와 보간도). words는 let이 텍스트를 담지 못해 같은 단어를 두세 번 쓰는데, 바닥은 한 번 쓴다: 그 차이를 이것이
메운다.
### 2. 타입과 범위
값마다 사실을 안다: 종류(bool, i64, 텍스트, 위치(어느 리스트의), 수)와, 수라면 **정수인지, 범위 [lo, hi], −0일 수 있는지, 유한한지**.
- 출처: 상수, 좁은 열(폭이 범위를 준다: 1바이트 [0, 255], 4바이트 [0, 2^32)), 메시지의 `u32`, 개수, 루프의 셈(`for i in a .. b`는
[a, b)), 위치.
- 전이: 산술은 구간 산술로(정수끼리의 `+ − *`는 정수, 범위가 2^53 안이면 정확하고 유한), `floor`, `min`, `max`, 비교가 가지를 좁힌다
(`if c >= w`의 참 쪽에서 `c − w >= 0`).
- 루프 머리의 φ는 넓히기(widening)로 수렴시킨다. 셈은 머리에서 [a, b)로 바로 안다.
- 정수이고 범위가 2^53 안인 값은 정수 레지스터에 둔다. 0인 곱이 −0이 될 수 있는 경우(음수가 될 수 있는 쪽과의 곱, 음의 0의 부호
바꾸기)는 범위가 0 이상이면 없다. 아니면 그 자리에 검사를 둔다.
- 정수인 `x − floor(x / d) * d`(x, d가 정수, 2^53 안, d > 0)는 정수의 나머지다(정확하다: 몫의 반올림이 정수 경계를 넘지 않는다).
### 3. 검사와 그 자리
뜻의 검사 하나하나를 IR의 연산으로 둔다: 유한, 0으로 나누기, −0, 키(정수·2^53 안·비트 안·닿는 범위 안), 위치(개수 안), 칸의 폭,
작업량, 메모리 몫, 리스트의 표현(FLAT, DENSE, 편 리스트).
- 범위가 증명하면 없앤다.
- 루프 불변이면 루프 앞(preheader)으로 끌어낸다: 리스트의 표현, 열의 주소와 폭, 키 비트의 주소.
- 귀납 변수로 묶이면 루프 앞에서 한 번: 위치 `i`가 [a, b)이고 b ≤ 개수면 경계 검사 하나. DENSE 리스트가 **꽉 찼으면**(개수가 닿는
키의 수와 같으면) 그 리스트의 키 비트 검사는 키가 [0, 닿는 범위) 안인지로 바뀌고, 그것도 귀납 변수로 묶이면 루프 앞에서 한 번.
- 루프 안의 덧붙이기나 고치기가 리스트를 바꿀 수 있으면, 그 리스트에 대한 사실은 그 명령 뒤에서 다시 확인한다(022의 규칙).
- 끌어낸 검사가 실패하면 그 루프를 검사가 제자리에 있는 코드(지금의 JIT, 또는 실행기)로 돈다. 결함은 위의 원칙대로 실행기가 낸다.
### 4. 작업량과 메모리 몫을 루프마다
- 루프가 열릴 때 회차의 수(셈은 `b − a`, 걷기는 조각의 길이)와 회차의 값(블록의 명령 수)을 안다. `남은 예산 ≥ 회차 × 값`이면
루프 안에서는 세지 않고, 끝날 때 실제 회차 × 값을 더한다(`BREAK`로 일찍 나가도 정확하다). 아니면 회차마다 센다(지금의 코드).
- 회차 안의 안쪽 루프는 그 안쪽 루프가 열릴 때 같은 일을 한다.
- 덧붙이기는 회차마다 많아야 하나라면 루프 앞에서 `회차 × 행의 바이트`를 메모리 몫과 견준다.
### 5. 레지스터 할당과 코드
- SSA의 선형 스캔 할당(정수, 실수 둘). 루프 깊이로 값의 무게를 정한다. 넘치면 프레임의 슬롯.
- 022의 기계어 조각(태그 붙은 열 주소, 장부, 줄 밖 길, `pure_run_rest`)은 계층의 하위 단계로 쓴다.
- 컴파일은 블록이 처음 돌 때 한다(지금처럼). 그 값은 재서 밝힌다.
### 6. 표현 (바닥이 가정한 것)
- **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소,
키의 비트, 칸의 4/5까지: 표가 L3에 들게; 절반까지면 조인 112 ms, 4/5면 84)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시
표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치,
찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은
FLAT이나 트리다(오가며 정렬하지 않게). 일반 코드의 APPEND도 표가 자라지 않는 한 칸을 바로 찾아 넣는다(sort 58 ms에서 37). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가
그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게).
- **텍스트 키의 이벤트 리스트**(했다): 리스트가 그 키를 안다(`text_key`, 트리의 리드는 그대로 수 키만). 이벤트의 리스트는 처음
넣을 때부터 HASHED이고, 칸에는 텍스트 바이트의 해시(FNV-1a)를 두며 같은 해시는 칸의 키 셀과 바이트로 견준다. HAS와 키로 읽기는
표에서 바로. 차례는 텍스트의 앞 여덟 바이트를 수로 견주고 같으면 바이트 전부를 견주는 병합 정렬로 낸다. 정렬되면 해시는 FLAT의
키 집합이 아니므로 버린다.
- **찾은 자리에 쓰기**(PLAN_ROW, 했다): `counts[w].n = counts[w].n + 1`처럼 FIND가 낸 위치를 ITEM_SET만 받고 그 사이가 한 줄(뛰어
들거나 나가지 않음)이며 리스트를 키로 찾기(합친 FIND, HAS) 말고 건드리지 않으면, 로더가 둘을 묶는다. HASHED 리스트는 위치 대신
칸에 쓴다(위치를 내면 정렬된다). words 453 ms에서 217.
- 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트).
- 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열).
## 단계
1. **표현**(값이 가장 큰 것부터): 차례로 작은 정수 키를 받는 키 있는 리스트는 DENSE로(지금은 키가 차례를 어길 때만 DENSE가 되고,
차례로 받으면 FLAT으로 남아 키로 찾기가 이분 탐색이다: knapsack과 matmul의 300배), 희소한 키의 해시 색인과 걸을 때의 정렬,
텍스트의 정수 자릿수. 지금의 JIT과 실행기로 잰다.
2. **IR**: 블록을 SSA로 올리고 타입과 범위를 낸다. 기계어는 그대로 두고, IR을 해석하는 시험용 실행기(명령의 뜻은 실행기의 step으로,
값마다 그 사실(정수, 범위, −0, 유한)이 맞는지 확인)로 모든 검사의 프로그램을 실행기와 견준다.
3. **코드**: IR에서 레지스터를 할당해 기계어를 낸다. 모든 블록. 검사는 아직 제자리에.
4. **검사 끌어올리기, 루프마다의 작업량과 메모리 몫, 다시 돌리기**(결함이 나면 실행기로).
단계마다 검사로 고정하고, 묶음을 재서 커밋한다.
## 착수 기준
- **최소 확인**
- Pure의 `make check`(ASan 포함), aup의 검사(무작위로 만든 프로그램 600개, 참조 모델과의 대조), Vega의 검사가 `PURE_JIT=1`,
`PURE_JIT=all`, `PURE_JIT=0`에서 모두 초록이다.
- 새 시험: 무작위 프로그램에 결함을 심어(작은 예산, 없는 키, −0, 0으로 나누기, 2^53을 넘는 정수, 넓혀지는 열) 계층과 실행기의
상태, 결함의 종류와 자리, 실행량이 같다. `module_assumptions`가 그대로 지난다.
- 기기 사이: 같은 `pure-run` 46번이 Pi(계층), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다.
- **통과 조건**(RAM의 Pi 5, `suite-run` 11번의 중앙값, `PURE_AHEAD=0`)
- 일마다 Pure의 중앙값이 같은 프로세스의 C의 **1.25배 안**이다.
- 일곱의 Pure / C의 **기하 평균이 1.1 아래**다.
- BFS를 미리 읽기와 함께 재면 같은 미리 읽기를 한 C(`bfs_ahead`)의 1.0배 아래다.
- **뜻의 값**: 일마다, 계층의 코드를 검사 없이 낸 것(`PURE_UNCHECKED=1`, 재기 위한 것이고 답이 같은지만 본다)보다 5% 넘게 느리지
않다.
- 지금의 앱: TPC-C와 은행 질의를 여섯 쌍 번갈아 잰 중앙값이 `5fffb63`보다 1% 넘게 느리지 않고, 은행 질의의 명령 수가 1% 넘게 늘지
않는다. 그 앱들의 블록 중 실행기로 도는 것이 없다(step으로 부르기로 정한 명령 말고는).
- **밝히는 것**: 단계마다의 묶음 표(Pure, C, 실행기, 검사 없는 계층), 블록마다의 컴파일 시간과 코드의 크기, 첫 이벤트가 컴파일에
쓰는 시간, 해시 색인과 정렬이 드는 메모리.
## 하지 않는 것
- aup 프로그램의 알고리즘을 바꾸기, 묶음의 크기나 상수에 맞추기. C를 고치기(견주는 C는 `natural.h` 그대로).
- SIMD로 벡터화하기. C도 `-O2`에서 이 루프들을 벡터화하지 않는다(gcc 14.2의 `-fopt-info-vec`: 답을 쓰는 두 칸만 묶는다).
- macOS와 x86-64의 계층(실행기가 같은 답을 낸다).
|
