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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
# 022 — 배열과 레지스터로 C를 넘기
작성일: 2026-10-05. 상태: 1–4단계를 만들었다(아래 "만들며 정한 것"). 코어 BFS는 C보다 빠르지만 미리 읽기 덕이고, 깡연산으로는
C의 1.6배 느리다. 기준은 [023](023-optimizing-tier.md)의 묶음으로 옮긴다(아래 "3단계를 마치며").
[021](021-past-c.md)은 BFS(노드 10만, 간선 100만) 한 번을 190 ms에서 90 ms로 줄였지만 C(9.1 ms)를 넘지 못했다
([123](../research/123-past-c.md)). 123의 바닥은 길이 있다고 말한다: Pure의 표현대로 손으로 쓴 C가 C를 넘는 것은 저장된 리스트가
배열이고, 열이 값만큼 좁고, 다음 노드를 미리 읽을 때뿐이다. 목표는 그대로다. 같은 aup 코드, 같은 뜻, 같은 기계에서 C보다 빠르게.
## 산수: 재어 본 것
모두 Pi 5(Cortex-A76 2.4 GHz, L2 512 KB, L3 2 MB), RAM. `bfsfloor.c`는 [038](../../research/experiments/038-past-c/)에 있다.
**C의 자리.** `bfs.c`는 탐색 하나를 21번 돌려 중앙값을 낸다(표가 데워진 채로).
| | 그래프 | C |
|---|---|---:|
| 033의 `bfs.py` (HTTP 기준이 견주는 C) | `bfs.py`의 것(시드 118) | 9.03–9.08 ms |
| `bfsfloor c`, 한 프로세스에 한 형태 (`-alone`) | `bfs-run`의 것(시드 121) | 9.42–9.56 ms |
**바닥.** 같은 방법(한 프로세스에 한 형태, 21번의 중앙값, 세 라운드)으로 손으로 쓴 Pure의 형태
(`2026-10-05-bfsfloor-alone.jsonl`):
| 형태 | 시간 |
|---|---:|
| `packed`: 저장된 리스트를 배열과 칸의 색인으로, 열은 모두 수(8바이트) | 23.1–23.3 ms |
| `narrow`: 열을 값만큼 좁게(u32, u8), 조밀한 리스트의 키 열은 두지 않음 | 12.8–13.0 ms |
| `narrow_ahead`: 그리고 큐의 앞 노드(16번 뒤의 칸, 8번 뒤의 첫 간선)를 미리 읽음 | **8.26–8.66 ms** |
| `c_ahead`: C에 같은 미리 읽기 (맥락) | 7.06–7.13 ms |
- `narrow_ahead`는 같은 그래프의 C보다 8–12% 빠르다. 명령은 C의 2.2배(2,170만 대 990만)이고, 이기는 것은 미스를 겹쳐서다(IPC
1.06 대 0.44).
- 이것이 이 설계가 닿을 수 있는 가장 좋은 자리로 본다. JIT이 내는 코드는 손으로 쓴 C보다 길기 쉽다.
**칸의 폭**(`2026-10-05-bfsfloor-widths.jsonl`). 칸의 폭이 조각의 경계(`node * 2^20`)의 배수가 아니면 경계가 칸 안에 떨어지고,
찾기가 키 열(8바이트, 8 MB)을 읽는다:
| 칸 하나의 항목 (폭) | 칸 | `narrow_ahead` |
|---|---:|---:|
| 8 (2^20) | 100,001 | 8.26–8.66 ms |
| 4 (2^19) | 200,000 | 8.99–9.10 ms |
| 16 (2^21) | 50,001 | 22.3–22.7 ms |
| 32 (2^22) | 25,001 | 28.5 ms |
폭을 항목 수만으로 고르면(021의 디렉터리처럼) 이 그래프에서는 우연히 맞고, 노드마다 간선이 다섯이면 2^21이 되어 세 배 느려진다.
그래서 폭은 **찾은 키에 맞춘다**(아래 1). 키를 `앞 * 2^k + 뒤`로 합쳐 앞으로 조각을 찾는 것은 aup에서 인접을 쓰는 방법이다(TPC-C도
`order * 16 + line`이다). BFS만의 모양이 아니다.
**HTTP의 몫.** 같은 앱에 거의 일이 없는 쓰기(`POST /inputs/size`)의 왕복이 0.15 ms(읽기 0.08 ms)다. 021에서 HTTP로 잰 Pure는
코어만 잰 것보다 0.6 ms 길었다(90.0 대 89.4, 그래프가 다르다). 그래서 HTTP 기준(Pure < 9.08 ms)에는 코어 8.48 ms 아래가 필요하다.
**그래서:**
- 코어의 기준(같은 프로세스의 C보다 빠르게)은 JIT의 코드가 바닥의 1.10배 안이면 선다.
- HTTP의 기준은 코어가 바닥의 중앙값(8.59 ms)보다 조금 짧아야 선다. **산수로 반반이다.** 바닥보다 짧아질 여지는 있다: 바닥은 루프의
`i`를 수로 세고, 칸을 수로 계산하고, 미리 읽기가 같은 계산을 두 번 한다. JIT은 그것을 정수로 할 수 있다. 그래도 미달이면 미달로
적는다.
- 지금의 JIT은 간선 하나에 약 80 명령, BFS 하나에 3억 1,900만이다. 바닥은 2,170만이다. 15배를 줄이는 일이다.
## 원칙
- **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트, 인덱스는 위치, 수는 수(−0은 −0)다. 표현과 실행의 길만 바뀐다. 어느 길로
가든 결과(값, 결함, 실행량, 메모리의 몫)는 바이트까지 같다.
- **벤치마크의 모양을 넣지 않는다.** 칸의 폭은 찾은 키에서, 미리 읽기는 "차례로 읽은 값으로 다른 리스트를 찾는" 일반적인 모양에서
온다. 코드에 그래프나 `1048576`을 아는 곳은 없다.
- **모든 길이 끝까지 간다.** 빠른 길은 가정(리스트의 표현, 열의 폭, 칸의 색인)을 루프 머리에서 확인하고, 가정이 깨지면 그 자리에서
일반적인 코드로 넘어간다. 일반적인 코드는 지금의 JIT과 실행기다.
- **값은 일이 쓴 만큼.** 배열과 색인은 많이 찾는 리스트에만 만든다. 바뀌면 버린다. 둘 다 그 비용을 산수로 정한다.
## 모양
### 1. 저장된 키 있는 리스트를 배열로 펴기
- **언제.** 수로 키를 둔 저장된 리스트(항목 4,096 이상)가 한 판(version)에서 키로 찾기를 항목 수의 8분의 1번 넘게 받으면, 그 판을
배열로 편다: 필드마다 열 하나(이벤트의 리스트의 FLAT과 같은 모양)와 칸의 색인. 펴기는 O(n)이고 열을 한 번 베낀다(항목 하나에
몇 ns로 본다; 재서 적는다). 트리에서 찾기 한 번이 수백 ns이니, 펴기 전의 n/8번의 찾기(항목 하나에 수십 ns)가 펴기보다 크다.
- **바뀌면 트리로.** 편 리스트에 바뀜(넣기, 지우기, 고치기, 비우기)이 오면 먼저 트리로 돌린다(O(n), 정렬된 배열에서 아래부터
짓는다). 바뀌는 리스트는 판마다 찾기를 다시 세니 다시 펴지지 않는다. 그래서 TPC-C처럼 늘 바뀌는 리스트는 늘 트리다.
- **칸의 색인.** 칸마다 그 칸의 시작 키 이상인 첫 위치(u32). 칸은 2의 거듭제곱 폭이고 원점은 폭의 배수다. 폭은 펼 때까지 찾은
키들의 정렬(원점과의 차의 끝에 있는 0 비트 수의 가장 작은 것)과 항목 수(칸 하나에 항목 여덟)에서 작은 쪽이다. 칸은 항목 수를
넘지 않는다(색인이 항목 하나에 4바이트를 넘지 않는다). 찾기: 칸을 곱셈 하나로 내고, 키가 칸의 시작이면 그 칸의 첫 위치가 답이다
(읽기 하나). 아니면 거기서 키 열을 앞으로 본다.
- **나누기.** 스냅숏의 사본은 편 배열을 함께 쓴다(참조 수). 배열은 펴진 동안 바뀌지 않는다. 트리로 돌릴 때 배열을 놓는데, 사본이
쥐고 있으면 참조만 줄인다. 텍스트는 지금처럼 리스트가 갖고, 놓을 때는 지금의 판(epoch)으로 늦춘다.
- **저널, 인코딩, 메모리의 몫.** 저널은 바뀜에서 나오는데 바뀜은 트리에서 일어나니 그대로다. 인코딩은 배열을 차례로 읽는다.
`bytes`(상태의 몫)는 표현과 상관없다. 배열은 트리보다 작다(잎에는 빈 자리와 머리가 있고, 안쪽 노드가 있다).
- 1단계만으로 지금의 JIT에서 BFS의 조각 찾기(노드마다 두 번)가 읽기 하나가 된다.
### 2. 좁은 열
- 배열(이벤트의 리스트의 FLAT과 DENSE, 편 리스트)의 수 열마다 폭이 있다: u8, u16, u32(0 이상의 정수, −0이 아닌), 그리고 수(8바이트).
처음 값이 들어갈 때 가장 좁은 폭에서 시작하고, 맞지 않는 값이 오면 열 전체를 그 값이 들어가는 폭으로 넓힌다(열마다 많아야 세 번).
i64와 텍스트의 열은 그대로다.
- 조밀한(DENSE) 리스트는 키 필드의 열을 두지 않는다. 그 칸은 키 그 자체다.
- 읽기는 폭을 보고 넓혀 읽는다. 이것만으로는 명령이 늘 수 있다. 2단계는 3단계와 함께 잰다. 혼자서는 시간이 그대로일 수 있다.
### 3. 최적화하는 JIT
지금의 JIT은 값을 메모리의 스택에 두고, 명령마다 리스트의 표현을 다시 보고, 수와 정수를 오간다. 바꿀 것:
- **스택의 값을 레지스터에.** 블록을 옮길 때 컴파일 중의 스택(상수, 수의 레지스터, 정수의 레지스터, 조건 플래그, 메모리)을 들고
간다. C를 부르기 전과 분기가 모이는 곳에서만 메모리에 내린다.
- **정수로 아는 값은 정수로.** 행 번호, 좁은 열에서 읽은 값, 개수, 루프의 셈은 정수 레지스터에 둔다. `has`와 항목 읽기는 그 정수를
그대로 쓴다(수로 바꿨다가 되돌리지 않는다). 수가 필요한 곳에서만 바꾼다.
- **루프 머리의 가정.** `EACH`와 `LOOP`이 열릴 때, 본문이 쓰는 리스트마다 표현, 열의 주소와 폭, 키 비트의 주소와 크기, 개수와
자리를 레지스터에 쥐고 확인한다. 본문 안에서는 그 리스트를 바꿀 수 있는 명령(그 리스트에 넣기, 덧붙이기, 고치기, 지우기, 그리고
그런 C 부르기) 뒤에서만 다시 읽고 확인한다(어느 명령이 어느 리스트를 바꾸는지는 로드할 때 안다). 가정이 깨지면 스택을 내리고
같은 자리의 일반적인 코드로 넘어간다.
- **비교와 분기를 하나로.** 비교, `NOT`, `has` 뒤의 `JZ`는 플래그나 비트의 분기 하나다.
- **이벤트의 리스트에 쓰기를 코드로.** 조밀한 리스트에 키로 넣기(키가 자리 안이고 없을 때), 납작한 리스트에 덧붙이기(자리가 있을
때)는 코드로 한다. 아니면 C를 부른다.
- **값이 맞는 블록만.** 루프의 본문에 코드로 쓴 명령이 적은 블록은 컴파일하지 않는다(123: TPC-C의 루프는 명령마다 `step`을 불러
2.1% 느렸다).
### 4. 미리 읽기
루프가 차례로 읽는 리스트(A)의 값으로 다른 리스트(B)를 키로 찾거나 조각을 걸으면(그 사이가 결함 없는 산술뿐이면), 루프 머리에서 몇
번 뒤의 A의 값으로 같은 계산을 해 B의 칸과 첫 항목을 미리 읽는다(prefetch). A가 아직 그만큼 길지 않으면 하지 않는다. 미리 읽기는
결과를 바꾸지 않는다. 간접 접근의 소프트웨어 미리 읽기는 컴파일러의 일반적인 기법이다(Ainsworth와 Jones, CGO 2017).
## 만들며 정한 것 (2026-10-05)
1–4단계를 처음으로 만든 판(`1e8c168`, 코어 BFS 14.9 ms)까지 정한 것과 달라진 것.
- **펴기는 이벤트가 끝난 뒤에만.** 이벤트 도중에 펴면 도는 fold의 런이 쥔 잎이 풀린다. 그래서 소유자 스레드가 이벤트를 끝낼 때
(`dispatch`) 판(version)에서 많이 찾은 리스트를 편다(`pure_list_settle`). 첫 이벤트는 트리로 돌고 끝에서 펴진다. 펴기와 트리로
돌리기 모두 판을 올린다(손가락, 런 캐시, fold의 패스, 스냅숏이 판으로 무효가 된다). 트리는 잎부터 지어 O(n)이다. 사본만 찾는
리스트(보기만 찾는)는 펴지지 않는다(다음 일).
- 문턱: 항목 4,096 이상, 판 하나에서 키로 찾기가 항목의 8분의 1(`PACK_SEARCHES`). 칸 하나에 항목 여덟을 기준으로, 찾은 키의 끝 0
비트 수가 허락하면 그 폭으로 좁힌다. 색인은 항목 수보다 칸이 많지 않다. 키가 모두 2^53 아래의 정수면 색인을 정수로도 둔다
(`whole`, 시프트, 원점): 찾기와 JIT의 조각 열기가 정수로 한다.
- **좁은 열의 폭은 1, 4, 8바이트**다(설계의 u16은 두지 않았다: 폭을 고르는 분기가 짧다). 수와 bool만 좁히고 −0은 좁히지 않는다.
FLAT 리스트의 키 열은 늘 8바이트(수로 찾는다), DENSE 리스트는 키 열을 두지 않고 −0은 DENSE의 키가 되지 않는다(그 칸은 키 그
자체라 +0으로 읽힌다). 비운 리스트가 DENSE였으면 배열을 놓는다(키 열이 없다). 런(`PureRun`)은 좁은 칸을 넓혀 담을 자리(4 KiB)를
갖는다.
- **JIT은 열의 주소 윗바이트에 폭을 적는다**(비트 56, 58, 59). AArch64 리눅스는 사용자 공간 주소의 윗바이트를 읽을 때 보지 않는다
(Documentation/arch/arm64/tagged-pointers.rst, TBI). 그래서 폭마다 레지스터를 더 쓰지 않는다. 리눅스 AArch64에서만 JIT이 있으니
이 가정은 그 안에 있다.
- 가둔 값은 루프 묶음(가장 바깥 루프와 그 안의 루프)마다 레지스터 하나씩이고, 묶음의 모든 레이블에서 다 읽혀 있다. C를 부르면
다시 읽는다. 편 리스트의 조각 루프는 코드로 연다(정수 칸). `ITEM_GET` 바로 뒤의 `has`는 하나로 한다(칸을 키로 곧장).
- 미리 읽기: 루프 몸체를 처음부터 기호로 따라가, 안쪽 조각 루프의 아래 경계가 루프의 셈에서 나오면(리스트의 항목, 그리고 산술)
16회 뒤의 칸과 8회 뒤의 첫 칸을 읽는다(`AHEAD_FAR`, `AHEAD_NEAR`, 바닥에서 잰 거리). 칸은 범위를 보지 않는다(PRFM은 결함을
내지 않는다). 첫 칸을 읽을 때만 칸 번호를 확인한다.
- **남은 몫**(덤프로 센 것, 탐색 하나 5,780만 명령, 3,965만 사이클): 노드 하나에 약 280명령(미리 읽기 45, 몸체 50, 조각 열기
130, 나가기와 바깥 반복 35, ...), 넣기 하나에 약 150, 간선 하나에 약 10. 바닥은 노드 93, 넣기 12다. 정수 가정만으로는 넣기에서
약 33, 노드에서 약 55가 줄어 4,900만이다(사이클로 C를 넘지 못한다). 나머지는 장부다: 노드마다 안쪽 루프의 프레임(루프 구조체,
이벤트의 행과 걷기, 프레임의 끝과 깊이)을 쓰는 약 40, 덧붙이기마다 개수·판·바이트·메모리 몫과 그 검사 약 25.
- **그래서 3단계를 이렇게 마친다.**
1. 정수 가정: 좁은 열(1, 4바이트)에서 읽은 값, 행 번호, 개수, 정수인 루프의 셈, 그것들의 정수 산술(결과가 2^53 안이고 −0이
생기지 않을 때)은 정수 레지스터에 둔다. 열이 8바이트이거나 산술이 범위를 넘으면 가정이 깨진다.
2. 가정이 깨지면 그 루프 회차의 남은 부분을 실행기가 한다(`pure_run_rest`): 스택을 수로 내리고, 걷기의 자리를 쓰고, 그 명령부터
루프의 끝까지 실행기가 돈 뒤 돌아와 다음 회차를 코드로 한다(BREAK면 루프 밖으로). 모든 길이 끝까지 간다는 원칙이 그대로다.
3. 바뀌는 장부를 레지스터에: 안쪽 루프의 프레임은 C를 부를 때만 쓰고 돌아오면 거둔다. 덧붙이기의 개수와 여분, 판, 바이트,
메모리 몫은 레지스터에서 세고 C를 부르기 전과 루프를 나갈 때 쓴다(걷기의 자리처럼).
### 3단계를 마치며 (2026-10-05 오후)
위의 셋 중 1, 2와 3의 장부 몫을 만들었다. 단계마다 코어 BFS(`bfs-run`, 탐색 하나의 중앙값)와 탐색 하나의 명령·사이클
(`perf_event`, 사용자 공간):
| 커밋 | 바꾼 것 | 시간 | 명령 | 사이클 |
|---|---|---:|---:|---:|
| `ddc8ba0` | 정수 가정, `pure_run_rest` | 14.6 ms | 5,780만 | 3,520만 |
| `e8d213b` | 장부를 레지스터에 | 12.5 ms | 4,620만 | 3,030만 |
| `4537289` | 작업량을 레지스터에, x30, 산술 다듬기 | 12.2 ms | 4,300만 | 3,030만 |
| `1aa334d` | 정수로 미리 읽기, 칸의 마지막 셀도 | 8.6 ms | 4,170만 | 2,070만 |
| `e9e0d22` | 간선 루프에서 확인 셋을 덜기 | 7.4 ms | 3,840만 | 1,790만 |
- **장부.** 묶음이 덧붙이는 FLAT 리스트의 개수(LIVE), DENSE 리스트에 더한 항목 수(PENDING), 이벤트가 더 자랄 수 있는 바이트
(HEADROOM, 예산과 여분 중 작은 쪽), 이벤트가 더 할 수 있는 일(WORK)을 레지스터에 둔다. C를 부르기 전(`write_back`), 결함에서,
묶음을 나갈 때(`join`, 묶음 밖으로 가는 `JZ`) 리스트와 앱에 쓴다. 장부는 읽혀 있을 때만 바뀌므로, 읽혀 있지 않은 장부는 쓸 것이
없다(그래서 줄 밖 길은 명령이 시작할 때 읽혀 있던 것만 쓴다). 개수를 읽는 곳(개수, 항목의 경계, 위치 옮기기, 걷기의 끝, 미리
읽기)은 장부의 개수를 본다. 레지스터가 모자라 장부를 다 두지 못하는 리스트는 예전처럼 메모리에 쓴다.
- **안쪽 루프의 프레임은 레지스터에 두지 않았다**(위 3의 앞 절반). 미스를 겹친 뒤로는 명령이 아니라 미스와 분기 예측이 시간을
쥐어서 미뤘다.
- **C를 넘은 것은 미리 읽기 덕이다. 깡연산으로는 아직 C보다 느리다.** 프로파일에서 사이클의 21%가 간선 열을 읽은 바로 뒤에
있었다. 노드의 간선(약 10개, 40바이트)은 64바이트 줄을 넘는 일이 잦은데(약 60%) 바닥도 JIT도 첫 셀만 읽었다. 칸의 끝
(`first[b + 1]`)을 이미 읽으니 마지막 셀도 미리 읽는다. 사이클이 3,030만에서 2,070만이 됐다. 그러나 이것은 C가 하지 않는 일을
한 것이다: C에 같은 미리 읽기를 하면 7.1 ms다(`c_ahead`, 위의 바닥 표). 미리 읽기를 끄면 `e9e0d22`의 BFS는 16.1 ms, 같은
프로세스의 C는 9.8 ms다(검사가 함께 돌던 때라 둘 다 조금 길다). **기계어의 체급은 C의 1.6배 느리다.**
- **그래서 BFS 하나로 C를 넘었다고 하지 않는다**(2026-10-05, 사용자의 지적). BFS는 예였다. 기준을 여러 종류의 일로 바꾸고(실수와
정수의 루프, 정렬, 해시 조인, 텍스트, 그리드, BFS, TPC-C와 질의), 바이트코드를 SSA로 올려 타입을 추론하고 검사를 루프 밖으로
끌어내고 레지스터를 할당하는 계층을 모든 블록에 두는 설계를 [023](023-optimizing-tier.md)으로 한다. 이 설계의 BFS 통과 조건으로
잴 계열은 023의 묶음에 들어간다.
- **간선 루프.** 정수의 코드에서, 편 리스트의 조각을 코드로 연 걷기 안에서는 그 리스트의 열이 늘 있다(편 리스트는 FLAT이다). 그래서
step이 연 같은 걷기는 실행기에 넘긴다(`pure_run_rest`). 키 비트가 없는 리스트는 비트가 닿는 키의 수(LIMIT)를 0으로 둬서, 키와
견주기 하나가 "비트가 있나"도 겸한다. `has`의 드문 길(1, 8바이트 칸, 비트 밖의 키)은 줄 밖에 둔다. 본 간선 하나에 명령 14개가
11개가 됐다.
- **고친 것.** 정수 산술의 결과 레지스터가 피연산자의 것과 같을 수 있는데, 범위 검사가 포기하면 실행기는 덮인 피연산자로 그 명령을
다시 했다. 2의 거듭제곱 곱을 시프트로 바꾸며 그 검사가 자주 포기하게 되자 aup의 검사(`PURE_JIT=all`, routes.aup의 깊이 우선
탐색)가 잡았다. 포기할 수 있는 산술은 결과를 x16에 만들고 검사 뒤에 옮긴다. `module_assumptions`에 그 꼴(`LOCALS_SOURCE`)을
더했다: 고치기 전 빌드에서 틀리고 고친 빌드에서 맞는다.
- **장부에서 더 고친 것**(2026-10-06, [128](../research/128-batch-executor-tables-and-costs.md)). 묶음 실행기의 무작위 시험이
덧붙이기를 섞자 둘이 나왔다. HASHED에 덧붙이는 C 호출이 레지스터에 있는 DENSE 장부의 증가를 모른 채 메모리를 봐서 `MEMORY`
결함이 한 회차 늦었다(`794801c`: 처음 덧붙일 때 장부의 여유를 본다). 그리고 레지스터가 모자라 장부를 두지 못한 리스트의 낡은
개수(x30)를 장부를 써 돌릴 때 리스트에 썼다(`dcfbc53`: 장부를 두는 리스트만 써 돌린다).
## 단계
1. 저장된 리스트를 배열로 펴기와 칸의 색인.
2. 좁은 열.
3. 최적화하는 JIT.
4. 미리 읽기.
단계마다 검사로 고정하고 재서 커밋한다. 2는 3과 함께 잰다.
## 착수 기준
- **최소 확인**
- `test-module`:
- 편 리스트가 무작위 연산의 열에서 트리만의 리스트와 매 걸음 같은 답을 낸다(펴기와 트리로 돌리기, 사본, 저널, 인코딩을 지나며).
- 좁은 열의 배열이 넓은 열의 것과 같은 답을 낸다(넓히기의 모든 경계, −0, 정수의 끝).
- JIT이 있는 빌드에서 Pure의 `make check`(ASan 포함)와 aup의 검사(무작위로 만든 프로그램, 참조 모델과의 대조), Vega의 검사가
`PURE_JIT=1`과 `PURE_JIT=0`에서 모두 초록이다.
- 기기 사이: 같은 `pure-run` 46번이 Pi(JIT), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다.
- **통과 조건**(RAM의 Pi 5)
- 코어만 잰 BFS: `bfs-run`이 같은 그래프로 같은 프로세스에서 C의 BFS(`bfs.c`의 루프, 21번의 중앙값)를 함께 돌리고, Pure의 중앙값이
그보다 작다. 같은 계열에서 탐색마다 거리, 닿은 노드 수, 실행량을 `PURE_JIT=0`의 것과 견주어 모두 같다.
- HTTP로 잰 BFS(033의 `bfs.py`): Pure의 중앙값이 C(`bfs.c`, 커밋된 그대로)의 중앙값보다 작다. 산수로 반반이다(위).
- 지금의 앱: TPC-C와 은행 질의를 여섯 쌍 번갈아 잰 중앙값이 `b1b3c7b`보다 1% 넘게 느리지 않고, 021 전(`a553601`)보다 3% 넘게 느리지
않다(쌓인 값의 한계). 은행 질의의 명령 수가 `b1b3c7b`보다 1% 넘게 늘지 않는다.
- **밝히는 것**: 단계마다의 BFS 시간과 명령 수. 첫 탐색이 펴기에 쓰는 값. 편 `edges`와 트리의 메모리. JIT의 BFS 코드와 바닥의
명령 수.
## 하지 않는 것
- 알고리즘을 바꾸기(방향을 바꾸는 BFS 같은), 같은 이벤트의 결과를 기억해 두기, 탐색을 여러 코어로 나누기. 같은 프로그램을 같은
차례로 한 코어에서 실행한다.
- `bfs.c`를 고치기. 견주는 C는 커밋된 그대로다(`c_ahead`는 맥락이다).
- macOS의 JIT, x86-64의 JIT.
|
