From 1b902056b7f2b68277534bcfbfa32d0808dbe05b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Thu, 8 Oct 2026 07:46:32 +0100 Subject: Research 130: the batch executor's frontiers (a count's guard, walks in a batch's rounds together or spread into lanes, filters asked as a batch opens and again at its end): the suite's BFS batched, 93 to 41 ms (the compiled code 7.7, C 10); where it goes (211 instructions an edge against 38.5: a filter's code over every lane the most); the floor of operations each a pass over the lanes (about 50 an edge, 1.3x the compiled code) and what would pass it (fused operations from a table, 024's); the choice left: a table of them, or the compiled code kept for such work; 024 and CHECKPOINT say so --- docs/design/024-batch-executor.md | 2 +- docs/research/130-batch-executor-frontiers.md | 114 ++++++++++++++++++++++++++ 2 files changed, 115 insertions(+), 1 deletion(-) create mode 100644 docs/research/130-batch-executor-frontiers.md (limited to 'docs') diff --git a/docs/design/024-batch-executor.md b/docs/design/024-batch-executor.md index 91e60a5..ec9a6c8 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 예상). +작성일: 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개라, 계층을 넘으려면 합친 연산의 표가 필요하다. [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/130-batch-executor-frontiers.md b/docs/research/130-batch-executor-frontiers.md new file mode 100644 index 0000000..f74dafc --- /dev/null +++ b/docs/research/130-batch-executor-frontiers.md @@ -0,0 +1,114 @@ +# 130 — 묶음 실행기로 BFS를: 가드, 묶음 안의 걷기, 걸러내기, 그리고 이 설계의 바닥 + +2026-10-08. [129](129-batch-executor-costs-cut.md)가 BFS에 필요하다고 적은 세 조각을 만들었다. 코드는 `33c6ef5`(가드와 묶음 안의 +걷기)와 `9b0b23f`(걸러내기)다. 같은 방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b7` = `9b0b23f`, 11번의 중앙값). 탐색만의 명령은 +`041-batches/search/`의 드라이버로 셌다(그래프를 읽은 뒤 탐색을 1번과 11번 돌려 뺐다, `2026-10-08-search-counts.jsonl`). + +## 쉬운 말로 + +- **BFS가 묶음으로 돈다.** 실행기만 93.4 ms이던 것이 묶음으로 41.0 ms다. 답(홉, 닿은 노드 수)은 C와 같다. 그러나 기계어는 7.66 ms, + C는 10.0 ms다. 기계어의 5.4배다. +- **어디에 드는지 셌다.** 탐색 하나에 묶음은 간선당 명령 211개(사이클 81개), 기계어는 38.5개(17개)다. 가장 큰 낭비는 걸러내기의 + 몸체다. 후보(간선의 약 10%)에만 필요한 명령 약 12개를 1024 레인 모두에 돈다. +- **이 설계의 바닥은 기계어보다 조금 위다.** 후보만 골라 몸체를 돌게 해도, 연산 하나가 레인을 한 번 훑는 방식으로는 간선당 약 50개로 + 셈된다. 기계어의 약 1.3배다. 기계어와 같거나 넘으려면 024의 표에 있던 합친 연산("칸을 모아 묻기", "묻고 고르기")이 있어야 한다. + 이것을 할지가 JIT를 걷어낼지를 정한다(아래, 판단할 것). + +## 묶음 + +| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | +|---|---:|---:|---:|---:| +| roots | 9.57 ms | **8.95** | 130.5 | 6.86 | +| knapsack | 7.94 | 10.32 | 1,053.9 | 6.24 | +| matmul | 14.89 | 36.51 | 914.8 | 7.81 | +| join | 78.75 | 117.8 | 427.6 | 34.7 | +| sort | 35.5 | 56.8 | 78.3 | 26.9 | +| BFS | 7.66 | **41.0** (b6 97.0) | 93.4 | 10.0 | +| words | 216.4 | 214.3 | 209.7 | 38.1 | + +- BFS 말고는 b6과 같다. 실행기만의 명령도 같다(roots 27.56억, knapsack 216.88억, matmul 214.37억, join 76.70억, sort 15.03억). + 바꾼 것은 묶음과 리스트, 그리고 로드 때의 계획이다. +- BFS의 묶음 명령은 `suite-run` 세 바퀴(C와 읽기 포함)로 46.93억(b5)에서 37.64억이 됐다. + +## 만든 것 + +- **가드**(`33c6ef5`). 세는 루프의 블록이 `if i >= L.count { break }`로 시작하고 블록이 L에 더하기만 하면(`PLAN_GUARD`), 묶음은 열 때의 + L의 개수까지만 돈다. 그 회차들에서 실행기의 시험도 거짓이다(개수는 커지기만 한다). 남은 회차가 최소(16)에 못 미치면 그 회차들은 + 실행기가 돌고, 그 뒤에 다시 묶음을 시도한다(BFS의 처음 몇 층). +- **묶음 안의 걷기**(`33c6ef5`). 묶음의 블록에 있는 `EACH`(조각이면 레인마다의 조각, where의 범위는 없음)는 레인마다 제 항목들을 걷는다. + 작업량은 각 걷기가 열릴 때 센다. 두 가지로 돈다. + - **함께**: 중첩 LOOP처럼 회차 t를 항목이 t개보다 많은 레인들이 돈다. `break`가 있으면 이 길이다. + - **펼치기**(`PLAN_SPREAD`): `break`가 없고 걷기가 정하는 지역 변수가 모으기이거나 항목 자신의 것이면, 항목들을 회차 차례대로 + 레인으로 펼쳐 1024개씩 돈다. 바깥 레인의 값은 각 항목의 바깥 레인에서 모아 읽는다. 모으기는 바깥 레인의 몫에 항목 차례대로 + 더한다. 항목 자신의 변수는 그것을 쓴 마지막 항목의 값을 남긴다(루프의 블록 다른 곳에서는 읽지 않는다). 함께 돌면 레인-회차가 + 간선의 2.17배라서(129) 펼치기가 기본이다. +- **걸러내기**(`9b0b23f`). `if !L.has(k) { 덧붙이는 곧은 코드 }`이고 L이 그 코드에서만 커지면(`PLAN_FILTER`; 리스트 하나에 걸러내기 + 하나, 중첩 LOOP 안에는 없음) 이렇게 한다. + 1. 묶음을 열 때의 L로 레인마다 묻는다. 참인 회차는 실행기도 건너뛴다(L은 커지기만 한다). + 2. 거짓인 회차에서 몸체를 돌리고, 그 회차들을 (회차, k, 덧붙이기의 칸들)로 모아 둔다. 펼친 걷기에서는 덩어리마다 모은다. + 3. 끝에서 회차 차례대로 다시 묻는다. 기준은 지금의 L과, 앞서 모은 회차가 더하는 키다. 그사이 더해졌으면 그 회차는 뺀다. + 4. 남은 것을 리스트마다 한꺼번에 넣는다(`pure_list_add_many`). + + 다시 묻고 결정하고 메모리 몫을 셈하는 일은 어떤 것도 바꾸기 전에 한다. 이미 있는 키를 더하려 하거나, 리스트가 그 꼴로 받지 못하거나, + 몫이 모자라면 묶음이 회차들을 돌려준다. 그러면 실행기가 정확한 회차에서 결함을 낸다. +- **커지는 리스트 읽기.** 걸러내기가 키우는 리스트는 앞 회차의 항목이 바꾸지 않는 꼴로만 읽는다. 가드의 개수, `first`, 키 없는 + 리스트의 자리, 키로 찾은 필드가 그렇다. 키로 찾아 없으면 묶음이 돌려준다. +- **키의 비트맵.** 키가 비트로 있는 리스트(`pure_list_bits`)의 `has`와, DENSE 리스트(모든 키가 있지는 않은 것도, `pure_list_dense`)의 + 키로 찾기를 레인 루프 하나로 한다. 4바이트 행과 키는 따로 빠른 루프를 쓴다. + +## 무엇에 값을 내는가 (BFS) + +| | 묶음 | 기계어 | +|---|---:|---:| +| 탐색 하나의 명령 | 2억 1,130만 | 3,850만 | +| 간선당 명령 / 사이클 | 211 / 81 | 38.5 / 17 | +| 프런티어 합(간선의 `to`를 더하기만)의 간선당 명령 / 사이클 | 70 / 26 | 35 / 15 | + +표본(탐색만, 묶음)으로 나누면 이렇다. +- 걸러내기 몸체를 모든 레인에 도는 값이 가장 크다. 키로 찾기, 칸 모으기 둘, 바깥 값 모으기, 행 검사가 대부분 여기서 난다(약 40%). +- 간선마다 하는 일(덩어리 만들기, `to` 모으기, `has`, `NOT`, 마스크)이 약 25%다. +- 후보를 모으고 다시 묻고 넣는 일(`keep_filtered`, `decide`, `apply_filters`와 그 리스트 호출)이 약 25%다. +- 노드마다 조각 경계를 두 번 찾는 일(`pack_seek`)이 약 6%다. + +**바닥의 셈.** 후보만 골라 몸체를 돌게 하면(고르기) 간선마다 남는 것은 레인 훑기 일곱 번쯤이다. 덩어리 만들기, `to` 모으기, `has`, `NOT`, +마스크, 후보 고르기가 그렇다. 훑기 한 번이 요소당 명령 3–5개이니 간선당 약 25개다. 여기에 다음이 더해진다. +- 노드마다: 경계 찾기와 바깥 연산, 간선 10개로 나누면 약 14개 +- 후보마다: 몸체와 다시 묻기와 넣기, 후보가 10%라 약 11개 + +합해 간선당 약 50개, 사이클로 약 23개다. 기계어의 1.3배쯤이다. 프런티어 합이 70개(기계어 35개)인 것도 같은 결을 보인다. 연산마다 +레인을 따로 훑는 값이 기계어의 레지스터 안 계산보다 크다. 이 바닥을 넘으려면 자주 나오는 연산의 짝을 빌드 때 C로 만든 합친 연산으로 +해야 한다. "행에서 `to`를 모아 비트에 묻기"를 하나로, "묻고 거짓인 레인 고르기"를 하나로 하는 식이다. 024가 처음부터 표로 두자고 한 +것이고, 묶음에서 나오는 꼴을 세어 정하기로 했던 것이다. + +## 뜻과 맞음 + +- 생성기에 `front` 꼴을 더했다. 가드 루프 안에 걷기(조각과 통째, 빈 조각 포함)가 있고, 그 안에 다음이 섞인다. + - 모으기, 분수, 항목 자신의 `let`, 바깥 변수 읽기 + - `break`(함께 도는 길) + - 걸러내기 `if !d.has(k) { d.add(...); e.append(...) }`(가끔 다른 키를 더해 부딪침) + + 시드 1, 2, 3, 5, 23의 프로그램이 다섯 길에서 같았다. 시드 23의 프로그램에서 펼친 걷기 8,819번, 함께 도는 걷기 7,651번이 돌았고, + 걸러내기는 5,806번 결정해 38번 돌려줬다(`33c6ef5` 때와 `9b0b23f` 때의 생성기 기준). +- 고정 소스는 둘이다. + - `FRONT_SOURCE`: 목록보다 긴 가드 루프, 레인마다 다른 조각, `break`가 있는 걷기, 분수의 합, 0 나누기, 작업량 예산 + - `GRAPH_SOURCE`: 걸러내기로 만든 그래프, 같은 그래프로 두 번의 BFS, 묻는 키와 다른 키를 더해 `EXISTS`가 나는 루프, 걸러내기의 + 넣기 한가운데에서 다하는 작업량·메모리 몫. 이 소스에서 걸러내기가 662번 결정하고 123번 돌려줬다. + + 세 길이 바이트까지 같다. +- 단위 시험 세 모드, ASan(실행기 모드), aup의 검사 두 모드, Pure의 `make check`가 통과했다. sanitized `pure-run`으로 시드 23의 프로그램과 + 고정 소스 여섯을 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다. +- ASan이 처음에 누수를 찾았다. 보기의 스레드에서 돈 걸러내기가 스레드 지역 버퍼를 남긴 것이다. 이제 묶음이 끝날 때마다 그 버퍼들을 + 놓는다. 메모리를 쥐고 있지 않는 쪽이기도 하다. +- `make check`에서 `server_clocks`와 `server_view_workers`가 한 번씩 실패했고, 다시 돌리자 통과했다(알려진 타이밍 문제). + +## 판단할 것 + +BFS는 기계어를 걷어내는 기준의 마지막 일이다. 셈으로는 지금의 꼴(연산마다 레인을 한 번 훑기)이 기계어의 약 1.3배에서 멈춘다. 길은 +둘이다. + +1. **합친 연산의 표를 만든다.** 빌드 때 C로 만드는 작은 연산 묶음이다. 실행 시간에 코드를 만들지 않는다는 원칙은 그대로다. 묶음에서 + 자주 나오는 짝을 세어 고르고, 계획이 그 짝을 알아보면 쓴다. 표는 유한하고, 맞지 않는 꼴은 지금처럼 따로 돈다. +2. **기계어를 BFS 같은 일에 남긴다.** 묶음 실행기가 덮지 못하는 곳에서만 쓴다. + +어느 쪽이든 다음 일은 같다. 걸러내기 몸체와 `if`/`else`의 갈래, roots의 빠진 레인처럼 레인이 적게 도는 곳을 위한 고르기다. 레인이 적을 때 +그 레인만 모아 돈다. 그것을 만들어 재고, 이 셈과 견준다. -- cgit v1.2.3