diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/design/024-batch-executor.md | 2 | ||||
| -rw-r--r-- | docs/research/129-batch-executor-costs-cut.md | 124 |
2 files changed, 125 insertions, 1 deletions
diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md index bfbe1e9..91e60a5 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는 아직 묶이지 않는다(바뀌는 개수, 커지기만 하는 걸러내기, 중첩 걷기가 필요하다). +작성일: 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 예상). [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/129-batch-executor-costs-cut.md b/docs/research/129-batch-executor-costs-cut.md new file mode 100644 index 0000000..c807df1 --- /dev/null +++ b/docs/research/129-batch-executor-costs-cut.md @@ -0,0 +1,124 @@ +# 129 — 묶음 실행기의 값 줄이기: 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기, 그리고 BFS의 산수 + +2026-10-06. [128](128-batch-executor-tables-and-costs.md)이 잰 값 가운데 셋을 줄였다. 덧붙이기 하나 약 100 ns, 점화식 한 회차 약 +60 ns, 모으기의 끝 회차당 4–9 ns다. 코드는 `4791c42`(덧붙이기), `9f0498b`와 `e8558e7`(점화식), `f9e3d22`(모으기)다. 128과 같은 +방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b5` = `f9e3d22`, `b6` = `e8558e7`, 11번의 중앙값; 작은 모듈은 `costs/`). 그리고 BFS를 +묶는 설계가 기준을 넘을 수 있는지 먼저 셈했다(`041-batches/frontier.c`). + +## 쉬운 말로 + +- **기계어 없이 넷이 빨라졌다.** knapsack 15.1 → 10.8 ms, matmul 46.1 → 36.4, join 161 → 118, sort 74 → 55.5다. roots는 8.87 ms로 + 기계어(9.57)보다 빠르다. 기계어와의 차이는 knapsack 2.9 ms, matmul 22 ms, join 40 ms, BFS 89 ms로 줄었다. +- **바꾼 것은 셋이다.** 묶음의 덧붙이기를 항목마다 실행기의 걸음으로 하지 않고 리스트의 한 호출로 한다. 점화식의 걸음은 스택이 + 아니라 번호 붙은 값 사이의 연산이다. 모으기의 끝은 차례가 답을 바꾸지 않는 곳(`min`, `max`, 2^53 안의 정수 합)에서 차례 없이 + 벡터로 합친다. +- **BFS는 셈해 보니 가능성이 있다.** 프런티어를 묶음으로 돌면, 묶음을 열 때 `has`가 거짓이라 차례대로 다시 물어야 하는 간선이 100만 + 개 가운데 약 10만 5천 개다. 이 꼬리를 실행기가 아니라 묶음의 C로 하면 1 ms 안팎이다. 다만 레인마다 간선 수가 달라, 간선을 레인으로 + 펼쳐야 한다(함께 돌면 2.17배를 돈다). 아직 만들지 않았다. + +## 묶음 + +| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만¹ | +|---|---:|---:|---:|---:|---:| +| roots | 9.57 ms | **8.87** | 130.4 | 6.86 | 1.67억 / 27.56억 | +| knapsack | 7.93 | 10.84 | 1,042.9 | 6.24 | 3.76억 / 216.88억 | +| matmul | 14.20 | 36.41 | 912.0 | 7.55 | 9.24억 / 214.37억 | +| join | 78.7 | 118.3 | 422.2 | 30.9 | 19.07억 / 76.70억 | +| sort | 35.6 | 55.5 | 77.3 | 26.9 | 10.13억 / 15.03억 | +| BFS | 7.66 | 96.9 | 92.9 | 9.93 | 46.93억 / 47.16억² | +| words | 215.6 | 215.2 | 207.0 | 37.8 | 39.76억 / 39.34억² | + +¹ `suite-run` 세 바퀴의 사용자 모드 명령(C와 읽기 포함, 126과 같다). ² `b5`. + +- `b4`(128)에서 `b6`으로 묶음의 시간: knapsack 15.07 → 10.84, matmul 46.07 → 36.41, join 161.2 → 118.3, sort 74.3 → 55.5, roots + 9.22 → 8.87 ms. 명령은 knapsack 4.72억 → 3.76억, matmul 11.18억 → 9.24억, join 28.77억 → 19.07억, sort 14.09억 → 10.13억이다. +- 실행기만의 명령은 그대로다(roots 27.56억, knapsack 216.88억, `b4`부터 `b6`까지). 바꾼 것은 묶음과 리스트의 코드뿐이다. +- knapsack은 `b5`에서 10.17 ms였다. 명령이 같고(3.76억) 사이클이 3% 많아, 놓인 자리로 본다. 기계어의 join은 빌드가 같은 코드인데 + 72.3–78.7 ms로 오간다. + +## 바꾼 것 + +- **한꺼번에 덧붙이기**(`4791c42`). 묶음의 끝에서, 모든 덧붙이기가 이벤트의 리스트에 하나씩이고(색인 없이), 리스트가 그 꼴을 + 지키며 받을 수 있으면(`pure_list_takes`: 키 없는 FLAT은 끝에, DENSE는 지금의 개수로 담을 수 있는 키로, HASHED는 수 키로; 배열의 + 한계를 넘지 않게) 128개씩 한 번에 넣는다(`pure_list_add_many`). 메모리 몫은 넣기 전에 끝의 모습으로 셈한다. 항목 하나는 몫이 세는 + 것을 늘리기만 하므로, 끝이 몫 안이면 그 사이의 어느 회차도 넘지 않는다. 넘으면 지금처럼 회차대로 해서 그 회차에서 결함이 난다. + 열은 한 번 늘리고 한 번 넓힌다. 이미 있는 키를 만나면 그 회차의 `EXISTS`다. 리스트의 꼴을 바꾼 회차(키 있는 리스트의 첫 항목이 + DENSE나 HASHED를 만든다) 뒤에는 다시 한 번에 넣기를 시도한다. DENSE에 5만 개: 5.18 → 0.65 ms(기계어 0.28). +- **점화식을 레지스터 꼴로**(`9f0498b`, `e8558e7`). 걸음은 스택에 넣고 빼는 대신, 한 회차가 쥐는 수(걸음의 결과, 점화식의 값, 루프의 + 값, 그대로인 수)에 번호를 매기고 그 두 번호의 연산이다. 한 문장 안에서 두 번 계산하는 연산은 한 번만 한다(문장이 끝나기 전에는 + x가 그대로다). 한 회차는 묶음마다 한 번 깔아 둔 동작들을 도는 루프 하나이고, 갱신의 마지막 걸음이 x에 바로 쓴다. 그 사이에 x를 + 읽는 자리(기록)는 x가 바뀌지 않았으면 레인 배열 하나를 함께 쓴다(join의 네 자리가 한 번 저장). MINSTD 100만 회차: 44.4 → 21.8 + ms(기계어 18.5, 실행기만 73.0). x를 네 번 읽어 합하면 50.4 → 36.0 ms(기계어 19.9). +- **차례 없는 모으기**(`f9e3d22`). `min`과 `max`의 합치기는 차례가 답을 바꾸지 않는다(−0이 +0 아래). 정수의 합도 크기의 합이 2^53 + 아래면 그렇다. 그런 끝은 레인 순서로 넷씩 합친다. 레인마다의 `min`, `max` 걸음과 그 끝은 수를 그 차례의 정수로 바꿔 비교하는 + 루프라 벡터가 된다. 레인을 비우는 루프는 개수를 지역 변수로 두어 벡터가 됐다. 100만 회차의 `max`: 9.80 → 4.00 ms(기계어 + 4.27), 회차를 세는 합: 4.51 → 1.61 ms. + +## 무엇에 값을 내는가 + +`costs/time.c`, 세 길, 세 번의 중앙값(`2026-10-06-costs.jsonl`의 `b5`, 점화식은 `b6`; 괄호는 `b4`). + +| 모듈 | 기계어 | 묶음 | 실행기만 | +|---|---:|---:|---:| +| `ops` (`max` 모으기) | 4.27 ms | **4.00** (9.81) | 156.3 | +| `nest` | 23.1 | **10.17** (10.20) | 653.0 | +| `adds` | 0.28 | 0.65 (5.18) | 5.17 | +| `probes` | 56.1 | 73.0 (85.1) | 259.7 | +| `recur` | 18.45 | 21.8 | 73.0 | +| `recur4` | 19.9 | 36.0 | 181.4 | + +`b6`의 표본(묶음, Pure의 몫 가운데, 대략): + +- **join (118 ms)**: 점화식 약 35 ms(회차당 약 33 ns: 연산의 사슬에 나누기가 있고, 값이 메모리를 거쳐 다음 걸음으로 간다), 레인의 + 산수와 칸 읽기 약 32 ms, HASHED 찾기 약 24 ms, 칸에 더하기와 끝 정리 약 20 ms, 덧붙이기 약 6 ms. +- **matmul (36 ms)**: 중첩 몸체 약 32 ms(안쪽 회차마다 명령 15개를 레인 200개에), 표를 만드는 루프 약 4 ms. 기계어는 전체가 14 ms다. +- **knapsack (11 ms, `b5`)**: 안쪽 루프 약 7 ms, 미룬 쓰기의 정리 약 2 ms, 덧붙이기 1 ms 아래. +- **sort**: 묶음 밖이다. 실행기, 정렬(`make_ordered`), 라이브러리의 몫이 대부분이다. + +## BFS의 산수 + +`frontier.c`는 스위트의 그래프(노드 10만, 간선 100만)로 BFS를 프런티어 묶음처럼 돈다. 회차 `i`부터 묶음을 열 때 큐의 개수까지(최대 +B개), 각 간선의 `has`는 묶음을 열 때 묻는다. 거짓이라 한 간선이 후보이고, 후보는 회차 차례대로 다시 물어 더하거나(처음 보는 노드) +버린다(같은 묶음의 앞 회차가 더했다). + +| B | 간선 | 후보 | 더하기 | 묶음 | 함께 돌 때의 레인-회차 | +|---:|---:|---:|---:|---:|---:| +| 1024 | 999,913 | 105,232 | 99,997 | 101 | 217만 (간선의 2.17배) | +| 256 | 999,913 | 101,243 | 99,997 | 394 | 200만 (2.00배) | +| 64 | 999,913 | 100,296 | 99,997 | 1,565 | 181만 (1.81배) | + +- **꼬리는 작다.** 차례대로 해야 하는 후보가 간선의 약 10%다. 후보 하나에 DENSE 비트를 다시 묻고, 부모의 깊이를 읽고(부모는 묶음을 + 열 때 이미 있다), 비트와 깊이를 쓰고, 큐에 덧붙인다. 묶음의 C로 하면 하나에 약 10 ns, 1 ms 남짓이다. 실행기의 걸음으로 하면 + 10만 × 100 ns 이상이라 그것만으로 기계어 전체(7.7 ms)를 넘는다. 그래서 꼬리는 `at_once`처럼 묶음 쪽 C여야 한다. +- **간선은 펼친다.** 레인마다 간선 수가 다르다(평균 10). 중첩 루프처럼 함께 돌면 가장 긴 레인만큼 돌아 2.17배다. 묶음의 노드마다 + 간선 행의 범위를 구해 간선을 레인으로 이어 붙이면(024가 적은 "펼치기") 간선 하나에 레인 하나다. +- **예상.** 간선 하나에 레인의 일 몇 가지(행의 `to` 읽기, 비트 묻기, 고르기) 약 3–4 ns로 3.5 ms, 노드 하나에 간선 범위 찾기(묶은 + 리스트의 색인) 약 15–20 ns로 2 ms, 꼬리 1 ms, 해석 값은 묶음 101개라 무시할 만하다. 합해 약 6–7 ms로, 기계어의 7.7 ms(C 9.9)와 + 겨룰 수 있다. 캐시 미스(간선 열 4 MB)는 C와 기계어도 내는 값이고, 묶음은 레인이 서로 떨어져 있어 미스가 겹친다. +- **필요한 셋.** (1) `if i >= L.count { break }`이고 몸체가 L에 덧붙이기만 하면, 묶음은 열 때의 개수까지다. (2) 레인마다 다른 걷기를 + 레인으로 펼친다. (3) 커지기만 하는 걸러내기: `if !L.has(k) { … }`이고 L이 몸체에서 더해지기만 하면, 열 때 참인 레인은 건너뛰고, + 거짓인 레인은 끝에서 차례대로 다시 묻고 몸체의 덧붙이기를 한다. 몸체가 읽는 것은 열 때 있던 것이어야 한다(BFS의 + `seen[q.node]`는 프런티어의 노드라 열 때 있다; 계획이 이것을 알아볼 규칙이 필요하다). (1)과 (2)는 (3) 없이도 시험할 수 있다 + (프런티어를 돌며 간선 수를 합하는 루프). 그것부터 만들고 잰다. + +## 뜻과 맞음 + +- `APPEND_SOURCE`: DENSE 리스트에서 회차 q에, HASHED 리스트에서 회차 p에 이미 있는 키(그 회차의 결함), 회차 p부터 DENSE가 담지 + 못하는 키(그 회차부터 꼴이 바뀐다), 한 리스트에 회차마다 두 번 덧붙이기(회차대로), 넓어지는 열, 덧붙이기 한가운데에서 다하는 + 메모리 몫 셋. 세 길(묶음, 실행기만, 기계어)이 같고, `exists`, `memory`, `work` 결함이 다 난다. +- 시드 1, 2, 3, 5, 23의 무작위 프로그램(665개)이 커밋마다 다섯 길에서 같았다. 시드 23의 프로그램에서 한꺼번에 덧붙이기가 31,402번 + (항목 400만 개) 돌았고, 메모리 몫 때문에 회차대로 간 것이 292번, 이미 있는 키의 결함이 4번이었다. +- 단위 시험이 세 JIT 모드와 ASan(실행기 모드)에서, aup의 검사가 두 모드에서 통과했다. sanitized `pure-run`으로 시드 1, 5, 23의 + 프로그램과 고정 소스 넷(410개)을 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다. +- Pure의 `make check`가 새벽에 다섯 번 연속 `server_view_workers`(모듈을 바꾼 뒤 스트림이 10초 안에 새 값을 주지 않음)에서 + 실패했다. 묶음을 꺼도, 바꾸기 전 커밋에서도 실패했고, 같은 코드가 09:50에는 세 번 다 통과했다. 따로 돌리면 늘 통과한다. 다른 + 세션이 기기를 쓰던 때의 타이밍 문제로 본다(이 시험은 10-05에도 같은 꼴로 한 번 실패했다). + +## 다음 + +- **모으기 인식의 빈틈.** `total = total + A + B`는 `(total + A) + B`라서 지금의 `x = x op e` 인식에 맞지 않고, 루프 전체가 + 계획에서 빠진다(같은 계산을 `total + (A + B)`로 쓰면 묶인다: 181 → 36 ms). 정수의 합에서는 둘이 같으니, 한 회차에 여러 번 더하는 + 모으기로 받을 수 있다. +- **BFS**: 위의 (1)과 (2)를 만들고 재고, 그다음 (3). +- **join**: HASHED 찾기를 레인에 대고 바로 하기(약 24 ms), 레인의 산수. +- **matmul**: 레인이 적은 중첩 몸체의 명령당 값(미리 풀어 둔 몸체, 곱해 더하기). |