# 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, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소,
  키의 비트, 2배 넘는 칸)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시
  표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치,
  찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은
  FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 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의 계층(실행기가 같은 답을 낸다).