Measure 021: BFS 190 to 90 ms over HTTP against C's 9.1, short of C; Pure's forms by hand beat C only packed, narrow and read ahead (123)

2 files changed, 218 insertions, 1 deletions

diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md
index 5ff1c61..f6f6072 100644
--- a/docs/design/021-past-c.md
+++ b/docs/design/021-past-c.md
@@ -1,6 +1,7 @@
 # 021 — C보다 빠르게
 
-작성일: 2026-10-05. 상태: 1–4단계를 구현해 쟀다. 아래 "바로잡음"이 처음의 산수를 고친다.
+작성일: 2026-10-05. 상태: 1–4단계를 구현해 쟀다([123](../research/123-past-c.md)). C를 넘지 못했다(HTTP로 90 ms, C 9.1 ms).
+아래 "바로잡음"이 처음의 산수를 고친다. C를 넘는 길은 123의 "다음"이다.
 [020](020-computing-faster.md)이 BFS(노드 10만, 간선 100만) 한 번을 397 ms에서 187 ms로 줄였다([121](../research/121-computing-faster.md)).
 같은 탐색을 C(033의 `bfs.c`: 인접을 오프셋 배열로, 깊이는 `int32_t` 배열)는 9 ms에 한다. 목표는 그 C보다 빠른 것이다. 같은
 aup 코드, 같은 뜻(키 있는 리스트, 인덱스는 위치, 결정적인 결과), 같은 기계에서.
diff --git a/docs/research/123-past-c.md b/docs/research/123-past-c.md
new file mode 100644
index 0000000..4ebe94f
--- /dev/null
+++ b/docs/research/123-past-c.md
@@ -0,0 +1,216 @@
+# 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에 적고 잰다.