From 2945d2c0d6661d3602a2950825179331cb0ce4e0 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 13:35:30 +0100 Subject: Design 023, before building it: a tier that lifts every block to SSA, knows types and ranges, hoists the meaning's checks out of loops, counts work per loop, allocates registers; criteria on research 124's suite of seven kinds of work against C (each within 1.25x, the geometric mean below 1.0, the meaning's checks within 5%), from floors at 0.90x C --- docs/design/023-optimizing-tier.md | 178 +++++++++++++++++++++++++++++++++++++ 1 file changed, 178 insertions(+) create mode 100644 docs/design/023-optimizing-tier.md (limited to 'docs') diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md new file mode 100644 index 0000000..e119e97 --- /dev/null +++ b/docs/design/023-optimizing-tier.md @@ -0,0 +1,178 @@ +# 023 — 최적화 계층: 여러 종류의 일에서 깡연산으로 C를 넘기 + +작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전에 커밋한다). + +[022](022-arrays-and-registers.md)의 BFS는 C(`bfs.c`)보다 빨라졌지만, 그것은 C가 하지 않는 미리 읽기 덕이었다. 미리 읽기를 끄면 +16 ms 대 9.9 ms로 1.6배 느리고, C에 같은 미리 읽기를 하면 다시 C가 앞선다. BFS 하나를 맞춰 넘는 것은 목표가 아니다. 목표는 같은 +aup 코드, 같은 뜻, 같은 기계에서 **여러 종류의 일을 C만큼, 모아 보면 C보다 빠르게** 계산하는 것이다. 그러려면 지금처럼 루프 묶음의 +명령을 하나씩 기계어로 옮기는 것이 아니라, 블록 전체를 SSA로 올려 타입과 범위를 알고, 뜻을 지키는 검사를 루프 밖으로 끌어내고, +레지스터를 할당하는 계층이 모든 블록에 있어야 한다. + +## 산수: 재어 본 것 + +모두 Pi 5(Cortex-A76 2.4 GHz), RAM, 조용한 기기. 원시 결과와 코드는 [040](../../research/experiments/040-against-c/)에 있다. + +**묶음.** 일곱 가지 일을 각각 이벤트 하나로 한다. 입력은 프로그램이 MINSTD(`x * 48271 mod 2^31 − 1`, 씨앗 1)로 만들고, C도 같은 +수열로 같은 입력을 만든다. C는 그 일을 하는 사람이 쓸 코드다: 같은 알고리즘, 자연스러운 타입(정수는 정수), `qsort`, 선형 탐사 해시표, +`snprintf`(`natural.h`). `suite-run`이 한 프로세스에서 Pure의 이벤트와 C를 번갈아 돌리고 답이 같은지 매번 본다. + +| 일 | 무엇 | 크기 | +|---|---|---| +| roots | 1..n의 제곱근을 뉴턴 걸음으로, 그 합 (실수, 나눗셈) | n 10만 (걸음 약 200만) | +| knapsack | 배낭 DP: 항목마다 용량을 거꾸로 (정수, 표 읽고 쓰기) | 항목 100, 용량 5만 | +| sort | 수를 키로 둔 리스트에 넣고 차례로 읽기 | 20만 | +| join | 희소한 id로 둔 고객과 주문 100만을 id로 이어 지역별 합 | 고객 10만 | +| words | "w{n}" 단어를 텍스트 키 리스트로 세기 | 단어 30만, 어휘 5만 | +| matmul | n×n 행렬 곱 (키 `행 * n + 열`의 리스트) | 200 (곱셈-덧셈 800만) | +| bfs | 033의 BFS (노드 10만, 간선 100만) | | + +**지금**(`5fffb63`, `2026-10-05-suite.jsonl`, 11번의 중앙값): + +| 일 | Pure | C | Pure / C | 실행기만 | +|---|---:|---:|---:|---:| +| roots | 22.9 ms | 6.86 ms | 3.3 | 19.3 | +| knapsack | 1,880 ms | 6.27 ms | 300 | 298 | +| sort | 128 ms | 27.0 ms | 4.8 | 4.7 | +| join | 672 ms | 30.8 ms | 22 | 24 | +| words | 455 ms | 38.3 ms | 12 | 12 | +| matmul | 2,284 ms | 7.52 ms | 304 | 303 | +| bfs (미리 읽기 없이) | 15.7 ms | 10.0 ms | 1.57 | 9.4 | + +roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거나(루프가 코드로 다 되지 않는 블록) 실행기다. knapsack의 시간 55%는 +키로 둔 표를 찾는 `pure_list_seek`다. + +**바닥과 뜻의 값**(`floor.c`, `2026-10-05-floor.jsonl`). 일마다 Pure가 할 수 있는 가장 좋은 코드를 손으로 C로 썼다. 표현은 Pure의 +것이다: 이벤트의 리스트는 배열(FLAT은 차례로, DENSE는 키 자리에, 키 비트와 함께), 열은 값만큼 좁게, 희소한 키로 둔 리스트는 해시 +색인(칸 하나에 키와 위치, 키도 좁게)이고 걸을 때 차례로 정렬한다(런타임의 정렬은 비교가 인라인). 뜻도 Pure의 것이다. 그 뜻이 드는 +값을 셋으로 쟀다: + +- **bare**: 검사 없음(표현만의 값). +- **hoisted**: 컴파일러가 남길 검사만. 범위로 증명되는 것은 없애고(2^53 안의 정수는 유한하고 −0이 되지 않는다), 루프가 할 일을 + 열 때 알 수 있는 것(작업량 예산 대비 회차, 메모리 몫 대비 덧붙이기, 꽉 찬 DENSE 리스트의 비트, 열의 폭)은 루프마다 한 번. +- **naive**: 수는 수(binary64, 범위 모름)로 두고 뜻이 놓는 자리마다 검사(결과마다 유한, 0으로 나누기, 키마다 정수·−0 아님·2^53 안· + 비트 안, 위치마다 개수 안, 칸마다 폭 안, 회차마다 작업량, 덧붙이기마다 메모리 몫). + +| 일 | bare / C | hoisted / C | naive / C | +|---|---:|---:|---:| +| roots | 0.99 | 1.02 | 1.77 | +| knapsack | 0.95 | 0.97 | 10.8 | +| sort | 0.61 | 0.64 | 0.83 | +| join | 0.95 | 0.91 | 1.57 | +| words | 0.92 | 0.90 | 0.91 | +| matmul | 0.96 | 0.95 | 12.1 | +| bfs | 1.09 | 0.96 | 1.23 | +| 기하 평균 | 0.91 | 0.90 | 2.6 | + +- **뜻의 값은 빠른 길에서 0에 가깝게 만들 수 있다.** 검사를 그 자리마다 두면 1.2–12배이고, 범위와 끌어올리기로 남기면 0–3%다 + (roots의 2%는 바깥 루프의 작업량). 그러니 뜻은 C를 넘지 못하는 이유가 아니다. 넘지 못하게 하는 것은 지금의 실행 계층이다. +- **sort의 0.64는 알고리즘 몫이다.** `qsort`는 비교마다 함수를 부르고, 런타임의 정렬은 수를 그 자리에서 견준다. 그렇게 적는다. +- join은 처음 쓴 바닥(키 8바이트, 색인과 위치가 따로)에서 1.8이었다. 칸에 키와 위치를 함께 두고 키를 4바이트로 좁혀 0.91이 됐다: + 표현이 몫을 정한다. + +**그래서:** 바닥의 기하 평균이 0.90이다. 계층이 내는 코드가 바닥의 1.11배 안이면 모아 보아 C를 넘는다. 일마다로는 바닥의 1.22배 안이면 +C의 1.25배 안이다(roots 1.02 × 1.22). **빠듯하다.** JIT의 코드는 C 컴파일러의 것보다 길기 쉽다. 그래도 미달이면 미달로 적는다. + +## 원칙 + +- **뜻은 그대로.** 수는 binary64이고 −0은 −0이다. 유한하지 않은 결과, 0으로 나누기, 없는 키, 넘친 예산은 이벤트를 실패시키고, 결함의 + 종류와 자리가 실행기와 같다. 바뀌는 것은 표현과 실행의 길뿐이다. +- **결함은 빠른 길이 났는지만 안다.** 이벤트는 실패하면 통째로 되돌려지고, 같은 상태와 입력에서 결정적이다(`now`도 이벤트마다 정해진 + 값이다). 그래서 빠른 길의 검사는 "어딘가에서 결함이 난다"만 정확하면 된다: 나면 이벤트를 되돌리고 실행기가 처음부터 다시 돌아 + 같은 결함을 같은 자리에서 낸다. 끌어올린 검사가 너무 일찍 실패하면(실행기라면 거기까지 가지 않았을 때) 이벤트를 실행기로 다시 + 돌리면 되니 결과가 같다. 값은 실패할 때만 든다. +- **모든 블록.** 핸들러, 본문 있는 보기, 함수의 블록 모두를 계층이 맡는다. 코드로 하지 않는 명령(드문 텍스트 편집 같은)은 지금처럼 + step을 부른다. 값 모형으로 블록을 거르지 않는다. +- **벤치마크의 모양을 넣지 않는다.** 묶음의 상수(`48271`, `1048576`)나 프로그램의 모양을 아는 코드는 없다. 미리 읽기 같은 기법은 + 남기되, 기준은 그것을 끄고 재고(`PURE_AHEAD=0`), 켤 때는 C에도 같은 기법을 해서 견준다. +- **실행기가 기준이다.** 계층의 답(상태, 보기, 결함, 실행량)은 실행기의 것과 바이트까지 같다. + +## 모양 + +### 1. SSA로 올리기 + +- 블록(명령의 범위)을 기본 블록으로 나눈다: 분기(`JZ`, `JMP`), 루프(`EACH`, `LOOP`의 머리와 회차와 끝), `BREAK`. +- 스택과 지역 변수를 값으로 바꾼다: 기본 블록마다 스택의 높이는 검증기가 이미 정했으니, 추상 해석으로 스택 칸과 지역의 슬롯을 + SSA 값에 대응시키고 합류점(루프 머리 포함)에 φ를 둔다. +- 상태, 리스트, 텍스트는 메모리다. 명령마다 무엇을 읽고 쓰는지(리스트별)를 이미 안다(`changes`). 이것으로 루프 불변을 가린다. +- step을 부르는 명령은 메모리 전체를 쓰는 것으로 본다(부르기 전에 장부와 걷기의 자리를 쓰고, 부른 뒤 다시 읽는다. 022의 규칙 그대로). + +### 2. 타입과 범위 + +값마다 사실을 안다: 종류(bool, i64, 텍스트, 위치(어느 리스트의), 수)와, 수라면 **정수인지, 범위 [lo, hi], −0일 수 있는지, 유한한지**. + +- 출처: 상수, 좁은 열(폭이 범위를 준다: 1바이트 [0, 255], 4바이트 [0, 2^32)), 메시지의 `u32`, 개수, 루프의 셈(`for i in a .. b`는 + [a, b)), 위치. +- 전이: 산술은 구간 산술로(정수끼리의 `+ − *`는 정수, 범위가 2^53 안이면 정확하고 유한), `floor`, `min`, `max`, 비교가 가지를 좁힌다 + (`if c >= w`의 참 쪽에서 `c − w >= 0`). +- 루프 머리의 φ는 넓히기(widening)로 수렴시킨다. 셈은 머리에서 [a, b)로 바로 안다. +- 정수이고 범위가 2^53 안인 값은 정수 레지스터에 둔다. 0인 곱이 −0이 될 수 있는 경우(음수가 될 수 있는 쪽과의 곱, 음의 0의 부호 + 바꾸기)는 범위가 0 이상이면 없다. 아니면 그 자리에 검사를 둔다. +- 정수인 `x − floor(x / d) * d`(x, d가 정수, 2^53 안, d > 0)는 정수의 나머지다(정확하다: 몫의 반올림이 정수 경계를 넘지 않는다). + +### 3. 검사와 그 자리 + +뜻의 검사 하나하나를 IR의 연산으로 둔다: 유한, 0으로 나누기, −0, 키(정수·2^53 안·비트 안·닿는 범위 안), 위치(개수 안), 칸의 폭, +작업량, 메모리 몫, 리스트의 표현(FLAT, DENSE, 편 리스트). + +- 범위가 증명하면 없앤다. +- 루프 불변이면 루프 앞(preheader)으로 끌어낸다: 리스트의 표현, 열의 주소와 폭, 키 비트의 주소. +- 귀납 변수로 묶이면 루프 앞에서 한 번: 위치 `i`가 [a, b)이고 b ≤ 개수면 경계 검사 하나. DENSE 리스트가 **꽉 찼으면**(개수가 닿는 + 키의 수와 같으면) 그 리스트의 키 비트 검사는 키가 [0, 닿는 범위) 안인지로 바뀌고, 그것도 귀납 변수로 묶이면 루프 앞에서 한 번. +- 루프 안의 덧붙이기나 고치기가 리스트를 바꿀 수 있으면, 그 리스트에 대한 사실은 그 명령 뒤에서 다시 확인한다(022의 규칙). +- 끌어낸 검사가 실패하면 그 루프를 검사가 제자리에 있는 코드(지금의 JIT, 또는 실행기)로 돈다. 결함은 위의 원칙대로 실행기가 낸다. + +### 4. 작업량과 메모리 몫을 루프마다 + +- 루프가 열릴 때 회차의 수(셈은 `b − a`, 걷기는 조각의 길이)와 회차의 값(블록의 명령 수)을 안다. `남은 예산 ≥ 회차 × 값`이면 + 루프 안에서는 세지 않고, 끝날 때 실제 회차 × 값을 더한다(`BREAK`로 일찍 나가도 정확하다). 아니면 회차마다 센다(지금의 코드). +- 회차 안의 안쪽 루프는 그 안쪽 루프가 열릴 때 같은 일을 한다. +- 덧붙이기는 회차마다 많아야 하나라면 루프 앞에서 `회차 × 행의 바이트`를 메모리 몫과 견준다. + +### 5. 레지스터 할당과 코드 + +- SSA의 선형 스캔 할당(정수, 실수 둘). 루프 깊이로 값의 무게를 정한다. 넘치면 프레임의 슬롯. +- 022의 기계어 조각(태그 붙은 열 주소, 장부, 줄 밖 길, `pure_run_rest`)은 계층의 하위 단계로 쓴다. +- 컴파일은 블록이 처음 돌 때 한다(지금처럼). 그 값은 재서 밝힌다. + +### 6. 표현 (바닥이 가정한 것) + +- **희소한 키로 둔 이벤트의 리스트**(해시 색인): 항목은 넣은 차례로 열에 두고, 칸 하나에 키와 위치를 함께 둔 열린 주소 색인으로 + 찾는다. 키가 정수이고 4바이트에 들면 키도 4바이트. 차례가 필요할 때(걷기, `first`, 조각) 정렬한다(런타임의 정렬: 비교가 인라인). + 정렬은 바뀌기 전까지 유효하다. 텍스트 키는 해시하고 견준다. +- 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트). +- 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열). + +## 단계 + +1. **IR**: 블록을 SSA로 올리고 타입과 범위를 낸다. 기계어는 그대로 두고, IR을 해석하는 시험용 실행기로 모든 검사의 프로그램을 + 실행기와 견준다(IR이 뜻을 옮겼는지). +2. **코드**: IR에서 레지스터를 할당해 기계어를 낸다. 모든 블록. 검사는 아직 제자리에. +3. **검사 끌어올리기, 루프마다의 작업량과 메모리 몫, 다시 돌리기**(결함이 나면 실행기로). +4. **표현**: 희소한 키의 해시 색인과 걸을 때의 정렬, 텍스트의 정수 자릿수. + +단계마다 검사로 고정하고, 묶음을 재서 커밋한다. + +## 착수 기준 + +- **최소 확인** + - Pure의 `make check`(ASan 포함), aup의 검사(무작위로 만든 프로그램 600개, 참조 모델과의 대조), Vega의 검사가 `PURE_JIT=1`, + `PURE_JIT=all`, `PURE_JIT=0`에서 모두 초록이다. + - 새 시험: 무작위 프로그램에 결함을 심어(작은 예산, 없는 키, −0, 0으로 나누기, 2^53을 넘는 정수, 넓혀지는 열) 계층과 실행기의 + 상태, 결함의 종류와 자리, 실행량이 같다. `module_assumptions`가 그대로 지난다. + - 기기 사이: 같은 `pure-run` 46번이 Pi(계층), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다. +- **통과 조건**(RAM의 Pi 5, `suite-run` 11번의 중앙값, `PURE_AHEAD=0`) + - 일마다 Pure의 중앙값이 같은 프로세스의 C의 **1.25배 안**이다. + - 일곱의 Pure / C의 **기하 평균이 1.0 아래**다. + - BFS를 미리 읽기와 함께 재면 같은 미리 읽기를 한 C(`bfs_ahead`)의 1.0배 아래다. + - **뜻의 값**: 일마다, 계층의 코드를 검사 없이 낸 것(`PURE_UNCHECKED=1`, 재기 위한 것이고 답이 같은지만 본다)보다 5% 넘게 느리지 + 않다. + - 지금의 앱: TPC-C와 은행 질의를 여섯 쌍 번갈아 잰 중앙값이 `5fffb63`보다 1% 넘게 느리지 않고, 은행 질의의 명령 수가 1% 넘게 늘지 + 않는다. 그 앱들의 블록 중 실행기로 도는 것이 없다(step으로 부르기로 정한 명령 말고는). +- **밝히는 것**: 단계마다의 묶음 표(Pure, C, 실행기, 검사 없는 계층), 블록마다의 컴파일 시간과 코드의 크기, 첫 이벤트가 컴파일에 + 쓰는 시간, 해시 색인과 정렬이 드는 메모리. + +## 하지 않는 것 + +- aup 프로그램의 알고리즘을 바꾸기, 묶음의 크기나 상수에 맞추기. C를 고치기(견주는 C는 `natural.h` 그대로). +- SIMD로 벡터화하기. C도 `-O2`에서 이 루프들을 벡터화하지 않는다(gcc 14.2의 `-fopt-info-vec`: 답을 쓰는 두 칸만 묶는다). +- macOS와 x86-64의 계층(실행기가 같은 답을 낸다). -- cgit v1.2.3