diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/024-batch-executor.md | 2 | ||||
| -rw-r--r-- | docs/research/131-batch-executor-general-cuts.md | 95 |
2 files changed, 96 insertions, 1 deletions
diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md index ec9a6c8..2ed21f5 100644 --- a/docs/design/024-batch-executor.md +++ b/docs/design/024-batch-executor.md @@ -1,6 +1,6 @@ # 024 — 묶음 실행기: 기계어 없이 루프를 C 가까이 -작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 1단계를 만들었다([126](../research/126-batch-executor-stage-one.md): knapsack이 실행기에서 1,041 ms → 13.6 ms, 안쪽 루프는 계층의 1.17배로 기준 미달). 2단계(중첩 루프를 함께, 모으기)를 만들었다([127](../research/127-batch-executor-stage-two.md): roots 9.13 ms로 계층 9.57보다 빠름, matmul 50 ms). 4단계의 앞 절반(덧붙이기), 5단계(점화식), 칸에 더하기, 걷기를 만들었다([128](../research/128-batch-executor-tables-and-costs.md): join이 실행기의 423에서 161 ms, 계층 74). 남은 값은 덧붙이기 하나 약 100 ns, join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). 그 셋을 줄였다([129](../research/129-batch-executor-costs-cut.md): 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기; knapsack 10.8, matmul 36.4, join 118 ms, roots 8.87로 계층 9.57보다 빠름). BFS를 셈하니 차례대로 할 꼬리가 간선의 약 10%라, 꼬리를 묶음의 C로 하고 간선을 레인으로 펼치면 계층과 겨룰 만하다(약 6–7 ms 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다. +작성일: 2026-10-05. 상태: 제안과 시제품([041](../../research/experiments/041-batches/)). 1단계를 만들었다([126](../research/126-batch-executor-stage-one.md): knapsack이 실행기에서 1,041 ms → 13.6 ms, 안쪽 루프는 계층의 1.17배로 기준 미달). 2단계(중첩 루프를 함께, 모으기)를 만들었다([127](../research/127-batch-executor-stage-two.md): roots 9.13 ms로 계층 9.57보다 빠름, matmul 50 ms). 4단계의 앞 절반(덧붙이기), 5단계(점화식), 칸에 더하기, 걷기를 만들었다([128](../research/128-batch-executor-tables-and-costs.md): join이 실행기의 423에서 161 ms, 계층 74). 남은 값은 덧붙이기 하나 약 100 ns, join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). 그 셋을 줄였다([129](../research/129-batch-executor-costs-cut.md): 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기; knapsack 10.8, matmul 36.4, join 118 ms, roots 8.87로 계층 9.57보다 빠름). BFS를 셈하니 차례대로 할 꼬리가 간선의 약 10%라, 꼬리를 묶음의 C로 하고 간선을 레인으로 펼치면 계층과 겨룰 만하다(약 6–7 ms 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다. 사용자는 범용의 길을 택했다(2026-10-08). 같은 코드의 값 다시 쓰기, `if !c`의 분기 하나, 고르기(적은 레인의 갈래를 그 레인만), 비트로 묻기, 아핀 `first + i`로 BFS가 간선당 112개, 24.0 ms가 됐다([131](../research/131-batch-executor-general-cuts.md)); 범용의 바닥은 계층의 약 2배로 보인다. [023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을 C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만 diff --git a/docs/research/131-batch-executor-general-cuts.md b/docs/research/131-batch-executor-general-cuts.md new file mode 100644 index 0000000..0827a9d --- /dev/null +++ b/docs/research/131-batch-executor-general-cuts.md @@ -0,0 +1,95 @@ +# 131 — 범용 장치로 값 줄이기: 같은 코드의 값 다시 쓰기, 고르기, 비트로 묻기 + +2026-10-08. [130](130-batch-executor-frontiers.md)이 BFS로 보인 간선당 명령 211개(기계어 38.5)를, 어떤 코드에도 듣는 장치로만 +줄였다. 사용자의 방향은 범용이다. 스위트의 꼴만 골라 합친 연산의 표를 만들지 않는다. 코드는 `589e669`와 `735ba81`이다. 같은 방법으로 쟀다 +(`041-batches/runs.sh`, 빌드 `b9` = `735ba81`, 11번의 중앙값; 탐색만의 명령은 `041-batches/search/`, `2026-10-08-search-counts.jsonl`). + +## 쉬운 말로 + +- **BFS가 간선당 211개에서 112개가 됐다.** 41.0 ms에서 24.0 ms다(기계어 7.7, C 9.9). 기계어의 3.1배다(5.4배였다). +- **바꾼 것은 다섯 가지 범용 장치다.** 같은 코드로 다시 계산하는 값을 한 번만 계산하기, `if !c`를 분기 하나로, 레인이 적은 갈래를 + 그 레인만 모아 돌기(고르기), 키가 비트로 있는 리스트에 비트로 묻기, `L.first + i`를 아핀 값으로. 어느 것도 BFS만을 위한 것이 + 아니다. 다만 knapsack과 matmul은 약 10% 느려졌다(아래: 패스의 코드가 커진 값으로 보이며, 원인을 다 가르지는 못했다). +- **이 꼴의 바닥은 기계어의 약 2배로 보인다.** 간선마다 레인을 한 번씩 훑는 일(모으기, 묻기, 분기, 고르기, 덩어리 만들기)이 약 40개, + 노드마다 약 20개, 후보마다 약 250개(간선당 26개)다. 레인 훑기는 연산마다 메모리를 오가고, 기계어는 레지스터에서 한다. 더 줄이려면 + 훑기를 합쳐야 하는데, 그것은 범용이 아니라 꼴의 표다. + +## 묶음 + +| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만 | +|---|---:|---:|---:|---:|---:| +| roots | 9.57 ms | **8.97** | 130.5 | 6.86 | 1.69억 / 27.56억 | +| knapsack | 7.93 | 11.45 (b7 10.32) | 1,040.7 | 6.25 | 3.94억 / 216.88억 | +| matmul | 14.24 | 39.98 (36.51) | 914.9 | 7.58 | 9.68억 / 214.37억 | +| join | 84.6 | 116.9 (117.8) | 435.1 | 31.7 | 18.93억 / 76.70억 | +| sort | 35.2 | 56.4 (56.8) | 77.0 | 26.9 | 10.08억 / 15.03억 | +| BFS | 7.71 | **24.0** (41.0) | 92.7 | 9.90 | 33.74억 / 47.12억 | +| words | 215.5 | 217.6 (214.3) | 209.9 | 39.5 | 39.77억 / 39.34억 | + +- 실행기만의 명령은 모두 그대로다. 기계어의 join이 78.8에서 84.6 ms로 오간 것은 같은 코드라 놓인 자리다. +- **knapsack과 matmul이 느려졌다.** 명령이 3–4%, 사이클이 7–8% 많다. 같은 코드의 값 다시 쓰기의 검사를 끄면 2%가 돌아오고(그래서 + 그런 값이 없는 모듈은 검사를 건너뛰게 했다), 고르기를 꺼도 나머지는 그대로다. 패스 함수가 커져 인라인과 배치가 바뀐 값으로 보인다. + 남겨 둔다. + +## 만든 것 + +- **같은 코드의 값 다시 쓰기**(`plan_reuse`, 로드 때). 묶음 블록 안에서 값 하나를 만드는 코드 조각(스택 높이로 자른 부분 나무)이 + 앞선 조각과 같고(`same_code`), 둘이 같은 가장 안쪽 블록의 한 줄에 있고(사이에 `JMP`·루프·`break`·착지 없음; `JZ`는 레인을 + 좁히기만 한다), 사이에서 조각이 읽는 지역 변수를 쓰거나 리스트를 바꾸지 않으면, 뒤의 조각은 앞의 값을 그대로 쓴다. 앞의 값은 + 묶음이 쥔다(버퍼를 놓지 않는다). 모듈은 조각의 시작마다 `reuse_from`, `reuse_length`를 둔다. BFS의 `e.to`를 세 번 모으던 것이 + 한 번이 됐다. +- **`if !c`는 분기 하나.** `NOT` 바로 뒤가 `JZ`면 `NOT`을 돌지 않고 뒤집어 가른다. 레인 세기도 같은 루프에서 한다. +- **고르기**(`select`, `deselect`). 가른 뒤 가는 레인이 4분의 1 이하이고 갈래가 곧은 코드(안에 분기·루프·`break` 없음, 끝의 `JMP`는 + else)면, 그 레인들만 모아(`sel[j]`) 갈래를 돈다. 갈래 안에서 바깥 값을 읽으면 `sel`로 모은다(펼친 걷기 안에서는 항목의 바깥 + 레인을 거쳐 한 번에). 모으기는 바깥 레인의 몫에 더한다. 갈래가 쓴 지역 변수는 갈래가 끝날 때 바깥 레인으로 돌려놓는다(바깥의 + 값은 그대로, 가른 레인만 새 값; 일부 레인에만 썼으면 그 마스크로). 미룬 쓰기와 칸에 더하기는 기록할 때 바깥 레인으로 펼친다. + 덧붙이기는 모은 레인의 칸을 `sel`과 함께 두어 끝의 처리가 그 레인만 돈다. 걸러내기의 몸체가 고르기면, 모은 회차의 기록도 후보만 + 돈다. `PURE_SELECT=all`은 레인 수와 상관없이 모든 곧은 갈래를 고르게 해서(시험용), 무작위 시험이 이 길을 다 지나게 한다. +- **비트로 묻기.** 키를 비트로 두는 리스트(`pure_list_bits`)의 `has`는 레인 루프 하나다. 걸러내기의 결정도 그 비트와 우리 비트 + (모은 회차가 더하는 키를 표시, 끝에 지움)로 한다. 해시 집합이 없어졌다. 비트가 없는 키(정수가 아니거나 범위 밖)는 없는 키다 + (`pure_list_contains`와 같다). 처음에 이것을 "있는 키"로 잘못 두어 무작위 시험 하나가 작업량에서 어긋났고, 고쳤다. +- **`L.first + i`는 아핀.** 균일 값과 아핀 값을 더한 자리가 리스트 안이면 아핀 값이다(전에는 레인마다 계산해 수 레인이 됐다). 그 + 뒤의 읽기가 보폭 읽기가 되고 범위 검사가 양 끝만 본다. +- **조각의 양 끝을 한 번에**(`pure_list_slice`). 걷기의 조각 경계 둘을 한 호출로 찾는다. 묶인 리스트의 정수 키면 버킷으로 바로 간다. +- **모은 회차의 기록.** 키와 칸을 수 레인으로 한 번 만들고 그대로 복사한다(레인마다 값의 꼴을 묻지 않는다). + +## 무엇에 값을 내는가 (BFS, 간선당 명령) + +| 단계 | 간선당 명령 | ms | +|---|---:|---:| +| 130 (`b7`) | 211 | 41.0 | +| 같은 코드의 값 다시 쓰기, `if !c` | 205 | 39.0 | +| 고르기 | 146 | 30.2 | +| 비트로 묻기, 아핀 `first + i`, 바깥 값 한 번에 | 121 | 24.8 | +| 모은 회차의 기록, 조각 양 끝 | **112** | **24.0** | +| 기계어 | 38.5 | 7.7 | + +프런티어 합(간선의 `to`만 더하기)은 70 → 56개다(기계어 35). 사이클로는 BFS 81 → 57(기계어 19), 프런티어 26 → 20(15)이다. + +남은 112개를 표본으로 나누면 대략 이렇다. +- 간선마다 레인을 훑는 일 약 45개: `to` 모으기 12, 비트로 묻기 11, 뒤집어 가르기와 고르기 7, 덩어리 만들기 7, 나머지 디스패치. +- 노드마다 약 20개(간선당): 조각 경계, 레인마다의 수와 작업량. +- 후보(간선의 10.5%)마다 약 250개(간선당 26개): 기록 50, 결정 90, 넣기 110(`pure_list_add_many`의 폭 검사와 칸 쓰기, 몫 셈). +- 묶음마다의 고정 값은 작다. + +**바닥.** 간선마다의 훑기는 연산마다 레인 배열을 메모리로 오가며 요소당 4–12개가 든다. 기계어는 같은 일을 레지스터에서 요소당 +1–2개로 한다. 훑기를 줄이지 않고는 간선당 약 45개 아래로 가지 못하고, 노드와 후보의 몫을 반으로 줄여도 70개쯤이다. 기계어의 +1.8배다. 훑기를 합치는 것은 꼴의 표라서 범용의 길에서는 여기가 바닥이다. 후보의 넣기(110개)는 리스트 쪽 C라 더 줄일 수 있다. + +## 뜻과 맞음 + +- 시드 1, 2, 3, 5, 23의 무작위 프로그램이 다섯 길에서 같았다. `PURE_SELECT=all`로 모든 곧은 갈래를 고르게 해도(시드 1, 2, 3, 5, 23) + 같았다. 처음 돌렸을 때 시드 23의 프로그램 하나가 작업량에서 어긋났다(위의 비트 없는 키). 고치고 다시 돌려 같았다. +- 고정 소스 여섯(`BATCH`, `NESTED`, `RECUR`, `APPEND`, `FRONT`, `GRAPH`)이 세 길에서 같았다(기본과 `PURE_SELECT=all`). +- 단위 시험 세 모드, ASan(실행기 모드), aup의 검사 두 모드, Pure의 `make check`가 통과했다. sanitized `pure-run`으로 시드 23의 + 프로그램과 고정 소스를 기본과 `PURE_SELECT=all`로 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다. +- 실행기만의 명령은 그대로다(`run`은 건드리지 않았다). + +## 다음 + +- 후보의 넣기를 리스트 쪽에서 줄이기(폭 검사를 한 번에, 비트와 칸을 함께). +- 고르기를 중첩 루프의 회차에도(roots의 빠진 레인). +- `total = total + A + B` 꼴의 모으기 인식(129). +- knapsack과 matmul의 10%: 패스를 나누거나 묶음 구조체의 뜨거운 자리를 모아 되찾기. +- 기계어를 걷어낼지는 사용자의 몫이다. 범용의 길로는 BFS가 기계어의 약 2배에서 멈춘다. 다른 일은 roots가 기계어보다 빠르고, + knapsack 1.4배, matmul 2.8배, join 1.4배, sort 1.6배다. |