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
|
# 021 — C보다 빠르게
작성일: 2026-10-05. 상태: 1–4단계를 구현해 쟀다. 아래 "바로잡음"이 처음의 산수를 고친다.
[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 코드, 같은 뜻(키 있는 리스트, 인덱스는 위치, 결정적인 결과), 같은 기계에서.
## 산수: 무엇이 가능하고 무엇이 아닌가
C의 9 ms는 Pi 5(Cortex-A76, 2.4 GHz)에서 약 2,160만 사이클이다.
- **실행기로는 안 된다.** 이 탐색은 바이트코드로 약 810만 명령이다: 간선마다 5개(`ROW, ITEM_GET, LIST_HAS, NOT, JZ`),
꺼낸 노드마다 19개, 새 노드마다 12개. 리스트 연산이 0 ns라 해도 C를 넘으려면 명령 하나에 2.7 사이클 이하여야 한다. 지금
실행기는 약 14 사이클이다(디스패치, 메모리의 스택, 함수 부르기). 기계어로 옮기는 것(JIT)이 전제다.
- **저장된 리스트를 키로 찾는 것은 O(1)이어야 한다.** 노드마다 간선 조각의 두 경계를 100만 항목의 `edges`에서 찾는다(20만 번).
2 ms 안에 하려면 한 번에 10 ns, 의존하는 메모리 읽기 둘 이하다. B+트리의 내려가기(네 단, 단마다 미스)나 잎의 첫 키들을 반씩
나눠 찾기(열다섯 번 읽기)는 이것만으로 15–20 ms다.
- **이벤트의 리스트는 O(1)이어야 한다.** `seen`은 키로 넣기 10만, `has` 100만, 키로 찾아 읽기 10만이고, `queue`는 덧붙이기
10만과 위치로 읽기 10만이다. B+트리로는 넣기마다 몇 단을 고친다. `has`는 이미 비트다(020).
- **간선 하나의 바닥**: `to`를 읽고(8바이트 수, 차례로), 정수로 바꾸고, `seen`의 비트(노드 10만이면 12.5 KB, L1에 든다)를
본다. 3–4 ns. C는 간선마다 400 KB의 `depth[to]`를 읽어 약 9 ns다. 이것이 Pure가 C를 넘을 수 있는 구조적인 몫이다(런타임이
키 집합을 비트로 고른다).
- **그래서 기대하는 것은 1.3–1.8배다**(5–7 ms), 10배가 아니다. 10 ms에 머물면 그렇게 적는다.
## 바로잡음 (2026-10-05, 1–4단계를 해 보고)
위의 산수는 명령의 수만 셌다. 잰 것은 다르다.
- **저장된 리스트의 디렉터리**(3)는 만들어 쟀고 넣지 않았다: 탐색 하나의 명령은 3.6% 줄었지만 사이클은 6% 늘었다. 칸의 표(760 KB)와
잎의 표(500 KB)가 L2(512 KB)에 들지 않아, B+트리 위쪽 단(캐시에 있다)을 내려가는 것보다 미스가 많았다. "필수"라는 판단은 틀렸다.
- **바닥은 메모리 지연이다.** `038-past-c/seekfloor.c`: 간선 100만 개의 리스트에서 노드마다 조각의 두 경계를 찾고 첫 간선을 읽는 데,
BFS처럼 무작위 차례로 노드 하나에 373 ns가 든다. 같은 일을 C의 오프셋 배열(`start[v]`, `to[start]`)은 21 ns에 한다. C의 반복끼리는
서로 기다리지 않아 미스가 겹치고, B+트리는 뿌리에서 잎까지 서로 기다리는 읽기를 넷 한다. 이것만으로 10만 노드에 18–37 ms다.
- 그래서 **저장된 키 있는 리스트가 B+트리뿐인 한, JIT만으로는 C(9 ms)를 넘지 못한다.** 바닥은 25–35 ms 근처로 본다. "1.3–1.8배
앞선다"는 예측은 틀렸다.
- **색인의 시제품**(`038-past-c/indexfloor.c`, 리스트 밖에서): 잎을 B+트리처럼 흩어 두고(항목 32개, 열 셋), 키의 범위를 2의
거듭제곱 폭의 칸으로 나눠 칸마다 첫 항목의 잎과 자리, 위치를 둔다. 칸의 원점을 폭의 배수에 맞추면(조각의 경계가 칸의 시작이
된다) 노드 하나에 124–134 ns, 맞추지 않으면 350–470 ns다. 같은 측정에서 C는 17–21 ns다. 둘 다 노드마다 DRAM 미스 하나인데,
C는 반복 하나가 명령 여덟 남짓이고 반복끼리 서로 기다리지 않아 미스 여럿을 겹친다. 색인은 B+트리보다 세 배 빠르지만, 노드마다
하는 일이 C만큼 짧지 않으면 C에 닿지 않는다.
- 그래서 C를 넘으려면 색인과 함께, 노드 하나와 간선 하나에 하는 일이 C와 같은 크기여야 한다(간선마다 명령 열 남짓, 노드마다 백
남짓, 서로 기다리는 읽기 둘). 지금 JIT은 간선마다 약 80, 노드마다 수백이다. 그만큼 줄이는 것(값을 레지스터에, 검사를 루프
밖으로, 표현이 바뀌지 않는다는 가정을 루프 머리에서 한 번 확인)은 최적화 컴파일러의 일이다.
## 원칙
- **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트이고 인덱스는 위치다. 바뀌는 것은 표현과 실행의 길이다. 어느 길로 가든
결과(값, 결함, 실행량, 메모리의 몫)는 바이트까지 같다.
- **벤치마크의 모양을 넣지 않는다.** 표현과 디렉터리와 JIT 모두 일반적이고, 무작위 프로그램 검사가 지나간다. 코드에 그래프나
`1048576`을 아는 곳은 없다.
- **모든 길이 끝까지 간다.** JIT에 "지원하지 않는 명령"은 없다: 빠른 길이 없는 명령은 그 명령 하나를 실행하는 C 함수를 부른다.
그래서 처음부터 모든 프로그램이 JIT으로 돌고, 실행기와 견줄 수 있다.
## 모양
### 1. 이벤트의 리스트의 세 표현
이벤트의 리스트(`let`, 메시지의 행, 보기의 본문의 리스트)는 나누지도, 저장하지도, 되돌리지도 않는다(018). 그래서 같은
`PureList`의 API 뒤에서 표현을 고를 수 있다.
- **납작(flat)**: 필드마다 배열 하나, 리스트의 차례대로. 덧붙이기 O(1), 위치로 읽기 O(1), 차례로 읽기(런)는 배열의 조각.
키 있는 리스트에 지금 마지막 키보다 큰 키가 오면 덧붙인다. 가운데 넣기와 지우기는 배열을 민다. 민 항목 수가 항목 수의 몇
배를 넘으면 B+트리로 바꾼다(그 뒤는 지금과 같다).
- **조밀(dense)**: 수로 키를 둔 리스트에서 키가 작은 0 이상 정수일 때(020의 비트와 같은 조건), 필드마다 키로 바로 찾는 배열과
있음의 비트. 키로 넣기, `has`, 키로 찾아 읽기, 개수가 O(1)이다. 키가 그 조건을 벗어나거나, 배열이 항목 수에 비해 너무 성기면
(키의 범위가 항목 수의 네 배와 4,096을 넘으면) 납작으로 바꾼다(키 순서로 한 번 훑는다).
- 조밀에서 위치가 필요한 연산(위치로 읽기와 쓰기, 지우기, 걷기, 키로 찾아 위치를 내기)이 오면 **한 번 납작으로 바꾼다**(O(n)).
위치를 세는 별도 구조(순위, 선택)는 두지 않는다. 한 이벤트에서 바뀜이 되풀이되면(두 번) 그 이벤트 동안 B+트리에 머문다.
- 배열의 바이트는 그 리스트가 쥔 것으로 센다(018의 몫, 020의 `extra`처럼). 이벤트가 끝나면 배열은 비우고 남긴다(다음 이벤트가
다시 쓴다; 큰 것은 놓는다).
- 다른 연산(나누기, 저장, 저널)은 이벤트의 리스트에 오지 않는다. 오면 B+트리로 바꾼 뒤 한다.
### 2. 키로 찾아 읽기를 하나로
`seen[k].depth`는 `LIST_FIND`(위치를 낸다) 다음 `ITEM_GET`이다. 로드할 때 둘 사이로 들어오는 분기가 없으면 둘을 하나로 묶는다
(`plan`의 표시). 그러면 위치가 만들어지지 않고, 조밀한 리스트에서 O(1)이다. 결함(없는 키)은 그대로다.
### 3. 저장된 키 있는 리스트의 디렉터리
수로 키를 둔 저장된 리스트를 한 판(version)에서 많이 찾으면(항목 수의 32분의 1번을 넘으면) 그 판의 디렉터리를 만든다.
- 키의 범위를 2의 거듭제곱 폭의 칸으로 나눈다(칸 하나에 항목이 평균 넷 남짓). 칸마다 그 칸의 시작 키 이상인 첫 항목의 위치와
그 잎(잎의 표에서의 번호, 잎 안의 자리)을 둔다. 잎의 표는 잎마다 포인터와 첫 위치다.
- 찾기: 칸을 계산하고(나눗셈 없이), 그 칸의 첫 항목에서 잎 안으로 앞으로 본다. 칸의 시작 키를 찾으면 읽기 둘이다.
- 판이 바뀌면 그 판의 것은 쓰지 않는다. 스냅숏의 사본은 같은 판이니 리스트의 디렉터리를 함께 쓴다(참조 수). 디렉터리의 바이트는
리스트의 저장된 바이트의 8분의 1을 넘지 않을 때만 만든다(파생된 것이라 상태의 몫에는 세지 않는다).
### 4. JIT (AArch64 리눅스)
- 핸들러와 보기의 블록을 로드할 때(또는 처음 돌 때) 기계어로 옮긴다. 다른 기계(x86, macOS)와 `PURE_JIT=0`에서는 실행기다.
- 처음에는 피연산자 스택을 지금처럼 메모리에 둔다(디스패치와 간접 분기를 없애는 것이 먼저다). 뜨거운 명령(산술, 비교, 분기,
지역 칸, 걷기의 행, 항목 읽기, `has`, 덧붙이기)은 안에 쓴 코드로, 나머지는 명령 하나를 실행하는 C 함수 부르기로.
- 걷기(`EACH`)는 리스트의 런을 레지스터에 쥐고 돈다(항목마다 위치로 찾지 않는다). 걷는 리스트가 바뀌면 그 자리에서 다시 쥔다.
- 실행기와 같아야 하는 것: `EACH`는 시작할 때 `길이 × 항목 수`를 실행량에 매기고 `LOOP`은 돌 때마다 매긴다. 유한하지 않은
수의 결함은 같은 명령에서 난다. 인덱스 지역 칸은 넣기와 지우기를 따라간다. 수의 연산은 따로 한다(곱셈과 덧셈을 하나로 묶는
FMA를 쓰지 않는다: C는 `-std=c17`이 막지만 내보낸 코드는 아무것도 막지 않는다).
- 쓰고 실행하는 페이지는 W^X(쓴 뒤 실행만 되게 바꾼다).
### 5. HTTP의 길
코어만 잰 BFS(187 ms)와 HTTP로 잰 것(191 ms)의 차이 4 ms를 먼저 잰다. 1단계가 지우지 못하면 따로 다룬다.
## 단계
1. 이벤트의 리스트의 세 표현과 키로 찾아 읽기 묶기.
2. 저장된 리스트의 디렉터리.
3. HTTP와 코어의 차이를 재고, 남으면 줄인다.
4. JIT.
앞의 셋은 JIT 없이 서야 한다. 단계마다 검사로 고정하고 재서 커밋한다.
## 착수 기준
- **최소 확인**
- `test-module`: 세 표현을 가진 이벤트의 리스트가 무작위 연산의 열에서 B+트리만의 리스트와 매 걸음 같은 답을 낸다(바뀜이 일어나는
모든 경계 포함). 디렉터리를 가진 리스트의 찾기가 디렉터리 없이 찾은 것과 같다(판이 바뀌기 전과 뒤, 사본 포함).
- JIT이 있는 빌드에서 Pure의 `make check`(ASan 포함)와 aup의 검사(무작위로 만든 프로그램, 참조 모델과의 대조)가 `PURE_JIT=1`과
`PURE_JIT=0`에서 모두 초록이고, 같은 프로그램의 출력이 둘에서 같다.
- 029/033의 기록: 같은 `pure-run` 46번이 Pi(JIT), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다.
- **통과 조건**(RAM의 Pi 5, 같은 그래프, 같은 실행에서 잰 C와 견준다)
- HTTP로 잰 BFS(033의 `bfs.py`): Pure의 중앙값이 C(`bfs.c`, 커밋된 그대로)의 중앙값보다 작다.
- 코어만 잰 BFS(`bfs-run`): 같은 그래프로 같은 프로세스에서 C의 BFS를 함께 돌려, Pure의 중앙값이 그보다 작다.
- 지금의 앱: TPC-C와 은행 질의를 전과 후 번갈아 여섯 쌍 재서 중앙값이 3% 넘게 느려지지 않고, 은행 질의의 명령 수가 네 번의
중앙값으로 1% 넘게 늘지 않는다(JIT이 은행 질의를 빠르게 하면 명령 수는 준다).
- **밝히는 것**: 단계마다의 BFS 시간. C의 `depth`를 비트로 바꾼 변형의 시간(기준이 아니라 맥락: Pure의 몫이 어디서 오는지).
첫 탐색이 디렉터리를 만드는 값.
## 하지 않는 것
- 알고리즘을 바꾸기(방향을 바꾸는 BFS 같은). 같은 프로그램을 같은 차례로 실행한다.
- 같은 이벤트의 결과를 기억해 두기. 매번 계산한다.
- macOS의 JIT(`MAP_JIT`), x86-64의 JIT. 리눅스 AArch64에서 먼저 잰다.
|
