diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/research/125-tier-first-steps.md | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/docs/research/125-tier-first-steps.md b/docs/research/125-tier-first-steps.md new file mode 100644 index 0000000..ada82c9 --- /dev/null +++ b/docs/research/125-tier-first-steps.md @@ -0,0 +1,80 @@ +# 125 — 최적화 계층의 첫 걸음들: C의 3–300배에서 1.9배로 + +2026-10-05. [023](../design/023-optimizing-tier.md)의 계층(중첩 루프를 SSA로 올려 레지스터의 기계어로 도는 것)과 리스트의 표현을 +하루 동안 고치며 잰 것. 코드와 원시 결과는 [040-against-c](../../research/experiments/040-against-c/)에 있고, 묶음은 매번 +`suite-run` 11번의 중앙값(같은 프로세스의 C와 견줌, `PURE_AHEAD=0`)이다. + +## 쉬운 말로 + +- **일곱 가지 일의 기하 평균이 C의 1.92배다.** [124](124-against-c.md)에서는 3–300배였다(배낭과 행렬 곱이 300배, 조인 22배, 텍스트 + 12배). 일마다 1.25배 안이라는 023의 기준은 배낭(1.19배) 하나가 맞고, 기하 평균 1.1배는 아직 멀다. +- **가장 크게 줄인 것은 계층보다 표현이었다.** 차례를 어긴 수 키의 리스트를 해시 표의 칸에 두고(HASHED) 위치가 필요할 때만 정렬하자 + 조인은 531 ms에서 74, 정렬은 98에서 37이 됐다. 텍스트 키도 같은 표로 찾게 하자 텍스트 일이 453에서 209가 됐다. +- **계층에서 값이 컸던 것은 측정이 가리킨 것이었다.** 행렬 곱의 안쪽 루프를 어셈블리로 여러 꼴로 써서 재 보니(`forms.c`) 위치를 곱셈으로 + 구하는 것이 2배, 적재 앞의 분기가 1.34배였고 2^53 오버플로 검사는 거의 공짜였다. 칸의 포인터를 루프의 φ로 두자 23.0 ms가 14.2가 됐다. + 짐작으로 명령을 줄인 시도(되돌림 패드, 줄 밖 비트맵, 상수 나눗셈의 곱셈화)는 0–1%거나 오히려 느려서 되돌렸다. +- **지금의 앱은 그대로다.** TPC-C와 은행 질의를 `5fffb63`과 여섯 쌍 번갈아 재니 TPC-C의 중앙값이 −1.2%(쌍마다 −5.2…+1.4%), 질의의 + 중앙값은 1% 안이고, 질의의 명령 수는 −0.1…+0.5%다. +- **새 검사가 버그 넷을 잡았다.** 무작위 프로그램에 작업량 예산과 작업량 비교를 더하자 022부터 있던 것(바깥 루프의 작업량이 모자랄 때 + LOOP 명령에서 빈 스택으로 포기하던 것)과 계층의 첫 날부터 있던 것(if가 만나는 곳의 φ가 루프 밖으로 끌려 나가던 것)이 나왔다. 둘 다 + 고정 시험(`MERGES_SOURCE`, `BUDGET_SOURCE`)으로 남겼다. +- **남은 것.** 텍스트 일(5.6배)은 실행기가 돈다. 루프가 텍스트를 만들고(`"w{n}"`을 한 바퀴에 세 번, aup의 `let`은 텍스트를 담지 못한다) + 텍스트 연산은 기계어가 없다. BFS(1.6배)는 계층이 키 구간의 걷기와 덧붙이기를 아직 못 한다. 조인(2.5배)은 메모리 미스가 쥐고 있다. + +## 묶음 + +| 일 | `5fffb63` (124) | `11f6d9c` 계층 처음 | `e01dae9` | C | +|---|---:|---:|---:|---:| +| roots (실수 루프) | 3.3배 | 14.0 ms | 9.59 ms (1.40배) | 6.87 | +| knapsack (정수 DP) | 300배 | 38.8 | 7.54 (1.19배) | 6.32 | +| sort (정렬) | 4.8배 | — | 36.7 (1.37배) | 26.8 | +| join (해시 조인) | 22배 | — | 78.4 (2.54배) | 30.8 | +| words (텍스트 셈) | 12배 | — | 209 (5.58배) | 37.5 | +| matmul (행렬 곱) | 304배 | 48.6 | 14.2 (1.85배) | 7.70 | +| BFS (미리 읽기 없이) | 1.57배 | — | 16.0 (1.61배) | 9.90 | +| 기하 평균 | — | — | **1.92배** | | + +미리 읽기를 둘 다 하면 BFS는 1.04배다. 실행기만으로는(`PURE_JIT=0`) roots 131 ms, 배낭 1,058, 행렬 곱 916이다. + +## 바꾼 것, 차례로 + +| 커밋 | 바꾼 것 | 일 | +|---|---|---| +| `cfefd45` | 루프를 열 때 아핀 키의 양 끝을 한 번 검사(BCE), 상수를 명령에, 한 바이트 열을 네 바이트로 | 배낭 38.8→16.5, 행렬 48.6→25.7 | +| `abe0412` | 안쪽 셈 루프의 작업량을 열 때 한꺼번에(나가면 돌려줌), 비교와 분기를 합침, 꽉 찬 리스트는 비트 없이 | 배낭 16.5→8.5 | +| `a3ed5b6` | 래치에서 나갈 때 회차를 next−1로(뒤로 가는 이동 없음), 2의 거듭제곱으로 나누기를 역수 곱으로, 2^53 검사 3명령 | roots 14.1→12.2, 배낭 8.5→7.8 | +| `8d68451` | HASHED: 차례를 어긴 수 키를 해시 표의 칸에, 위치가 필요할 때 기수 정렬; 계층이 키로만 찾을 때 줄 밖 탐사 | 조인 531→108, 정렬 98→58 | +| `082a3dc` | 텍스트 키도 HASHED(FNV-1a, 칸의 키와 바이트 비교), 찾은 자리에 쓰기(PLAN_ROW) | 텍스트 453→217 | +| `b56341e` | 표를 4/5까지(100,000 키가 1 MB: L3 안), 일반 코드의 APPEND가 칸에 바로, 양수로 나눈 정수는 −0이 아님 | 조인 108→84, 정렬 58→37 | +| `e4b4694` | 한 줄로 이어 읽히는 수 산수는 마지막만 유한 검사, 스냅숏의 상수는 상수로, 장부 루프에서도 HASHED에 바로 | roots 12.2→10.9, 조인 84→74 | +| `6466b9e` | 포인터 귀납 변수: 아핀 키의 칸 주소를 루프 머리의 φ로 | 행렬 23.0→14.2 | +| `e01dae9` | 유한 검사를 정수로(지수 비트) | roots 10.9→9.6 | + +## 어셈블리로 잰 꼴 + +`forms.c`(행렬 곱의 안쪽 루프, 11번의 중앙값): 계층의 꼴 20.7 ms, 검사와 비트 없이 20.1, 포인터와 곱하기-더하기 13.1, 포인터와 +곱·합 따로 10.0, 거기에 두 검사 10.2, 적재 앞에 비트 13.4, 정적 배열의 C 3.8(바깥 루프를 벡터로 묶는다). + +`newton.c`(roots의 루프): 계층의 꼴(next를 따로 두고 뒤로 가며 옮김) 7.7 ms, gcc의 꼴(next를 r의 레지스터에) 7.0, 수로 하는 유한 검사를 +더하면 9.7, 정수로 하면 8.7. 같은 생각으로 0으로 나누기 검사를 정수로 하면 오히려 느렸다. + +측정이 짐작을 두 번 뒤집었다. 명령 18개를 16개로 줄인 것(`mov` 하나와 줄 밖 비트맵)은 0%였고, 상수 나눗셈을 곱셈으로 바꾼 것은 +조인을 2–4% 느리게 했다(메모리에 묶인 루프에서 수의 나눗셈은 정수 파이프 밖에서 공짜에 가깝다). + +## 뜻과 맞음 + +- 무작위 계층 시험(`module_tier`)이 이제 작업량을 비교하고 작은 예산 넷을 돈다. 리스트는 DENSE(꽉 참/빈틈), HASHED(키로만), 키를 회차와 + 함께 움직이는 훑기를 섞는다. 지금의 생성기로 시드 6개(프로그램 약 800개)가 같은 답을 낸다. +- 고정 시험: `MERGES_SOURCE`(if가 만나는 곳의 φ), `BUDGET_SOURCE`(작업량이 모자란 바깥 루프), `CHAIN_SOURCE`(넘치는 수의 줄). +- 리스트: `arrays_equivalence`가 HASHED를, `text_keys_equivalence`가 텍스트 키의 HASHED와 위치를 묻는 덧붙이기를 트리와 견준다. +- 저장된 리스트(트리)의 길에서 HASHED 확인을 빼, 은행 질의의 명령 증가를 0.3–0.8%에서 0.5% 안으로 줄였다. + +## 다음 + +- **텍스트**: 텍스트를 지역 값으로 담기(aup의 `let`과 Pure의 지역 칸)와 텍스트 연산의 기계어. 이 일의 남은 시간 대부분이 같은 텍스트를 + 세 번 만드는 데와 실행기의 디스패치에 있다(디스패치 약 20%, 해시와 탐사 약 11%, 수의 서식과 텍스트 만들기 약 13%). +- **BFS**: 계층이 키 구간의 걷기(sliced EACH)와 이벤트 리스트의 덧붙이기를 하게. +- **루프 묶음 일반**: 레지스터가 모자라면 계층이 묶음을 포기한다(행렬 곱이 그랬다). 루프 밖에서만 쓰이는 진입 값을 다시 읽거나 프레임에 + 두는 스필이 필요하다. 꽉 차지 않은 DENSE를 키로 훑는 루프는 지금 일반 코드로 돈다(루프를 열 때 읽을 키만 확인하는 것이 다음). +- **뜻의 값**: 검사 없는 계층(`PURE_UNCHECKED`)으로 일마다 검사의 몫을 재는 손잡이는 아직 없다. roots에서 임시로 잰 유한 검사의 + 몫은 지연 전 27%였다. |