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 --- CHECKPOINT.md | 2 +- docs/design/024-batch-executor.md | 2 +- docs/research/130-batch-executor-frontiers.md | 114 ++++++++++++++++++++++++++ 3 files changed, 116 insertions(+), 2 deletions(-) create mode 100644 docs/research/130-batch-executor-frontiers.md diff --git a/CHECKPOINT.md b/CHECKPOINT.md index b6a01b7..7dc06be 100644 --- a/CHECKPOINT.md +++ b/CHECKPOINT.md @@ -13,7 +13,7 @@ | 영역 | 확인한 것 | 근거 | |---|---|---| | 앱 표현 | 상태(수, `bool`, 정확한 64비트 정수 `i64`, text와 커서·마크, 레코드의 리스트와 키 있는 리스트, 인덱스), 입력(키, text, 필드 있는 메시지, 타이머), 원자적 이벤트 핸들러, 순수 보기(조건식, 표와 걸러진 표, count·sum·max·min·first), `fn`·`use` 라이브러리, text 비교, 시간(`now`, `every`, `floor`, `%`). 로드할 때 타입·스택·합류·커서와 인덱스의 소속을 모두 검증하고 이벤트의 실행량에 상한이 있다 | 008, [016](docs/design/016-bool-and-i64.md), aup `docs/design/002-dsl-direction.md`, aup `make check`(파이썬 참조 모델 대조, 진단 223건) | -| 수명과 계산 | 값의 수명은 선언이 말한다: `state`(저장), `transient state`(앱이 도는 동안: 저장소에 쓰지 않고 다시 시작하면 초기값, SD 카드에서 쓰기 17배), `let`(이벤트 동안). 핸들러와 보기가 계산한다: 이벤트의 리스트(`let seen: list of Seen by node`), 세는 `for i in a .. b`, `break`, 8겹까지의 중첩, 그리고 `view 이름(인자) { … return … }`(스냅숏에서 돌아 소유자를 막지 않는다). 모든 반복은 시작할 때 횟수의 상한을 갖고, 모든 이벤트와 보기는 실행량 예산(정하지 않으면 2^28 명령)과 메모리 몫(2^28 바이트) 안에서 끝난다. 노드 10만·간선 100만의 BFS 한 이벤트가 HTTP로 90 ms였고(처음 397, 020 뒤 191; CPython 452, C 9.1, 123), 022 뒤 코어는 7.4 ms다(같은 프로세스의 C 9.9): 많이 찾는 저장된 리스트를 배열과 칸의 색인으로 펴고, 열을 값만큼 좁히고, 루프 묶음을 레지스터의 기계어로 돈다(리눅스 AArch64의 JIT; 다른 곳은 실행기, 답은 같다). 다만 C를 넘은 것은 미리 읽기 덕이고, 끄면 15.7 ms로 C의 1.57배다. 일곱 가지 일(실수 루프, 배낭, 정렬, 조인, 텍스트, 행렬, BFS)로 C와 견주면 124에서는 3–300배 느렸고, 023의 계층과 표현(HASHED: 차례를 어긴 키는 해시 표의 칸에, 위치가 필요할 때 정렬)으로 지금은 1.19–5.58배(기하 평균 1.92)다(125). Pure의 표현과 뜻대로 손으로 쓴 바닥은 C의 0.90배이고 뜻의 검사는 끌어내면 0–3%라, 막는 것은 실행 계층이다(124). 모든 블록을 SSA로 올리는 최적화 계층(023)의 첫 걸음들이 들어갔고, 텍스트(실행기로 돈다)와 BFS(계층이 덧붙이기를 못 한다)가 남았다. 기계어를 만들지 않는 길로, 루프를 회차 256개의 묶음으로 돌고 연산마다 빌드 때 만든 C 루프를 쓰는 묶음 실행기(024)를 시제품으로 재니 연산을 따로 해석하면 roots 0.99배, 배낭 0.71배(4바이트 레인), BFS 1.03배, join 1.77배, 행렬 곱 2.50배이고, 행렬 곱은 곱해 더하기를 합치면 0.94배였다(계층 1.20–2.46배, 기하 평균 1.92 대 1.58, 합친 꼴로 1.24; 041, 손으로 짠 천장). 1단계(세는 루프의 레인 꼴 몸체, 회차 1024개씩)가 들어가 knapsack이 실행기에서 1,041 ms에서 13.6 ms가 됐다(계층 7.5, 안쪽 루프는 1.17배). 묶음 루프가 없는 모듈의 실행기는 명령과 사이클이 그대로다(126). 2단계(중첩 루프를 레인마다 함께, `x = x + e`·`min`·`max` 모으기)로 roots가 9.13 ms가 되어 기계어 없이 계층(9.57)보다 빠르고, matmul은 914.9에서 50.0 ms다(계층 14.3, 127). 덧붙이기, 점화식, 칸에 더하기, 걷기를 묶어 join이 실행기의 423에서 161 ms가 됐다(계층 74). 남은 값은 덧붙이기 하나 약 100 ns(실행기와 같다), join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 묶이지 않아 기계어를 아직 걷어낼 수 없다(128). 덧붙이기를 리스트의 한 호출로, 점화식을 레지스터 꼴로, 모으기의 끝을 차례 없이 하자 knapsack 10.8, matmul 36.4, join 118, sort 55.5 ms가 됐다(기계어 7.9, 14.2, 72–79, 35.6; 129). BFS는 프런티어 묶음으로 셈하면 차례대로 할 꼬리가 간선의 약 10%다(129). TPC-C −2.8%(기준 3% 안), 은행 질의의 명령 수는 1% 안. 같은 계산이 Pi(JIT)·WSL2·M3 Mac에서 같다. 같은 탐색을 보기로 하면 쓰기는 CPU를 나누는 만큼만 줄고(이벤트로 하면 0.2%로 멈춘다), 본문이 있는 보기는 보기의 스레드(`--view-workers`)가 계산해 연결 스레드를 막지 않는다(쓰기 최대 지연이 CPU만 나눌 때의 1.0배, 연결 스레드 하나에서 묻는 연결 둘이 1.95배) | [018](docs/design/018-lifetimes-and-computation.md), [020](docs/design/020-computing-faster.md), [117](docs/research/117-transient-states.md), [118](docs/research/118-computing-in-one-event.md), [119](docs/research/119-views-that-compute.md), [121](docs/research/121-computing-faster.md), [122](docs/research/122-views-off-the-connection-threads.md), [021](docs/design/021-past-c.md), [123](docs/research/123-past-c.md), [022](docs/design/022-arrays-and-registers.md), [124](docs/research/124-against-c.md), [023](docs/design/023-optimizing-tier.md), [125](docs/research/125-tier-first-steps.md), [024](docs/design/024-batch-executor.md), [126](docs/research/126-batch-executor-stage-one.md), [127](docs/research/127-batch-executor-stage-two.md), [128](docs/research/128-batch-executor-tables-and-costs.md), [129](docs/research/129-batch-executor-costs-cut.md) | +| 수명과 계산 | 값의 수명은 선언이 말한다: `state`(저장), `transient state`(앱이 도는 동안: 저장소에 쓰지 않고 다시 시작하면 초기값, SD 카드에서 쓰기 17배), `let`(이벤트 동안). 핸들러와 보기가 계산한다: 이벤트의 리스트(`let seen: list of Seen by node`), 세는 `for i in a .. b`, `break`, 8겹까지의 중첩, 그리고 `view 이름(인자) { … return … }`(스냅숏에서 돌아 소유자를 막지 않는다). 모든 반복은 시작할 때 횟수의 상한을 갖고, 모든 이벤트와 보기는 실행량 예산(정하지 않으면 2^28 명령)과 메모리 몫(2^28 바이트) 안에서 끝난다. 노드 10만·간선 100만의 BFS 한 이벤트가 HTTP로 90 ms였고(처음 397, 020 뒤 191; CPython 452, C 9.1, 123), 022 뒤 코어는 7.4 ms다(같은 프로세스의 C 9.9): 많이 찾는 저장된 리스트를 배열과 칸의 색인으로 펴고, 열을 값만큼 좁히고, 루프 묶음을 레지스터의 기계어로 돈다(리눅스 AArch64의 JIT; 다른 곳은 실행기, 답은 같다). 다만 C를 넘은 것은 미리 읽기 덕이고, 끄면 15.7 ms로 C의 1.57배다. 일곱 가지 일(실수 루프, 배낭, 정렬, 조인, 텍스트, 행렬, BFS)로 C와 견주면 124에서는 3–300배 느렸고, 023의 계층과 표현(HASHED: 차례를 어긴 키는 해시 표의 칸에, 위치가 필요할 때 정렬)으로 지금은 1.19–5.58배(기하 평균 1.92)다(125). Pure의 표현과 뜻대로 손으로 쓴 바닥은 C의 0.90배이고 뜻의 검사는 끌어내면 0–3%라, 막는 것은 실행 계층이다(124). 모든 블록을 SSA로 올리는 최적화 계층(023)의 첫 걸음들이 들어갔고, 텍스트(실행기로 돈다)와 BFS(계층이 덧붙이기를 못 한다)가 남았다. 기계어를 만들지 않는 길로, 루프를 회차 256개의 묶음으로 돌고 연산마다 빌드 때 만든 C 루프를 쓰는 묶음 실행기(024)를 시제품으로 재니 연산을 따로 해석하면 roots 0.99배, 배낭 0.71배(4바이트 레인), BFS 1.03배, join 1.77배, 행렬 곱 2.50배이고, 행렬 곱은 곱해 더하기를 합치면 0.94배였다(계층 1.20–2.46배, 기하 평균 1.92 대 1.58, 합친 꼴로 1.24; 041, 손으로 짠 천장). 1단계(세는 루프의 레인 꼴 몸체, 회차 1024개씩)가 들어가 knapsack이 실행기에서 1,041 ms에서 13.6 ms가 됐다(계층 7.5, 안쪽 루프는 1.17배). 묶음 루프가 없는 모듈의 실행기는 명령과 사이클이 그대로다(126). 2단계(중첩 루프를 레인마다 함께, `x = x + e`·`min`·`max` 모으기)로 roots가 9.13 ms가 되어 기계어 없이 계층(9.57)보다 빠르고, matmul은 914.9에서 50.0 ms다(계층 14.3, 127). 덧붙이기, 점화식, 칸에 더하기, 걷기를 묶어 join이 실행기의 423에서 161 ms가 됐다(계층 74). 남은 값은 덧붙이기 하나 약 100 ns(실행기와 같다), join의 점화식 회차당 약 60 ns, 레인이 적은 중첩 몸체의 해석이고, BFS는 묶이지 않아 기계어를 아직 걷어낼 수 없다(128). 덧붙이기를 리스트의 한 호출로, 점화식을 레지스터 꼴로, 모으기의 끝을 차례 없이 하자 knapsack 10.8, matmul 36.4, join 118, sort 55.5 ms가 됐다(기계어 7.9, 14.2, 72–79, 35.6; 129). BFS는 프런티어 묶음으로 셈하면 차례대로 할 꼬리가 간선의 약 10%다(129). 가드 루프, 묶음 안의 걷기, 커지기만 하는 걸러내기로 BFS도 묶음으로 돌아 93에서 41 ms가 됐다(기계어 7.7, C 10). 간선당 명령 211개 대 38.5개이고, 이 꼴의 바닥(약 50개)이 기계어 위라서 기계어를 걷어내려면 합친 연산이 필요하다(130). TPC-C −2.8%(기준 3% 안), 은행 질의의 명령 수는 1% 안. 같은 계산이 Pi(JIT)·WSL2·M3 Mac에서 같다. 같은 탐색을 보기로 하면 쓰기는 CPU를 나누는 만큼만 줄고(이벤트로 하면 0.2%로 멈춘다), 본문이 있는 보기는 보기의 스레드(`--view-workers`)가 계산해 연결 스레드를 막지 않는다(쓰기 최대 지연이 CPU만 나눌 때의 1.0배, 연결 스레드 하나에서 묻는 연결 둘이 1.95배) | [018](docs/design/018-lifetimes-and-computation.md), [020](docs/design/020-computing-faster.md), [117](docs/research/117-transient-states.md), [118](docs/research/118-computing-in-one-event.md), [119](docs/research/119-views-that-compute.md), [121](docs/research/121-computing-faster.md), [122](docs/research/122-views-off-the-connection-threads.md), [021](docs/design/021-past-c.md), [123](docs/research/123-past-c.md), [022](docs/design/022-arrays-and-registers.md), [124](docs/research/124-against-c.md), [023](docs/design/023-optimizing-tier.md), [125](docs/research/125-tier-first-steps.md), [024](docs/design/024-batch-executor.md), [126](docs/research/126-batch-executor-stage-one.md), [127](docs/research/127-batch-executor-stage-two.md), [128](docs/research/128-batch-executor-tables-and-costs.md), [129](docs/research/129-batch-executor-costs-cut.md), [130](docs/research/130-batch-executor-frontiers.md) | | 보기 밀기 | 보기의 `GET`에 `Accept: text/event-stream`이면 그 값을 민다(SSE, 브라우저의 `EventSource` 그대로). 같은 보기와 인자를 보는 구독자는 계산 한 번을 나누고, 값이 바뀔 때만, 많아야 10 ms마다 한 번 보낸다. 느린 구독자에게는 가장 새 값 하나만 기다리게 한다. 모듈이 바뀌어도 같은 이름의 보기로 이어 가고, 토큰을 빼면 끊는다. 구독자 1,000에 쓰기 초당 100번까지 신선도 p99 11 ms 이하, 초당 1번이면 100 ms 폴링의 약 10분의 1 CPU(이벤트 하나와 요청 하나의 값이 같아 메시지 수의 비다), 구독자 1만에 구독자마다 0.3–0.4 KiB, 1만에게 퍼지기까지 p99 45 ms | [019](docs/design/019-pushing-views.md), [120](docs/research/120-pushing-views.md) | | 영속 | 선언한 상태가 곧 영속 상태다. 목록은 이미지와 로그(저장마다 바뀐 기록 한 항목, 재사용하는 할당 구간, 앞 항목의 다이제스트로 이어짐)에, 나머지는 트리 저장소에(커밋당 한 연속 구간과 동기화 한 번). 이벤트 묶음마다 저장 한 번, 이미지는 소유자 밖에서 체크포인트. `kill -9`와 커밋 각 단계의 죽음 뒤 확인 응답한 이벤트가 모두 남는다. 레코드·키가 바뀐 모듈로 바꿔도 데이터가 이름으로 옮겨진다 | [076](docs/research/076-one-sync-commit.md), [081](docs/research/081-tail-records.md), [092](docs/research/092-tpcc.md), 008 상태 영속·교체 | | 인터페이스 | 한 명세가 TUI(셀 단위 갱신), CLI, 문장(NUI), 웹 GUI가 된다. 저장하면 실행 중인 앱이 상태를 이어 새 모듈로 바뀐다(`aup watch`, `vega … --watch`) | Vega `docs/design/001-first-component.md`, Vega `make check`(가상 터미널, 헤드리스 Chromium 포함) | 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