From 65b86223e36948c9cfc3693a3c3018bacc0dddb5 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 22:56:44 +0100 Subject: Research 126: the batch executor's first stage (024) as built and measured: knapsack 1,041 to 13.6 ms in the executor (the compiled code 7.5; its inner loop 1.17x the tier's, the stage's criterion missed; the table's adds left to stage 4), the executor without batch loops unchanged; what measuring overturned (a call among the steps cost 20% of the instructions, so two copies; run aligned to 64 for its cycles; results apart from operands for vector code); tests; 1024 lanes, 134 KB a thread; 024 and CHECKPOINT say so --- CHECKPOINT.md | 2 +- docs/design/024-batch-executor.md | 5 +- docs/research/126-batch-executor-stage-one.md | 100 ++++++++++++++++++++++++++ 3 files changed, 105 insertions(+), 2 deletions(-) create mode 100644 docs/research/126-batch-executor-stage-one.md diff --git a/CHECKPOINT.md b/CHECKPOINT.md index d5aeea1..6662e91 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, 손으로 짠 천장). 구현 전이다. 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) | +| 수명과 계산 | 값의 수명은 선언이 말한다: `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). 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) | | 보기 밀기 | 보기의 `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 1e6fae6..92e065a 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/)). 구현 전. +작성일: 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배로 기준 미달). [023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을 C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만 @@ -108,6 +108,9 @@ C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-s 레인 레지스터 16개 × 256 × 8바이트 = 32 KB를 이벤트 스레드 하나가 쓴다(L1 64 KB 안). 펼친 레인(BFS의 간선)도 256씩 끊어 같은 자리를 쓴다. 묶음 프로그램은 루프마다 연산 수십 개 × 32바이트다. 실행 가능한 페이지도, 코드 캐시도 없다. +1단계는 묶음을 1024 레인으로 했다(126). 묶음마다 명령을 해석하는 고정 값(약 500 ns)을 나누기 위해서다. 그래서 레인 버퍼가 16개 × +1024 × 8바이트 = 약 134 KB다. 스레드의 정적 TLS에 있고, 묶음을 도는 스레드만 그 페이지를 쓴다. + ### JIT와의 관계 022의 JIT(copy 0/1)와 023의 계층은 기계어를 쓴다. 묶음 실행기는 C 컴파일러가 가는 곳 어디서나 같은 코드로 돈다. copy-and-patch도 빌드 때 C로 만든 조각을 쓰지만, 실행 시간에 그 조각을 복사하고 고쳐 실행 가능한 페이지에 쓰고, 기계마다 조각과 고치기가 따로다. 묶음 실행기는 빌드 때 만든 C를 쓰는 생각은 같고, 코드를 쓰지 않는다. Mac과 WSL의 diff --git a/docs/research/126-batch-executor-stage-one.md b/docs/research/126-batch-executor-stage-one.md new file mode 100644 index 0000000..f51b050 --- /dev/null +++ b/docs/research/126-batch-executor-stage-one.md @@ -0,0 +1,100 @@ +# 126 — 묶음 실행기 1단계: 기계어 없이 세는 루프를 회차 1024개씩 + +2026-10-05. [024](../design/024-batch-executor.md)의 1단계를 만들고 잰 것. 코드는 `core/module-batch.c`이고(`1513463`), 측정 스크립트와 +원시 결과는 [041-batches](../../research/experiments/041-batches/)에 있다(`runs.sh`, `2026-10-05-suite.jsonl`, +`2026-10-05-counts.jsonl`). 묶음은 `suite-run` 11번의 중앙값이다. 같은 빌드를 세 가지로 돌렸다. 하나는 기계어(JIT), 하나는 묶음을 쓰는 +실행기(`PURE_JIT=0`), 하나는 실행기만(`PURE_BATCH=0`까지)이다. + +## 쉬운 말로 + +- **실행기가 세는 루프를 회차 1024개씩 돈다.** 루프의 몸체를 회차마다 해석하지 않는다. 명령 하나를 회차 1024개(레인)에 한 번에 한다. + 연산은 빌드 때 C 컴파일러가 만든 루프이고, 실행 시간에 만드는 코드는 없다. knapsack이 실행기만으로 1,041 ms였는데 묶음으로 13.6 ms가 + 된다(77배). 기계어(023의 계층)는 7.5 ms, C는 6.2 ms다. +- **1단계의 기준은 아직 못 맞췄다.** 기준은 "계층보다 느리지 않다"였다. 안쪽 루프만 보면 묶음이 약 8.5 ms, 계층이 약 7.2 ms로 1.17배다 + (둘 다 바깥 부분을 뺀 값이다). knapsack 전체로는 1.8배다. 차이의 대부분은 표를 만드는 바깥 루프다. `table.add`를 5만 번 하는 이 + 루프는 묶을 수 없어서(덧붙이기는 4단계) 실행기에서 5.1 ms가 든다. 계층에서는 0.3 ms다. +- **묶음이 없는 모듈의 실행기는 그대로다.** 명령 수와 사이클이 `e01dae9`와 같거나 조금 적다(roots 27.56억 대 27.60억 명령, 사이클은 + 같다). 여기까지 오는 데 측정이 세 번 짐작을 뒤집었다(아래). +- **어떤 루프를 묶는가.** 몸체의 명령이 모두 레인 꼴을 가진 세는 루프를 묶는다. 레인 꼴은 fold가 쓰는 `has_lanes`와 같다. 그 밖에 + 허락하는 것은 회차마다 먼저 쓰고 읽는 지역 변수, `if`와 `else`, 수 칸에 쓰기다. 합 같은 누적, 점화식, 중첩 루프, `break`, 덧붙이기, + 텍스트, i64가 있으면 묶지 않는다. 그래서 일곱 가지 일 가운데 지금은 knapsack만 묶인다. roots(`break`), matmul(합), join(점화식), + BFS(덧붙이기)는 2–5단계의 몫이다. + +## 묶음 + +| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | +|---|---:|---:|---:|---:| +| knapsack | 7.52 ms | **13.57** | 1,040.9 | 6.23 | +| roots | 9.58 | 130.6 | 130.5 | 6.86 | +| matmul | 14.23 | 914.8 | 914.8 | 7.50 | +| join | 74.2 | 428.4 | 427.2 | 28.6 | +| sort | 36.9 | 78.2 | 82.5 | 26.9 | + +`suite-run` 세 바퀴의 사용자 모드 명령 수(`icount.c`, perf_event_open): + +| 일 | `e01dae9` 실행기 | `1513463` 실행기만 | `1513463` 묶음 | +|---|---:|---:|---:| +| roots | 27.60억 | 27.56억 | 27.56억 | +| knapsack | 219.05억 | 216.88억 | **4.60억** | +| matmul | 214.62억 | 214.36억 | 214.36억 | +| join | 77.15억 | 76.69억 | 76.69억 | +| sort | 15.13억 | 15.02억 | 15.02억 | + +knapsack의 안쪽 루프 하나(500만 회차)에 묶음이 쓰는 시간은 회차당 약 1.7 ns다. 레인을 한 번 도는 일 여섯 가지가 대부분을 차지한다. +거꾸로 읽기 둘, 덧셈과 넘침 검사, 비교, 마스크의 개수 세기, 마스크를 단 저장이다. 그 밖에 묶음마다 명령을 해석하는 고정 값이 +약 500 ns다. 묶음을 256 레인으로 하면 21.6 ms, 512면 16.4, 1024면 13.7 ms였다. + +## 만들며 정한 것 + +- **값의 꼴.** 값은 세 가지 꼴로 든다. 모든 회차에 같은 값(균일), 회차마다 정수 보폭으로 움직이는 정수(아핀), 회차마다의 값(레인)이다. + 레인은 수(8바이트)이거나, 2^32 아래의 정수(4바이트)다. 아핀 값의 덧셈, 뺄셈, 양수 곱셈은 O(1)이다. 아핀 키로 DENSE 리스트를 찾으면 + 양 끝만 검사하고, 그 칸을 읽는 것은 열을 보폭으로 읽는 것이 된다. 아핀 값은 정수이고 2^52 안이며 −0이 아니어야 한다. 그래야 레인마다의 + 값이 회차마다 계산한 값과 비트까지 같다(−0의 부호 포함). 음수를 곱하거나 부호를 바꾸면 레인으로 계산한다. +- **분기.** 레인 조건의 `if`는 두 길을 다 돈다. 각 길은 제 레인(마스크)으로만 돈다. 마스크는 갈라진 부모와 짝을 알아서, 두 길이 다시 + 만나면 계산 없이 부모로 돌아간다. 비교의 0/1 레인이 그대로 마스크가 된다. 돌지 않는 레인의 결함은 결함이 아니다. +- **쓰기는 끝에.** `ITEM_SET`은 묶음의 끝까지 미룬다. 묶음의 어떤 회차도 앞선 회차가 쓴 칸을 읽지 않을 때만 쓴다. 아핀 행끼리는 보폭이 + 같으면 O(1)로, 다르면 O(n)으로 검사한다. 같은 열에 두 번 쓰면 두 쓰기의 차례가 회차와 엇갈리는지도 본다. 열이 좁으면 먼저 넓히고 쓴다. + 넓히는 것은 항목을 바꾸지 않는다. +- **실패하면 그 회차들을 실행기에.** 결함, 꼴이 없는 값, 읽기와 쓰기의 겹침이 있으면 묶음은 아무것도 바꾸지 않았다. 그 회차들은 실행기가 + 하나씩 돌아서 결함이 제 회차에서 난다. 그 뒤 묶음을 다시 시도하고, 한 루프에서 세 번 실패하면 그만둔다. 남은 작업량이 두 회차를 덮지 + 못할 때도 한 회차를 실행기에 넘긴다. 처음에는 넘기지 않아서 작은 예산의 시험에서 무한 루프가 됐다. +- **레인의 방향.** 거꾸로 가는 접근이 더 많으면 다음 묶음부터 레인을 거꾸로 번호 매긴다. 그러면 읽기와 쓰기가 메모리의 차례가 된다. + 의존 검사와 쓰기의 차례는 레인이 아니라 회차로 센다. +- **로드 때 거르기.** 회차를 넘어 이어지는 지역 변수(쓰기 전에 읽는 것)가 있는 루프는 로드 때 계획에서 뺀다. 처음에는 실행 중에만 + 알아서, 무작위 프로그램에서 묶음 실패의 99.9%(3만 5,752번)가 이것이었다. + +## 측정이 뒤집은 것 + +1. **실행기 루프에 호출 하나가 명령 20%였다.** `step`의 LOOP 케이스에 묶음으로 가는 호출을 두자 roots의 명령이 27.6억에서 33.1억이 + 됐다. 묶음은 쓰이지도 않았다. 원인은 `run`의 레지스터 할당이었다. `&frame`이 인라인되지 않는 함수로 넘어가면 Frame의 필드가 모두 + 메모리로 가고, 디스패치마다 스택 기준을 다시 읽고 `pc`를 메모리에 쓴다. 그래서 실행기를 두 벌로 나눴다. 묶음 루프가 없는 모듈은 + 지금과 같은 코드를 돈다(`step`의 묶음 인자가 상수 false로 접힌다). 묶음 루프가 있는 모듈만 사본 `run_batches`를 돈다. 사본은 묶음 + 경로에 Frame의 복사본을 넘긴다. 사본에서 묶음이 아닌 코드는 명령 +2%다. +2. **같은 명령 수, 사이클 +10%.** 두 벌로 나누자 명령 수는 같아졌는데 사이클이 10% 많았다. `run`의 시작 주소가 64바이트 경계에서 + 8바이트 경계로 밀렸기 때문이다. `run`을 64바이트에 맞추자 사이클도 같아졌다. +3. **벡터화된 루프의 값.** 산술 루프가 느린 것을 처음에는 벡터화가 안 된 탓으로 봤다. 실제로는 결과를 입력 레인에 다시 쓰게 해서 gcc의 + 실행 시간 별칭 검사가 스칼라 경로로 떨어진 것이었다. 결과를 늘 새 레인에 쓰고(`restrict`), 다 쓴 레인을 빈 목록으로 돌려쓰게 했다. + 레인 버퍼의 캐시 연관도 충돌도 의심했지만, 버퍼 사이를 엇갈리게 해도 같아서 원인이 아니었다. + +## 뜻과 맞음 + +- `module_tier`가 `PURE_JIT=0`(묶음)과 `PURE_BATCH=0`(실행기만)도 견준다. 상태, 결함, 오류, 작업량이 바이트까지 같아야 하고, 작은 예산 + 넷도 돈다. 생성기에 회차가 서로 떨어진 루프(`lanes`)를 더했다. 몸체 안의 `let`, 아핀 키로 `t`에 쓰기, 조건과 `else`를 섞는다. 시드 + 1, 2, 3, 23의 프로그램 553개가 같았다. 시드 23에서는 139개 중 19개 모듈에서 묶음 884개(53,924 회차)가 돌았다. +- `module_assumptions`에 `BATCH_SOURCE`를 더했다. 넓어지는 열(1바이트 → 4 → 8), 묶음 한가운데의 분수와 −0, 회차 q에서의 0 나누기, + 앞 회차의 쓰기를 읽는 루프(묶음이 실패하고 실행기가 돈다), 거꾸로 가는 키와 `if`/`else`, 한 열에 두 번 쓰기를 담았다. 세 길(묶음, + 실행기만, 기계어)이 같다. +- 단위 시험은 세 JIT 모드와 ASan(실행기 모드)에서 통과했고, aup의 검사는 실행기와 기본 모드에서 통과했다. sanitized `pure-run`으로 + 무작위 프로그램 139개와 `BATCH_SOURCE`를 돌려도 오류가 없었고, 출력은 실행기만으로 돈 것과 같았다. + +## 메모리 + +레인 버퍼는 16개 × 1024 × 8바이트 = 약 134 KB다. 스레드의 정적 TLS에 있고, 묶음을 도는 스레드만 그 페이지를 쓴다. 024가 적은 +32 KB(256 레인)보다 크다. 묶음마다의 고정 값을 나누려고 고른 크기다. + +## 다음 + +- **2단계: 중첩 루프와 모으기.** matmul과 roots는 바깥 루프의 회차를 레인으로 삼고 안쪽 루프를 함께 돌아야 한다. matmul은 횟수가 같고, + roots는 `break`로 레인이 빠진다. 합(`total = total + s`, `count = count + 1`)은 회차의 차례대로 모은다. +- **합친 연산.** knapsack 안쪽의 1.17배는 레인을 여섯 번 도는 값이다. 041의 시제품에서는 합친 연산이 1.7배였다. +- **덧붙이기(4단계).** knapsack 전체의 1.8배는 대부분 실행기에서 도는 `table.add` 루프다. -- cgit v1.2.3