From 85a57b8eb2704565ef646f2415eedcd1386a4afd Mon Sep 17 00:00:00 2001
From: eunhhu <necpition205@gmail.com>
Date: Sun, 4 Oct 2026 21:36:04 +0100
Subject: Measure computing faster: a search 2.1 times as fast, TPC-C 4.1%,
 four fingers found and undone (121)

---
 docs/research/121-computing-faster.md | 160 ++++++++++++++++++++++++++++++++++
 1 file changed, 160 insertions(+)
 create mode 100644 docs/research/121-computing-faster.md

(limited to 'docs/research/121-computing-faster.md')

diff --git a/docs/research/121-computing-faster.md b/docs/research/121-computing-faster.md
new file mode 100644
index 0000000..db99568
--- /dev/null
+++ b/docs/research/121-computing-faster.md
@@ -0,0 +1,160 @@
+# 121 — 계산을 빠르게
+
+2026-10-04. [020](../design/020-computing-faster.md)의 1단계(키로 찾기를 싸게)를 잰다. 기준은 구현하기 전에 적어
+커밋했다(`1d8c1f1`). 처음 만든 것은 `9484700`이고, 잰 뒤에 손가락을 하나로 되돌리고(`316d701`) 루프의 끝 비교를 접었다
+(`dde73e4`). 판정은 `dde73e4`로 한다. 만들면서 설계와 달라진 것은 020의 "1단계에서 달라진 것"에 적었다.
+
+## 쉬운 말로
+
+- **BFS(노드 10만, 간선 100만) 한 번이 397 ms에서 187 ms가 됐다(2.1배).** 기준(200 ms 이하)을 채웠다. 같은 일을 CPython은 441 ms,
+  C는 9 ms에 한다. 이제 CPython보다 2.4배 빠르고, C의 약 20배다.
+- **나눠 말하면**: 약 395 ms에서 204 ms까지는 길을 바꾼 것이다. 이벤트의 키 있는 리스트가 키를 비트(작은 정수일 때)나 표로도 갖고
+  (`seen.has`가 트리를 내려가지 않는다), 키로 넣기를 한 번 내려가서 한다. 204 ms에서 185 ms까지는 거의 다 컴파일러다: 리스트의
+  파일(`module-list.c`) 하나를 `-O3`로 빌드했다. 자식 찾기를 세기로 바꾼 것은 `-O3`와 짝일 때만 싸다.
+- **지금의 앱도 빨라졌다**: TPC-C가 4.1%, 은행 질의 넷이 1.0–5.1%. 명령 수는 일곱 질의 모두 기준(늘면 1% 안) 안이다(가장 는 것이
+  +0.24%, 준 것은 −10.8%까지).
+- **처음 만든 것은 명령 수의 기준을 어겼다**(`field` +2.94%). 하나씩 바꾼 빌드로 세어 보니 원인은 스레드마다 손가락을 넷으로 늘린
+  것이었다. 그것은 BFS도 빠르게 하지 않았다. 하나로 되돌렸다(원래 하나였다).
+
+## 결과
+
+원시 결과와 명령은 [036-faster-loops](../../research/experiments/036-faster-loops/)에 있다(`runs.sh`, `bfs-run.c`, `pairs.py`,
+`same_answers.py`, `bfscount.py`). 전은 `1d8c1f1`(기준의 커밋, 코드는 `313074a`와 같다), 후는 `dde73e4`다. 처음의 후(`9484700`)로 잰
+것은 `2026-10-04-four-*`에 있다.
+
+### BFS 한 번, 코어만 (`bfs-run`)
+
+`bfs-run.c`: 033의 `graph.aup`를 코어로만 돌린다(호스트도 저장소도 없다). 무작위 그래프(노드 100,000, 간선 999,937, 시드 121)를
+행으로 넣고, 정해진 출발 일곱 곳에서 BFS를 한 번씩 하고 그 중앙값을 낸다. 전과 후를 번갈아 여섯 쌍(`runs.sh core`).
+
+| 쌍 | 1 | 2 | 3 | 4 | 5 | 6 | 중앙값 |
+|---|---:|---:|---:|---:|---:|---:|---:|
+| 전 | 436.1 | 397.1 | 396.2 | 393.5 | 397.5 | 400.6 | 397.3 ms |
+| 후 | 186.5 | 188.0 | 186.5 | 186.7 | 188.1 | 187.6 | 187.2 ms |
+
+처음의 후(`9484700`, 손가락 넷)는 여섯 쌍의 중앙값이 185.3 ms(전 396.2 ms)였다.
+
+어디서 줄었는가(같은 `bfs-run`, 한 번씩 쟀다, 만든 차례대로):
+
+| 단계 | 중앙값 |
+|---|---:|
+| 전 | 394 ms |
+| 소속 표(열린 주소의 표만)와 손가락 | 286 ms |
+| 작은 정수 키는 비트로 | 207 ms |
+| 키로 넣기를 한 번 내려가서(`pure_list_add`) | 204.5 ms |
+| 항목 필드의 text 여부를 로드할 때, 손가락 넷과 앞으로 옮기기 | 약 206 ms |
+| 재귀 없는 루프 | 203.7 ms |
+| 자식 찾기를 세기로 | 204.7 ms |
+| 잎의 울타리 | 206.7 ms (뺐다) |
+| `module-list.c`를 `-O3`로 | 185.7 ms |
+| 손가락을 하나로 되돌리기 (`316d701`) | 183.2–184.1 ms |
+| 루프의 끝 비교를 접기 (`dde73e4`) | 186.5–189.8 ms |
+
+- 표만으로 286 ms였던 것은 키 하나를 찾는 데 캐시 미스가 하나 남기 때문이다(10만 키의 표는 2 MiB). 노드 번호는 작은 정수라 비트로
+  12.5 KB이고 L1/L2에 든다.
+- 마지막 줄은 일을 줄이고 시간을 늘렸다. `bfscount.py`(025의 `pcount`)로 세면 탐색 하나에 명령은 888M에서 867M으로 2.4% 줄고
+  사이클은 440M에서 448M으로 1.9% 는다. 같은 바이너리에서는 늘 그렇다(번갈아 다섯 번). 일이 아니라 코드의 자리와 분기 예측의 몫이다.
+  일이 적고 코드가 짧은 쪽을 남겼다(은행 질의의 명령 수도 줄었다: `field` +0.80%에서 +0.24%).
+- 남은 187 ms의 대부분은 간선의 B+트리를 걷는 메모리 미스(새 노드마다 잎과 그 위의 몇 단)와 실행기의 명령 디스패치(명령 하나에
+  약 6 ns)다. 코어만의 미세 측정(같은 빌드, 반복 하나에): 세기만 하는 반복 29에서 24 ns, 리스트 걷기 45에서 41 ns, 덧붙이기
+  163에서 128 ns.
+
+### BFS 한 번, HTTP로 (033의 `bfs.py`)
+
+118과 같다: 무작위 그래프(노드 100,000, 간선 1,000,000, 시드 118)를 `pure-serve`(RAM, 코어 0–2)에 넣고 출발 다섯 곳에서 BFS를 한
+이벤트씩, C와 CPython이 같은 탐색을 한다(`runs.sh bfs before`, `runs.sh bfs after`). 세 쪽의 거리와 닿은 노드 수(99,996)가 같다.
+
+| 중앙값 | C | CPython | Pure 전 | Pure 후 |
+|---|---:|---:|---:|---:|
+| BFS 한 번 | 9.0 ms | 449 ms | 397.5 ms | **190.9 ms** |
+
+Pure는 C의 44배에서 21배로, CPython의 0.88배에서 0.43배로 왔다. HTTP로 잰 것과 코어만 잰 것의 차이(약 4 ms)는 요청과 저장이다.
+
+### 지금의 앱: TPC-C와 은행 질의, 명령 수
+
+`runs.sh pairs`(033과 같다: TPC-C는 RAM, W=1, 64터미널, 20초; 은행 질의), 전과 후를 번갈아 여섯 쌍. `runs.sh counts`: 025의
+`count.py`로 은행 질의 일곱의 묻기 한 번당 사용자 모드 명령 수(전, 후, 전, 후).
+
+처음의 후(`9484700`, 손가락 넷):
+
+| | 전 | 후 | 바뀜 |
+|---|---:|---:|---:|
+| TPC-C 중앙값(초당) | 43,181 | 44,729 | +3.6% (여섯 쌍 모두 +2.8–+5.2%) |
+| per_branch | 5.29 ms | 5.25 ms | −0.9% |
+| in_credit | 0.845 ms | 0.825 ms | −2.4% |
+| large | 0.38 ms | 0.37 ms | −2.6% |
+| ranks | 6.80 ms | 6.73 ms | −1.0% |
+| 명령 수: field | | | **+2.94%** |
+| 명령 수: found | | | −5.8% |
+| 명령 수: 나머지 다섯 | | | −1.5–+0.9% |
+
+**명령 수의 기준(늘면 1% 안)을 `field`가 어겼다.** `field`는 거래 2만 행 가운데 `delta > 0`인 행의 `aid`를 읽는 표다(행마다
+셀 하나). 두 빌드의 답은 일곱 질의 모두 바이트까지 같다(같은 일을 한다). 샘플로 본 함수의 몫은 바뀌지 않은 함수까지 움직여서
+(`put_bytes` 9.7%에서 6.9%) 이 크기를 가르지 못했다. 그래서 하나씩 바꾼 빌드로 셌다(전 대비):
+
+| 빌드 | field | found | large |
+|---|---:|---:|---:|
+| 후(손가락 넷, `-O3`) | +2.94% | −5.8% | +0.3% |
+| 후, `module-list.c`를 `-O2`로 | +3.61% | +18.7% | +8.0% |
+| 후, 손가락 없이 | +7.51% | −4.2% | +0.6% |
+| 옛 `module.c` + 새 리스트 | +2.04% | −6.4% | −0.2% |
+| 그 위에서 `-O2` | +2.71% | +18.1% | +7.5% |
+| 그 위에서 옛 이분 탐색 | +2.29% | −6.3% | +0.2% |
+| 그 위에서 손가락 하나 | **−0.31%** | **−9.8%** | **−3.0%** |
+
+- 옛 코드에도 손가락이 하나 있었다(스레드마다 마지막 잎). 넷(리스트마다 하나, 맞은 것을 앞으로)은 그것보다 명령이 더 들었다.
+  코어만의 BFS도 하나로 빠르다(세 번의 중앙값: 하나 183.2 ms, 둘 185.0 ms, 넷 184.8 ms). 그래서 하나로 되돌렸다(`316d701`).
+- `-O3`는 자식 찾기를 세기로 바꾼 것과 짝이다: 가지 32개를 모두 비교하는 세기는 벡터가 될 때 싸고, `-O2`이면 `found`가 18%
+  늘어난다.
+- 옛 `module.c`로 되돌리면 `field`가 0.9%포인트 준다. 실행기의 재귀 없는 루프는 명령마다 비교 하나(`pc == loop_end`)를 더한다.
+
+**`dde73e4`로 다시 쟀다**(여섯 쌍, 명령 수는 전과 후를 네 번씩):
+
+| | 전 | 후 | 바뀜 |
+|---|---:|---:|---:|
+| TPC-C 중앙값(초당) | 42,996 | 44,771 | **+4.1%** (여섯 쌍 모두 +3.4–+6.4%) |
+| per_branch | 5.26 ms | 5.21 ms | −1.0% |
+| in_credit | 0.845 ms | 0.83 ms | −1.8% |
+| large | 0.39 ms | 0.37 ms | −5.1% |
+| ranks | 6.78 ms | 6.68 ms | −1.5% |
+
+| 명령 수(중앙값) | 바뀜 | 네 쌍 |
+|---|---:|---|
+| per_branch | −0.97% | −0.84, +0.30, −1.32, −1.43 |
+| in_credit | −0.02% | +0.20, +2.21, −0.62, −0.82 |
+| large | −3.33% | 넷 모두 −3.33 |
+| ranks | +0.12% | +0.19, +0.89, −0.09, −0.16 |
+| none | +0.17% | 넷 모두 +0.17–+0.18 |
+| field | +0.24% | 넷 모두 +0.24 |
+| found | −10.84% | 넷 모두 −10.84–−10.85 |
+
+in_credit의 둘째 쌍(+2.21%)은 한 쌍으로는 기준을 넘는다. 그 질의는 같은 바이너리로도 실행마다 흔들린다: 전의 네 번이 3,443,329에서
+3,503,100(1.7%)까지다. 네 쌍의 중앙값으로 판정한다.
+
+### 검사
+
+- `test-module`의 `key_sets`: 키를 비트와 표로 갖는 리스트가 무작위 12만 걸음(넣기 4만 5천, 지우기 2만, 키 바꾸기 1만 3천, 되돌린 것
+  9,799)의 매 걸음에 모델 배열과 같은 답을 낸다(`has`, 키로 넣기의 자리와 있음, 키로 찾기, 위치로 읽기, 차례로 읽기). 키가 비트에서
+  표로 일곱 번 바뀌고, 비우기 12번(64 KiB 넘는 비트는 버리고 다시), 표의 사슬 가운데서 지우기(뒤를 당긴다), 음수와 분수 키, `-0`.
+  스냅숏의 사본(같은 리스트, 다른 판)과 다른 리스트 넷을 사이사이 읽어 손가락이 다른 리스트나 다른 판의 잎을 내주지 않는다.
+- `keyed_journal`: 저장되는 키 있는 리스트의 키로 넣기(이미 있는 키 1,156번, 되돌린 이벤트 607번, 키 바꾸기와 지우기 포함)가 적은
+  기록을, 통째로 저장한 항목 뒤에 다시 하면 그 리스트다(재시작 59번).
+- 두 검사가 잡는지 일부러 망가뜨려 봤다: 표에서 지울 때 뒤를 당기지 않으면 `key_sets`가, 손가락이 판을 보지 않으면 공유 검사가,
+  키로 넣기가 기록의 길이를 더하지 않으면 `keyed_journal`이 멈춘다.
+- 두 빌드(전과 처음의 후)의 은행 질의 일곱의 답이 바이트까지 같다(`same_answers.py`).
+- Pure의 `make check`(ASan 포함), aup와 Vega의 모든 검사가 초록이다(`dde73e4`).
+
+## 판정
+
+- **020의 1단계는 들어간다.** BFS는 기준(200 ms 이하) 안이고(187.2 ms, 2.1배), TPC-C와 은행 질의의 시간은 빨라졌고, 명령 수는
+  네 쌍의 중앙값으로 일곱 모두 1% 안이다.
+- 처음 만든 것(`9484700`)은 명령 수의 기준을 어겼다(`field` +2.94%). 원인을 하나씩 바꾼 빌드로 찾아(손가락 넷) 되돌린 뒤 다시 쟀다.
+- 줄어든 약 210 ms 가운데 약 20 ms(204에서 약 185)는 컴파일러의 `-O3`다. 그것은 세기로 바꾼 자식 찾기와 짝이라 `-O2`로 내리면
+  명령 수가 오히려 는다(`found` +18%).
+
+## 다음
+
+- 남은 시간은 간선의 B+트리를 걷는 메모리 미스와 명령 디스패치다. 간선의 조각을 잎 단위로 걷는 것(행마다 `pure_list_get`이
+  아니라 조각의 열을 한 번에), 이벤트의 리스트를 B+트리가 아닌 배열로 두는 것(이벤트의 리스트는 나누지도 저장하지도 않는다)을
+  잴 수 있다. 측정이 요구할 때.
+- 020의 2단계: 긴 보기를 연결 스레드 밖에서([122](122-views-off-the-connection-threads.md)).
-- 
cgit v1.2.3