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
|
# 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배
앞선다"는 예측은 틀렸다.
- C를 넘으려면 둘 다 있어야 한다: 저장된 키 있는 리스트의 조각을 L2에 드는 색인으로 찾는 형태(잎 하나에 칸 하나, 칸에서 잎으로
바로: C의 `start[v]` → `to[k]`와 같은 사슬)와, 검사를 루프 밖으로 빼고 값을 레지스터에 두는 JIT. 앞의 것은 저장 형태의 일이라
설계 022로 따로 적고 기준을 둔다.
## 원칙
- **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트이고 인덱스는 위치다. 바뀌는 것은 표현과 실행의 길이다. 어느 길로 가든
결과(값, 결함, 실행량, 메모리의 몫)는 바이트까지 같다.
- **벤치마크의 모양을 넣지 않는다.** 표현과 디렉터리와 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에서 먼저 잰다.
|
