diff options
Diffstat (limited to 'docs/research')
| -rw-r--r-- | docs/research/128-batch-executor-tables-and-costs.md | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/docs/research/128-batch-executor-tables-and-costs.md b/docs/research/128-batch-executor-tables-and-costs.md new file mode 100644 index 0000000..4c3e7b2 --- /dev/null +++ b/docs/research/128-batch-executor-tables-and-costs.md @@ -0,0 +1,147 @@ +# 128 — 묶음 실행기 4·5단계, 칸에 더하기, 걷기: 표를 만드는 루프가 묶이고, 남은 값이 보인다 + +2026-10-06. [024](../design/024-batch-executor.md)의 4단계 앞 절반(덧붙이기), 5단계(점화식), 3단계의 일부(칸에 더하기), 그리고 +`EACH`의 묶음. 코드는 `ca4978c`, `44f9ced`, `f290225`, `92c060a`이고, 그 사이에 JIT의 장부에서 버그 둘을 고쳤다(`794801c`, +`dcfbc53`). [126](126-batch-executor-stage-one.md), [127](127-batch-executor-stage-two.md)과 같은 방법으로 쟀다 +(`041-batches/runs.sh`, 빌드 `b4` = `92c060a`, 11번의 중앙값). 묶음이 무엇에 값을 내는지는 따로 지은 작은 모듈로 갈라 쟀다 +(`041-batches/costs/`). + +## 쉬운 말로 + +- **표를 만드는 루프가 묶인다.** matmul, knapsack, join은 처음에 MINSTD 점화식으로 수를 뽑아 리스트에 더한다. 지금까지 이 루프는 + 실행기에서 돌았다. 이제 점화식은 묶음 앞에서 회차마다 돌고(실행기와 같은 계산), 나머지 몸체는 묶음으로 돌고, 덧붙이기는 묶음의 + 끝에서 회차 차례대로 한다. join의 `totals[region].amount = totals[region].amount + …`(칸에 더하기)도 묶인다. 묶음으로 join이 + 실행기만의 423.4 ms에서 161.2 ms가 됐다. 계층(기계어)은 74.4 ms다. +- **아직 기계어를 걷어낼 수 없다.** 024의 기준은 roots, knapsack, matmul, join, BFS 각각 계층보다 느리지 않은 것이다. roots만 + 맞는다. 나머지가 어디에 시간을 쓰는지 쟀다. 가장 큰 것 셋은 이렇다. 덧붙이기 하나에 약 100 ns(실행기와 같다, 기계어는 5.6 ns), + join의 점화식 한 회차에 약 60 ns, matmul의 안쪽 회차에서 명령을 해석하는 값. BFS는 지금의 묶음 규칙으로는 묶이지 않는다(아래, + 열린 문제). +- **명령을 해석하는 값은 레인이 많으면 작다.** 묶음마다 명령 하나에 약 20 ns다. 레인 1024개로 나누면 회차당 0.02 ns다. 그래서 + 몸체를 미리 풀어 두는 것(pre-decode)보다 레인마다 드는 값(덧붙이기, 찾기, 모으기의 끝)을 줄이는 것이 먼저다. 레인이 적은 곳 + (matmul의 안쪽 루프 200, BFS의 간선 약 10)에서만 해석 값이 보인다. + +## 묶음 + +| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만¹ | +|---|---:|---:|---:|---:|---:| +| roots | 9.57 ms | **9.22** | 130.2 | 6.86 | 1.75억 / 27.56억 | +| knapsack | 7.93 | 15.07 | 1,039.0 | 6.23 | 4.72억 / 216.88억 | +| matmul | 14.23 | 46.07 | 911.8 | 7.51 | 11.18억 / 214.37억 | +| join | 74.4 | 161.2 | 423.4 | 31.5 | 28.77억 / 76.70억 | +| sort | 35.8 | 74.3 | 77.1 | 26.9 | 14.09억 / 15.03억 | +| BFS | 7.95 | 96.9 | 92.7 | 10.0 | 46.71억 / 47.12억 | +| words | 214.2 | 214.9 | 209.1 | 38.4 | 39.82억 / 39.34억 | + +¹ `suite-run` 세 바퀴의 사용자 모드 명령(`icount.c`, 126과 같이 C와 읽기도 포함). + +- BFS와 words는 묶음으로 바뀐 것이 거의 없다. 둘 다 이제 묶음 걷기가 하나씩 있어(BFS는 그래프를 읽는 핸들러의 + `for r in load.rows`, words는 끝의 걷기) 모듈 전체가 실행기의 사본(`run_batches`)을 돈다. 사본에서 묶음 아닌 코드는 명령이 + 약 2% 많다(126). words는 프로세스의 명령이 1.2% 많다. BFS는 읽기의 걷기가 묶여 프로세스의 명령이 0.9% 적지만, 재는 탐색은 + 사본으로 돈다. 탐색의 시간 차(96.9 대 92.7, 4.5%)는 그 2%보다 크고 `b3`에서는 반대(92.5 대 95.8)였으니, 나머지는 놓인 + 자리로 본다. +- knapsack은 `b3`(`f290225`)에서 14.71 ms였다. 명령은 같고(4.71억 대 4.72억) 사이클이 1.7% 많다. 놓인 자리다. + +`b2`(127)에서 `b4`로 묶음의 명령: roots 1.73억 → 1.75억, knapsack 4.65억 → 4.72억, matmul 12.06억 → 11.18억, join 76.69억 → 28.77억, +sort 15.02억 → 14.09억. 묶음 루프가 없는 모듈의 실행기는 그대로다(126의 두 벌). + +## 만든 것 + +- **덧붙이기(4단계의 앞 절반).** 묶음의 몸체가 수와 bool의 항목을 리스트에 더하거나 덧붙일 때, 그 리스트를 몸체가 달리 읽지 않고 + (색인도 걷기도 없이) 중첩 루프가 없으면 묶는다. 항목은 묶음의 끝에서 회차 차례대로 실행기의 걸음(`pure_run_step`)으로 만든다. + 그래서 이미 있는 키, 메모리 몫, 되돌리기 기록이 실행기의 것 그대로다. +- **점화식(5단계).** 회차가 쓰기 전에 읽는 지역 변수로, 쓰는 곳마다 `x = (x의 식)`이고, 그 식이 수, 필드, 상태, 루프의 값, 몸체가 + 쓰지 않는 지역 변수로만 되고, 분기 안에 있지 않은 것. 로드 때 그 쓰기를 `PLAN_RECUR`로 표시한다. 묶음마다 식을 걸음(스택의 수, + x, 루프의 값, 연산)으로 한 번 풀고, 묶음 앞에서 회차마다 실행기와 같은 계산으로 돈다. 다른 곳에서 x를 읽는 값은 레인마다 기록해 + 두고, 묶음의 패스는 그 쓰기를 건너뛴다. 어떤 회차의 걸음이 결함을 내면(수가 아니게 되거나 0으로 나누기) 묶음이 회차들을 돌려준다. +- **칸에 더하기(3단계의 일부).** `L[k].f = L[k].f + e`에서 k를 두 번 같게 계산하고, k와 e가 L을 읽지 않으면, 패스는 두 번째 k와 + 그 찾기, 칸 읽기를 건너뛰고 행과 e를 남긴다. 묶음의 끝에서 회차 차례대로 실행기처럼 더하고 쓴다. 더한 값이 수가 아니면 그 회차에서 + 실행기의 결함이고, 열이 좁으면 넓힌다. 묶음이 그 칸을 달리 읽거나 쓰면 회차들을 돌려준다. +- **걷기.** `EACH`의 몸체가 묶음 꼴이면, 항목 1024개씩을 한 묶음으로 돈다. 레인은 항목의 자리이고(걷는 리스트의 `ROW`는 아핀), + 작업량은 열 때 센다. 묶음이 끝나면 걷기의 자리를 묶음 뒤로 옮긴다. 걷는 리스트에 덧붙이는 몸체는 묶지 않는다. +- **세 번째 출구.** 묶음의 끝에서 회차 차례대로 하는 일(덧붙이기, 칸에 더하기)은 어떤 회차에서 결함이 날 수 있다. 그때는 묶음이 + 회차들을 돌려주지 않고, 그 회차의 실행기 결함으로 끝낸다. 이벤트가 되돌려지므로 남는 것은 결함의 종류와 명령, 그때까지의 작업량 + 뿐이고, 묶음은 그 셋을 실행기와 같게 낸다. + +## JIT에서 고친 것 + +무작위 시험이 덧붙이기를 섞자, 묶음이 아니라 022의 장부에서 기계어가 실행기와 다른 곳이 둘 나왔다. + +- **HASHED에 덧붙일 때의 메모리 몫**(`794801c`). 장부가 DENSE 리스트의 증가를 레지스터에 두는 묶음에서, HASHED 리스트에 + 덧붙이는 C 호출은 앱의 증가에 장부의 몫이 아직 없는 채로 메모리를 봤다. 그래서 `MEMORY` 결함이 한 회차 늦게 났다(DENSE, FLAT, + HASHED에 덧붙이는 루프, `memory 6000`에서 작업량 3562 대 3525). 이제 처음 덧붙일 때 장부의 여유를 본다. `pure-run`에 `memory N` + 명령을 더했다. +- **장부를 두지 않는 리스트의 개수**(`dcfbc53`). 레지스터가 모자라 장부를 두지 못한 리스트도 살아 있는 개수(x30, 열세 번째 + 레지스터)를 쥐고 있다가, 덧붙이기가 장부 없는 길로 간 뒤 그 낡은 개수를 리스트에 썼다(`t.has`를 읽는 두 겹 루프 뒤에 덧붙이는 + 루프, `PURE_JIT=all`에서 개수 36이 1). 이제 장부를 두는 리스트만 써 돌린다. + +## 무엇에 값을 내는가 + +같은 빌드에서 `costs/time.c`(모듈 하나에 `go`를 일곱 번, 중앙값)로, 세 길 각각을 세 번 돌렸다 +(`2026-10-06-costs.jsonl`). 그리고 묶음으로 돌 때 표본을 떠서(`PURE_JIT=0`, 2 kHz) 함수와 줄로 나눴다. + +| 모듈 | 하는 일 | 기계어 | 묶음 | 실행기만 | +|---|---|---:|---:|---:| +| `ops` | 1,024,000 회차, 아핀 `let` 여섯과 `max` 모으기 | 4.27 ms | 9.81 | 156.3 | +| `nest` | 200 × 200 × 200, 안쪽 루프를 레인 200개가 함께 | 23.08 | **10.20** | 653.1 | +| `adds` | DENSE에 키 5만 개를 차례로 | 0.28 | 5.18 | 5.17 | +| `probes` | HASHED에 10만 개, 100만 번 찾기 | 56.3 | 85.1 | 256.1 | + +- **명령의 해석: 묶음마다 명령 하나에 약 20 ns.** `ops`의 `let`을 하나, 여섯, 열둘로 바꿔 쟀다(묶음 1000개): 9.40, 9.80, + 10.30 ms. 모으기를 `total = total + 1`로 바꾸면 4.51, 4.92, 5.42 ms. 어느 쪽이든 명령 44개가 0.90 ms, 묶음마다 명령 하나에 + 약 20 ns다. 레인 1024개면 회차당 0.02 ns다. +- **모으기의 끝: 회차당 4–9 ns.** 그러면 `ops`의 나머지는 모으기다. 합이면 회차당 약 4.4 ns, `max`면 약 9.2 ns다(기계어는 몸체 + 전체가 4.2 ns). 표본으로 보면 합의 63%가 끝에서 회차 차례대로 합치는 루프(레인을 하나씩, 회차의 차례를 계산하고, 검사하며), + 20%가 묶음을 열 때 모으기의 레인을 비우는 루프다(벡터가 되지 않았다: 쓰기가 `b->n`과 겹칠 수 있어 회차마다 다시 읽는다). + `max`는 레인마다의 비교가 더 든다. 그런데 `min`과 `max`의 합치기는 차례가 답을 바꾸지 않는다(−0과 +0 사이도 같다). + 정수의 합도 2^53 안이면 그렇다. 차례대로 해야 하는 것은 분수의 합뿐이다. roots에서 이 끝이 묶음 시간의 약 8%다. +- **함께 도는 중첩 루프는 기계어보다 빠르다.** `nest`의 안쪽 회차(800만)가 레인당 약 1.3 ns, 기계어는 2.9 ns다. +- **덧붙이기: 하나에 약 100 ns, 실행기와 같다.** 기계어는 5.6 ns다. 표본의 40%가 실행기의 걸음(`pure_run_step`), 약 45%가 + 리스트의 더하기와 그 검사(`pure_list_add`, `arrays_fit`, `member_add`, `pure_list_contains`, `dense_holds`)다. 항목마다 실행기의 + 걸음 하나, 메모리 몫과 되돌리기 기록 하나, 칸마다의 검사를 따로 한다. +- **HASHED 찾기.** `probes`에서 표본의 41%가 해시 칸의 탐사(`hashed_slot`, `pure_list_lookup`)이고, 대부분 칸을 견주는 줄이다 + (표의 칸 2^18개가 L2보다 크다: 캐시 미스). 38%가 키의 산수(나누기와 `floor`), 10%가 덧붙이기다. 기계어도 같은 미스를 낸다. + +같은 표본을 묶음의 일에 떴다(`b4`, Pure의 몫 가운데 비율, 대략): + +- **join (161 ms)**: 점화식의 걸음 약 41%(110만 회차, 회차당 약 60 ns: 걸음 열둘을 하나씩 디스패치하고, 스택이 메모리에 있고, + 사슬 안에 나누기가 있다), HASHED 찾기 약 16%, 레인의 산수와 칸 모으기 약 18%, 칸에 더하기 약 9%, 덧붙이기 약 9%. +- **matmul (46 ms)**: 중첩 몸체 약 67%(안쪽 회차마다 명령 15개를 레인 200개에: 해석 값만 셈하면 15 × 20 ns ÷ 200, 레인당 약 1.5 ns), + 표를 만드는 루프 약 30%(덧붙이기 약 20%, 점화식 약 10%). +- **knapsack (15 ms)**: 덧붙이기 약 28%(약 4 ms), 나머지가 안쪽 루프. +- **roots**: 모으기의 끝 약 8%. + +## BFS: 열린 문제 + +BFS는 묶음 96.9 ms, 실행기만 92.7 ms(같은 일, 위), 기계어 7.95 ms, C 10.0 ms다. 묶이지 않는다. 033의 `graph.aup`에서, + +- 바깥 루프는 `if i >= queue.count { break }`와 `queue.first + i`로 큐를 읽으면서 같은 큐에 덧붙인다. 4단계의 규칙(덧붙이는 + 리스트를 몸체가 달리 읽지 않는다)에 걸린다. +- 안쪽 걷기(노드의 간선)는 회차가 약 10개라 묶음의 최소(16)에 못 미치고, `seen.has`로 읽는 리스트에 `seen.add`로 더한다. + +024가 적어 둔 길은 둘이다. **바뀌는 개수**: 묶음을 열 때의 `queue.count`까지만 묶는다(BFS의 한 층, 프런티어). **커지기만 하는 +걸러내기**: 묶음 전체에 `has`를 먼저 묻고, 거짓인 레인만 회차 차례대로 다시 물어 더하고 덧붙인다. 여기에 바깥 레인마다 다른 +간선 걷기를 레인으로 펼치는 것(중첩 `EACH`)이 더해져야 한다. 지금의 중첩은 `LOOP` 한 겹뿐이다. 셋 다 만들어야 BFS가 묶음이 된다. +그리고 그때 레인당 값이 기계어(간선 하나에 명령 약 11개, 022)보다 낮을지는 재 봐야 안다. **JIT를 걷어낼지는 이것에 달려 있다.** + +## 뜻과 맞음 + +- 생성기의 `lanes` 꼴에 덧붙이기(`e`, `d`, 회차가 떨어진 핸들러, 메모리 몫 아래), 칸에 더하기, 점화식(`x1`, 덧붙이기와 쓰기와 + 칸에 더하기 앞), 걷기(`f`, `g`, `h`, `g`의 조각)를 더했다. 시드 1, 2, 3, 5, 23의 프로그램 665개가 다섯 길(묶음, 실행기만, 기계어의 두 + 모드, 계층 없는 기계어)에서 같았다. 시드 1에서 걷기의 묶음이 1,891개, 칸에 더하기를 품은 묶음이 278개 돌았다. 명령 목록에 `memory 6000` + 구간을 더해, 메모리 몫이 덧붙이기의 한가운데에서 다하는 경우도 견준다. +- 고정 소스: `BATCH_SOURCE`가 세 칸에 차례로 더하기와 조각의 걷기를 담고, `RECUR_SOURCE`가 회차마다 두 번 바뀌는 점화식, 어떤 + 회차의 0 나누기와 수를 넘는 곱을 작업량과 메모리 몫 아래에서 담는다. +- 단위 시험이 세 JIT 모드와 ASan(실행기 모드)에서 통과했다. sanitized `pure-run`(ASan, UBSan)으로 무작위 프로그램과 고정 소스 + 137개를 돌려도 오류가 없었고, 출력은 실행기만으로 돈 것과 같았다. + +## 다음 + +재 본 것으로 차례를 정한다. 기계어와의 차이(기계어를 걷어내는 기준)로 보면 join 87 ms, BFS 89 ms, matmul 32 ms, knapsack 7 ms다. + +1. **한꺼번에 덧붙이기.** 묶음의 끝에서 항목을 실행기의 걸음으로 하나씩 만들지 않고, `module-list.c`의 한 호출로 레인의 칸을 + 열에 쓴다. 메모리 몫과 되돌리기 기록은 묶음에 한 번, 키의 차례(DENSE)와 중복은 레인의 검사로. join, matmul, knapsack에 함께 + 걸린다(대략 15, 9, 4 ms). +2. **점화식의 걸음을 레지스터 꼴로.** 피연산자(상수, x)를 연산에 붙이고, 스택을 레지스터에 두고, 걸음마다의 디스패치를 줄인다. + join의 약 65 ms가 여기에 있다. 상수로 나누기의 준비된 역수는 실행기의 `floor(a / m)`와 비트까지 같다는 것을 먼저 보여야 한다. +3. **모으기의 끝.** `min`, `max`, 2^53 안의 정수 합은 차례 없이(벡터로) 합치고, 레인을 비우는 루프를 벡터로. +4. **BFS의 세 가지**(위). 그 뒤에 matmul의 합친 연산(곱해 더하기). |