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
|
# 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%였다.
|
