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
|
# 022 — 배열과 레지스터로 C를 넘기
작성일: 2026-10-05. 상태: 설계와 착수 기준.
[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).
## 단계
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.
|
