path: root/docs/research/123-past-c.md

# 123 — C보다 빠르게 (미달)

2026-10-05. [021](../design/021-past-c.md)을 잰다. 기준은 구현하기 전에 적어 커밋했다(`820cca3`). 해 보고 알게 된 것으로
021의 산수를 바로잡았다(`2c602fc`, `38e0280`, 021의 "바로잡음"). 잰 빌드는 `b1b3c7b`다.

## 쉬운 말로

- **C를 넘지 못했다.** BFS(노드 10만, 간선 100만) 한 번이 HTTP로 190 ms에서 90 ms가 됐다(020 전부터는 397 ms에서 4.4배). 같은
  실행에서 C는 9.1 ms, CPython은 452 ms다. Pure는 C의 9.9배 걸리고, CPython보다 5배 빠르다.
- **넘지 못한 까닭을 쟀다.** 노드마다 간선 조각의 두 경계를 찾고 첫 간선을 읽는 데, 저장된 리스트(B+트리)는 373 ns, 같은 일을 C의
  오프셋 배열은 21 ns다. B+트리는 뿌리에서 잎까지 서로 기다리는 읽기를 넷 하고, C는 반복끼리 기다리지 않아 미스를 겹친다.
- **C를 넘을 수 있는 길을 손으로 재 봤다.** 같은 탐색을 Pure의 표현대로 C로 손수 썼다(`bfsfloor.c`). 표현을 지금처럼 수(8바이트)로
  두면 가장 잘 써도 23 ms다: 노드의 표들이 L3(2 MB)에 들지 않아 DRAM 미스가 C의 6.6배다. 열을 값에 맞게 좁히면(정수는 4바이트,
  작은 수는 1바이트) 13 ms, 거기에 큐의 앞 노드를 미리 읽으면 **8.8 ms로 C(9.9 ms)보다 빠르다**. 이 셋(저장된 리스트를 배열과 칸의
  색인으로, 좁은 열, 미리 읽기)과 손으로 쓴 것에 가까운 기계어가 함께 있어야 한다. 다음 설계(022)가 이것이다.
- **지금의 앱은 기준 안이다.** TPC-C 여섯 쌍의 중앙값 −2.8%(기준 3%), 은행 질의는 같거나 빠르고, 명령 수는 +0.8% 안(기준 1%).
  다만 TPC-C는 여섯 쌍 모두 느렸다(−1.8%에서 −4.6%). 그중 2.1%는 JIT이다: TPC-C의 루프(주문의 줄)는 대부분의 명령이
  `step` 부르기라, 같은 빌드에서 JIT을 끄면 그만큼 빠르다.
- **만든 것.** 이벤트의 리스트를 배열로(차례대로 또는 키 자리에), 키로 찾아 읽기를 하나로, 실행기를 프레임과 step으로, 그리고
  AArch64 JIT(분기와 루프와 뜨거운 명령을 코드로, 트리의 항목은 프레임이 쥔 런에서; 루프가 있는 블록만). JIT과 실행기의 답은 모든
  검사에서 같고, 같은 계산 46번이 Pi(JIT)와 WSL2, Mac(실행기)에서 바이트까지 같다.
- **틀린 것.** 처음 잰 JIT 뼈대의 "60 ms"는 표의 경계를 넘어 쓰는 버그가 결과를 망친 빌드였다(닿은 노드 92,179, 맞는 값 99,998).
  커밋 메시지는 푸시 전에 고쳤다. 저장된 리스트의 디렉터리를 "필수"라 했지만 재 보니 사이클이 늘어 넣지 않았다. "키 집합을 비트로
  두는 것이 C를 넘는 몫"이라 했지만, C의 `depth`를 비트로 바꾸면 C가 오히려 느려진다(9.9에서 12.0 ms).

## 결과

원시 결과와 명령은 [038-past-c](../../research/experiments/038-past-c/)에 있다(`runs.sh`, `bfs-run.c`, `seekfloor.c`,
`indexfloor.c`, `bfsfloor.c`, `pairs.py`). 전은 `a553601`(021 직전), 후는 `b1b3c7b`다. 모든 블록을 컴파일하던 `38e0280`으로
먼저 잰 계열은 `2026-10-05-all-*`로 남겼다(아래 "고친 것").

### BFS

**HTTP**(033의 `bfs.py`: `pure-serve`, 저장소는 RAM, 다섯 탐색 세 라운드, 같은 실행에서 C와 CPython). 다섯 탐색 모두 Pure의
거리와 닿은 노드 수가 C와 같다.

| 중앙값 | 전 (`a553601`) | 후 (`b1b3c7b`) |
|---|---:|---:|
| Pure | 190.0 ms | **90.0 ms** |
| C (`bfs.c`) | 9.03 ms | 9.08 ms |
| CPython | 449 ms | 452 ms |
| Pure ÷ C | 21.0 | 9.9 |

처음 잰 후의 계열은 내가 같은 때 다른 기기로 30 MB를 보내던 중이라(한 탐색 106 ms) 버리고 다시 쟀다. 버린 것은 남기지 않았다.

**코어만**(`bfs-run`: 호스트 없이, 일곱 탐색의 중앙값). 전과 후를 번갈아 여섯 쌍.

| | 전 | 후 |
|---|---:|---:|
| 여섯 쌍의 중앙값 | 189.5 ms | **89.4 ms** |
| 범위 | 188.8–190.6 | 89.0–90.0 |

### 단계마다의 BFS (코어만, `bfs-run`, 노드 10만, 간선 999,937)

시간은 같은 빌드를 한 번(일곱 탐색의 중앙값), 명령과 사이클은 탐색 하나당(025의 `pcount`). 모든 줄의 답(거리, 닿은 노드 수,
실행량)이 실행기의 것과 같다(아래의 한 줄은 빼고).

| 단계 | 시간 | 명령 | 사이클 |
|---|---:|---:|---:|
| 전 (020 끝, `dde73e4`) | 187 ms | 867M | 448M |
| 1. 이벤트의 리스트를 배열로, 키로 찾아 읽기를 하나로 (`7d1e9dd`) | 126 ms | 702M | 300M |
| 3. 저장된 리스트의 디렉터리 (넣지 않음) | 130 ms | 677M | 316–320M |
| 실행기를 프레임과 step으로 (`5b2b58a`, JIT 없이) | 121.6 ms | 655M | 294M |
| 4. JIT 뼈대: 분기와 루프만, 나머지는 step 부르기 (`5b2b58a`) | 150 ms | 822M | 357M |
| ~~같은 뼈대, 처음 잰 것~~ | ~~60 ms~~ | ~~308M~~ | 답이 틀렸다: 닿은 노드 92,179 |
| JIT 2판: 뜨거운 명령을 코드로 (`0503439`) | 103 ms | 424M | 250M |
| JIT 3판: 트리의 항목을 런에서, 손가락의 잎에서 런 (`f3e3fe6`) | 89 ms | 319M | 213–229M |
| 끝: 루프가 있는 블록만 컴파일 (`b1b3c7b`) | 89–90 ms | 319M | 216–217M |

- 1단계가 HTTP에서는 처음에 효과가 없었다(191 ms에서 188.6 ms). 저장 뒤에 스냅숏이 모든 리스트를 나누면서, 비어 있는 이벤트의
  리스트까지 트리로 바꿔 다음 이벤트 내내 트리로 남겼다. 빈 리스트는 그대로 나누게 고친 뒤(`b66858e`) HTTP도 125 ms가 됐다.
- JIT 뼈대가 실행기보다 느렸던 것: 명령마다 `step` 함수를 부르는 값(레지스터 저장, 큰 switch)이 실행기 루프 안의 switch보다 크다.
  JIT이 이득을 내는 것은 명령을 코드로 쓴 뒤다.
- 지금 간선 하나는 기계어 명령 약 80개다: `ROW` 5, `ITEM_GET` 약 20(런 캐시의 검사), `HAS` 약 22, `NOT`과 `JZ` 8, 반복 약 25. 값이
  모두 메모리의 스택을 오가고, 행 번호를 수로 바꿨다가 다시 정수로 바꾼다.

### 지금의 앱

`runs.sh pairs 1 3`, `pairs 4 6`: TPC-C(RAM, 창고 하나, 터미널 64, 20초)와 은행 질의를 전과 후 번갈아 여섯 쌍, 부하 평균이 1.5
아래일 때 시작.

| 쌍 | 전 (초당) | 후 | 바뀜 | 거래당 CPU 전, 후 (µs) |
|---|---:|---:|---:|---:|
| 1 | 44,584 | 42,630 | −4.4% | 43.3, 45.3 |
| 2 | 45,341 | 43,259 | −4.6% | 43.2, 44.6 |
| 3 | 44,865 | 43,560 | −2.9% | 43.8, 44.5 |
| 4 | 44,245 | 42,781 | −3.3% | 44.5, 44.8 |
| 5 | 44,190 | 43,390 | −1.8% | 44.6, 44.7 |
| 6 | 44,224 | 43,069 | −2.6% | 44.4, 45.5 |
| 중앙값 | 44,415 | 43,164 | **−2.8%** | 44.1, 44.75 |

소유자 코어의 몫은 모두 0.88–0.90이다. 기준(3% 안)은 지나지만 여섯 쌍이 모두 느리니 잡음이 아니다.

**어디서 오나**(`runs.sh jit 1 4`): 후의 빌드 하나로 TPC-C를 JIT을 켜고(`PURE_JIT=1`) 끄고(`PURE_JIT=0`) 번갈아 네 쌍.

| 쌍 | JIT (초당) | 실행기 | 바뀜 |
|---|---:|---:|---:|
| 1 | 42,380 | 43,586 | −2.8% |
| 2 | 43,122 | 44,326 | −2.7% |
| 3 | 42,838 | 43,484 | −1.5% |
| 4 | 42,722 | 43,771 | −2.4% |
| 중앙값 | 42,780 | 43,679 | **−2.1%** |

TPC-C의 핸들러에도 루프가 있다(새 주문의 줄, 배달). 그 블록은 컴파일되지만, 안의 명령(키로 찾기, 넣기, 필드 쓰기)은 대부분 코드로
쓰지 않아 명령마다 `step`을 부른다. 그것이 실행기의 switch보다 비싸다(JIT 뼈대가 BFS에서 실행기보다 느렸던 것과 같은 까닭). 남는
0.7%쯤은 다른 실행에서 잰 것끼리라 나누지 않는다. 022의 JIT은 코드로 쓴 명령이 적은 블록을 컴파일하지 않거나, 그런 명령을 코드로
써야 한다.

은행 질의(여섯 번의 중앙값, ms): `per_branch` 5.25 → 5.15(−1.9%), `in_credit` 0.885 → 0.87(−1.7%), `large` 0.37 → 0.37,
`ranks` 6.755 → 6.705(−0.7%).

명령 수(`runs.sh counts`: 025의 `count.py`, 전과 후 두 번씩의 중앙값):

| 질의 | 명령 | 사이클 |
|---|---:|---:|
| `per_branch` | +0.3% | −6.8% |
| `in_credit` | −0.8% | −15.7% |
| `large` | +0.2% | −4.1% |
| `ranks` | +0.3% | −2.2% |
| `none` | +0.5% | +1.1% |
| `field` | +0.8% | −2.7% |
| `found` | −0.5% | −2.0% |

**고친 것.** 처음(`38e0280`)에는 루프가 없는 블록까지 모두 컴파일했다. 그때 `large`의 명령이 +15.7%, `field` +23.7%, `found`
+22.2%였다. 루프 없는 블록은 명령마다 `step`을 부르는 뼈대 그대로라 실행기보다 길었다. 루프가 있는 블록만 컴파일하고, 그런 블록이
없는 모듈은 JIT을 두지 않고, 프레임의 필드를 하나씩 채우고, `group_of`를 인라인한 뒤(`b1b3c7b`) 위의 표가 됐다.

### 기기 사이

033의 `record.py`(aup의 검사 중 `transients`와 `computing`: 예제의 `pure-run` 46번)를 `git archive`로 묶은 같은 소스(`b1b3c7b`,
aup `da7361a`)로 세 기기에서. Pi는 JIT으로, WSL2(x86-64)와 Mac(M3, macOS)은 실행기로 돈다. 029의 `compare.py`로 견주어
Pi와 WSL2 46번 모두 같고, Pi와 Mac 46번 모두 같다(출력, 오류, 종료 코드). 기록은 `2026-10-05-pi.jsonl`, `-wsl.jsonl`,
`-mac.jsonl`이다.

### 바닥: 저장된 리스트에서 조각을 찾는 값

`seekfloor.c`: 같은 분포의 간선 100만 개를 저장된 리스트(키 있는 B+트리)에 넣고, 노드 10만 개를 무작위 차례로, 노드마다 조각의 두
경계를 찾고 첫 간선의 필드를 읽는다(`slice_of`가 하듯). 같은 차례로 C의 오프셋 배열(`start[v]`, `start[v + 1]`, `to[start[v]]`).

| 노드 하나 | Pure (B+트리) | C (오프셋) |
|---|---:|---:|
| 다섯 라운드 | 372–388 ns | 21–29 ns |

`indexfloor.c`: 022에서 생각한 색인을 리스트 밖에서. 잎을 B+트리처럼 흩어 두고(항목 32개, 열 셋, 따로 할당해 차례를 섞었다),
키의 범위를 2의 거듭제곱 폭의 칸으로 나눠 칸마다 첫 항목의 잎과 자리, 위치를 둔다.

| 노드 하나 | 색인 | C |
|---|---:|---:|
| 칸에 항목 여덟, 원점을 폭에 맞춤 | 124–134 ns | 17–18 ns |
| 칸에 항목 서른둘 (폭이 노드 넷) | 376–469 ns | 17–19 ns |
| 원점을 맞추지 않음 | 351–374 ns | 19–21 ns |

C는 반복 하나가 명령 여덟 남짓이고 반복끼리 기다리지 않아, 노드마다의 DRAM 미스를 여럿 겹친다. B+트리는 뿌리에서 잎까지 서로
기다리는 읽기가 넷이고, 색인도 칸에서 잎의 표, 잎으로 기다리는 읽기가 셋이다.

### 바닥: 탐색 전체를 Pure의 표현으로

`bfsfloor.c`: `bfs-run`의 그래프로 탐색 전체를 손으로 쓴 C로, 형태마다 번갈아 아홉 탐색. 모든 형태의 답(거리, 닿은 노드 수)이
같다. 카운터는 이 스레드의 사용자 공간만(`perf_event_open`). 미리 읽기는 노드 i를 꺼낼 때 i + 16의 칸과 i + 8의 첫 간선이다.

- `c`: 033의 `bfs.c` 그대로(오프셋, `to`, `depth`, 큐 모두 32비트).
- `c_bits`: `bfs.c`에서 본 것을 비트로, `depth`는 볼 때만 쓴다(021의 "밝히는 것").
- `packed`: Pure의 표현을 그대로, 검사도 그대로. 간선은 저장된 키 있는 리스트를 열(키, `to`: 수)로 펴고 칸의 색인(칸마다 그 시작
  이상인 첫 위치, 칸은 2의 거듭제곱 폭, 원점을 맞춤)을 둔다. `seen`은 조밀한 이벤트의 리스트(키의 비트, `node`와 `depth`의 열),
  큐는 납작한 이벤트의 리스트. 실행량도 실행기처럼 매긴다.
- `narrow`: `packed`에서 열을 값에 맞게 좁힌다. `to`와 큐의 `node`는 u32, `seen`의 `depth`는 u8, `seen`의 `node` 열은 두지 않는다
  (조밀한 리스트의 키 열은 키 그 자체다).
- `ahead`, `narrow_ahead`, `c_ahead`: 각각에 미리 읽기를 더한 것.

| 탐색 하나의 중앙값 | 시간 | 명령 | 사이클 | IPC | 분기 미스 | L1D 미스 | LLC 미스 |
|---|---:|---:|---:|---:|---:|---:|---:|
| `c` | **9.89 ms** | 9.9M | 22.5M | 0.44 | 234k | 1,188k | 199k |
| `c_bits` | 12.01 ms | 14.9M | 28.6M | 0.52 | 204k | 496k | 215k |
| `packed` | 22.98 ms | 29.1M | 54.4M | 0.53 | 196k | 689k | 1,326k |
| `ahead` | 20.24 ms | 32.9M | 48.4M | 0.68 | 197k | 598k | 1,046k |
| `narrow` | 13.18 ms | 18.5M | 31.1M | 0.60 | 201k | 451k | 212k |
| `narrow_ahead` | **8.82 ms** | 21.7M | 20.5M | 1.06 | 201k | 261k | 169k |
| `c_ahead` | 7.79 ms | 11.4M | 17.6M | 0.65 | 231k | 1,004k | 189k |

- C의 시간은 DRAM이다(IPC 0.44). 간선의 줄을 처음 읽는 미스가 노드마다 하나둘이고, OoO가 그중 둘쯤을 겹친다.
- `packed`가 C의 2.3배인 것은 명령이 아니라 미스다. 노드의 표들(색인 390 KB, `seen`의 열 둘 1.6 MB, 큐 800 KB)이 L3(2 MB)를
  넘는다. C의 표들(오프셋, `depth`, 큐 각 400 KB)은 든다.
- 좁히면 미스가 C와 같아지고(212k), 남는 것은 명령(C의 1.9배)이다. 미리 읽으면 미스가 겹쳐 IPC가 1.06이 되고 C를 넘는다.
  다른 거리(i + 8에서 i + 64)로도 7.8–9.0 ms, 같은 실행의 C는 9.6–9.7 ms였다.
- `c_bits`가 C보다 느린 것: C의 `depth[to]`는 L1을 놓쳐도 L2에서 오고 OoO가 겹친다. 비트는 L1 미스를 반으로 줄이지만 명령이
  간선마다 다섯쯤 늘어 그 몫이 더 크다.
- `c_ahead`(C에 같은 미리 읽기)는 7.8 ms다. 기준은 커밋된 `bfs.c`이고, 이것은 맥락이다.

## 판정

미달부터.

- **HTTP로 잰 BFS: 미달.** Pure 90.0 ms, C 9.08 ms(9.9배).
- **코어만 잰 BFS: 미달.** Pure 89.4 ms. 기준은 C를 같은 프로세스에서 함께 돌리는 것이었는데, `bfs-run`은 C를 돌리지 않는다.
  같은 그래프의 C는 `bfsfloor`에서 9.6–9.9 ms다.
- **TPC-C: 통과**(−2.8%, 기준 3% 안). 다만 여섯 쌍 모두 느렸고, 그중 2.1%가 JIT이다(위).
- **은행 질의: 통과**(같거나 빠르다). **명령 수: 통과**(가장 큰 늘어남 +0.8%, 기준 1%).
- **최소 확인: 통과.** `test-module`(세 표현과 B+트리만의 리스트를 매 걸음 견주는 것 포함)과 `make check`, aup와 Vega의 검사가
  `PURE_JIT=1`과 `PURE_JIT=0`에서 모두 초록이다(`b1b3c7b`). 기기 사이 46번이 같다. 디렉터리는 넣지 않았으니 그 검사는 없다.
- **밝히는 것.** 단계마다의 시간은 위의 표다. C의 `depth`를 비트로 바꾼 변형은 12.0 ms로 C보다 느리다. 첫 탐색이 디렉터리를
  만드는 값은 없다(디렉터리를 넣지 않았다).

## 다음

C를 넘으려면 `bfsfloor`의 `narrow_ahead`에 가까워야 한다. 022에서 산수와 기준을 먼저 적는다. 필요한 것은 넷이다.

1. **저장된 키 있는 리스트를 배열로.** 바뀌지 않고 많이 찾는 리스트는 열의 배열과 칸의 색인으로 두고(찾기가 읽기 하나), 바뀌면
   트리로 돌린다. 스냅숏은 배열을 함께 쓴다.
2. **좁은 열.** 배열의 수 열은 값이 허락하는 가장 좁은 정수(u8, u16, u32)로 두고, 맞지 않는 값이 오면 넓힌다. 조밀한 리스트의 키
   열은 두지 않는다. 뜻(수는 수)은 그대로다.
3. **최적화하는 JIT.** 스택의 값을 레지스터에, 리스트의 표현과 열의 검사를 루프 머리로, 비교와 분기를 하나로, 이벤트의 리스트에
   넣기와 덧붙이기를 코드로. `narrow`의 명령 수(1,850만)에 가까워야 한다. 지금은 3억 1,900만이다.
4. **미리 읽기.** 루프가 차례로 읽는 리스트의 값으로 다른 리스트를 키로 찾으면, 몇 번 뒤의 값으로 그 칸과 첫 항목을 미리 읽는다
   (간접 접근의 소프트웨어 미리 읽기: 컴파일러의 일반적인 기법이다. BFS를 아는 코드가 아니다).

`narrow_ahead`가 C를 넘는 폭은 11%뿐이다. JIT이 손으로 쓴 C만큼 짧지 않으면 넘지 못한다. 그것도 022에 적고 잰다.