diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/021-past-c.md | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/docs/design/021-past-c.md b/docs/design/021-past-c.md new file mode 100644 index 0000000..ec0df36 --- /dev/null +++ b/docs/design/021-past-c.md @@ -0,0 +1,112 @@ +# 021 — C보다 빠르게 + +작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전). +[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에 머물면 그렇게 적는다. + +## 원칙 + +- **뜻은 그대로.** 키 있는 리스트는 키 순서의 리스트이고 인덱스는 위치다. 바뀌는 것은 표현과 실행의 길이다. 어느 길로 가든 + 결과(값, 결함, 실행량, 메모리의 몫)는 바이트까지 같다. +- **벤치마크의 모양을 넣지 않는다.** 표현과 디렉터리와 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에서 먼저 잰다. |