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
|
# 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`이 멈춘다.
- 전과 후(`9484700`, `dde73e4` 둘 다)의 은행 질의 일곱의 답이 바이트까지 같다(`same_answers.py`, `2026-10-04-same-answers.txt`).
- 기기 사이(033의 `record.py`, 029의 기록 방식): aup의 `transients`와 `computing` 검사가 돌리는 `pure-run` 46번이 Pi, WSL2(gcc 13),
M3 Mac(clang 21)에서 출력, 오류, 종료 코드까지 모두 같고, 그 모듈 넷의 바이트가 같다(`2026-10-04-{pi,wsl,mac}-record.jsonl`).
Mac의 기본 SDK(27.0)는 그 기계의 링커가 읽지 못해 26.5로 빌드했다(`SDKROOT`). WSL에서 처음 한 번 멈춘 것은 기록을 쓸 수 없는
경로를 준 내 명령 때문이었다(같은 경로로 다시 내면 같은 자리에서 멈추고, 맞는 경로로는 세 번 모두 통과했다).
- 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)).
|
