From 58b8d5b291422a0c12db590eefbad6efe96cc6de Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 09:29:23 +0100 Subject: Design 022: stored lists as arrays with a bucket index fitted to the keys searched, narrow columns, a JIT with registers and loop guards, read ahead; criteria first --- docs/design/022-arrays-and-registers.md | 151 ++++++++++++++++++++++++++++++++ 1 file changed, 151 insertions(+) create mode 100644 docs/design/022-arrays-and-registers.md (limited to 'docs') diff --git a/docs/design/022-arrays-and-registers.md b/docs/design/022-arrays-and-registers.md new file mode 100644 index 0000000..12f0870 --- /dev/null +++ b/docs/design/022-arrays-and-registers.md @@ -0,0 +1,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. -- cgit v1.2.3