From 33091dbffe19bcac00fb7863e24bf0fd445dadd0 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Thu, 8 Oct 2026 14:36:27 +0100 Subject: Design 025: batch programs (132's A), the block's facts once at load and only values each batch: knapsack's per-batch cost measured at 0.90 us, 38% of its 11.5 ms (BATCH 1024 against 256 under a sampled profile: re-reading the block about 39%, value kinds 26%, list facts and dependence 22%, dispatch 14%), sum0's 0.33 us, matmul's inner-round dispatch about 13 ms and float-checked arithmetic about 22; five stages (facts at load, static kinds and list facts once a batch, typed kernels, fewer passes, the tails) with bars from those shares; 041 batch-costs data --- CHECKPOINT.md | 2 +- docs/design/024-batch-executor.md | 2 +- docs/design/025-batch-programs.md | 179 +++++++++++++++++++++ .../041-batches/2026-10-08-batch-costs.jsonl | 85 ++++++++++ research/experiments/041-batches/runs.sh | 6 +- 5 files changed, 271 insertions(+), 3 deletions(-) create mode 100644 docs/design/025-batch-programs.md create mode 100644 research/experiments/041-batches/2026-10-08-batch-costs.jsonl diff --git a/CHECKPOINT.md b/CHECKPOINT.md index d60a126..9db7e80 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). 가드 루프, 묶음 안의 걷기, 커지기만 하는 걸러내기로 BFS도 묶음으로 돌아 93에서 41 ms가 됐다(기계어 7.7, C 10). 간선당 명령 211개 대 38.5개이고, 이 꼴의 바닥(약 50개)이 기계어 위라서 기계어를 걷어내려면 합친 연산이 필요하다(130). 범용 장치만으로(같은 코드의 값 다시 쓰기, 고르기, 비트로 묻기, 아핀 `first + i`) 간선당 112개, 24.0 ms가 됐고, 범용의 바닥은 기계어의 약 2배로 보인다(131). 레지스터 타일 해석기를 시제품으로 재니(133) 산수의 사슬은 C보다 빠르고(roots 5.8 ms) 모으기가 있는 몸체는 졌으며(배낭 4배, BFS 2.4배), 같은 자리에서 꽉 짠 훑기가 BFS 기계어의 1.2배·배낭 0.4배였다: 훑기의 꼴은 옳고 3배는 구현이라, 묶음 프로그램을 로드 때 한 번 만들고 루프를 꽉 짜는 길로 간다. 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), [131](docs/research/131-batch-executor-general-cuts.md), [132](docs/research/132-batch-executor-floor-and-the-way-past.md), [133](docs/research/133-register-tiles-measured.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). 범용 장치만으로(같은 코드의 값 다시 쓰기, 고르기, 비트로 묻기, 아핀 `first + i`) 간선당 112개, 24.0 ms가 됐고, 범용의 바닥은 기계어의 약 2배로 보인다(131). 레지스터 타일 해석기를 시제품으로 재니(133) 산수의 사슬은 C보다 빠르고(roots 5.8 ms) 모으기가 있는 몸체는 졌으며(배낭 4배, BFS 2.4배), 같은 자리에서 꽉 짠 훑기가 BFS 기계어의 1.2배·배낭 0.4배였다: 훑기의 꼴은 옳고 3배는 구현이라, 묶음 프로그램을 로드 때 한 번 만들고 루프를 꽉 짜는 길로 간다. 그 값을 재니 배낭에서 묶음마다 0.90 µs(시간의 38%)이고, 블록의 모양에서 나오는 사실은 로드 때, 값에서 나오는 사실만 묶음마다 보는 설계를 다섯 단계로 세웠다(025). 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), [131](docs/research/131-batch-executor-general-cuts.md), [132](docs/research/132-batch-executor-floor-and-the-way-past.md), [133](docs/research/133-register-tiles-measured.md), [025](docs/design/025-batch-programs.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 26a4fb7..5d35ae3 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 예상). 가드, 묶음 안의 걷기(함께, 펼치기), 걸러내기를 만들어 BFS가 묶음으로 돈다([130](../research/130-batch-executor-frontiers.md): 93 → 41 ms, 계층 7.7). 간선당 명령은 211개(계층 38.5)이고, 후보만 골라 돌게 해도 연산마다 레인을 훑는 꼴의 바닥이 약 50개라, 계층을 넘으려면 합친 연산의 표가 필요하다. 사용자는 범용의 길을 택했다(2026-10-08). 같은 코드의 값 다시 쓰기, `if !c`의 분기 하나, 고르기(적은 레인의 갈래를 그 레인만), 비트로 묻기, 아핀 `first + i`로 BFS가 간선당 112개, 24.0 ms가 됐다([131](../research/131-batch-executor-general-cuts.md)); 범용의 바닥은 계층의 약 2배로 보인다. 레지스터 타일(값을 NEON 레지스터에 두는 해석기)을 시제품으로 재니 산수의 사슬(roots)은 C보다 빠르지만 모으기가 있는 몸체(배낭 4배, BFS 2.4배)에서 졌고, 같은 자리에서 꽉 짠 훑기는 BFS 1.2배·배낭 0.4배였다([133](../research/133-register-tiles-measured.md)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. +작성일: 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개라, 계층을 넘으려면 합친 연산의 표가 필요하다. 사용자는 범용의 길을 택했다(2026-10-08). 같은 코드의 값 다시 쓰기, `if !c`의 분기 하나, 고르기(적은 레인의 갈래를 그 레인만), 비트로 묻기, 아핀 `first + i`로 BFS가 간선당 112개, 24.0 ms가 됐다([131](../research/131-batch-executor-general-cuts.md)); 범용의 바닥은 계층의 약 2배로 보인다. 레지스터 타일(값을 NEON 레지스터에 두는 해석기)을 시제품으로 재니 산수의 사슬(roots)은 C보다 빠르지만 모으기가 있는 몸체(배낭 4배, BFS 2.4배)에서 졌고, 같은 자리에서 꽉 짠 훑기는 BFS 1.2배·배낭 0.4배였다([133](../research/133-register-tiles-measured.md)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. 묶음마다의 값을 다시 재니 배낭에서 0.90 µs, 시간의 38%이고(132의 "6,500 명령"은 세 배로 잘못 나눈 수였다), 블록의 모양에서 나오는 사실은 로드 때 한 번, 값에서 나오는 사실만 묶음마다 보는 묶음 프로그램을 다섯 단계로 설계했다([025](025-batch-programs.md)). [023](023-optimizing-tier.md)의 계층은 루프 묶음을 SSA로 올려 AArch64 기계어를 실행 시간에 만든다. 일곱 가지 일의 기하 평균을 C의 3–300배에서 1.92배로 줄였지만([125](../research/125-tier-first-steps.md)), 실행 가능한 메모리에 코드를 쓰고 리눅스 AArch64에서만 diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md new file mode 100644 index 0000000..ce8fe6f --- /dev/null +++ b/docs/design/025-batch-programs.md @@ -0,0 +1,179 @@ +# 025 — 묶음 프로그램: 블록은 로드 때 한 번 읽고, 묶음마다는 값만 본다 + +작성일: 2026-10-08. 상태: 설계. [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번 +만든다")이고, [132](../research/132-batch-executor-floor-and-the-way-past.md)의 A, [133](../research/133-register-tiles-measured.md)이 +정한 길이다. 사용자의 방향: 범용 장치로, 합친 연산의 표 없이, 기계어 없이, 메모리를 적게(2026-10-05, 2026-10-08). + +## 쉬운 말로 + +- 묶음 실행기는 묶음 하나를 열 때마다 루프의 블록을 처음부터 다시 읽는다. 어느 지역 변수를 쓰는지, 점화식과 칸에 더하기가 + 어디 있는지, 이 `LOCAL_LOAD`가 모으기의 앞인지, 같은 코드의 값이 어디서 오는지를 다시 찾고, 명령마다 값의 꼴(균일·아핀·레인)을 + 다시 묻는다. 블록은 바뀌지 않으니 답도 매번 같다. +- 배낭에서 이 값이 묶음 하나에 0.90 µs, 시간의 38%다(11.5 ms 가운데 4.4). matmul은 같은 일을 묶음이 아니라 안쪽 회차(k)마다 + 한다(메시지 하나에 4만 번). 132는 이 값을 "묶음마다 6,500 명령"이라 적었는데, 세 번 돈 수를 한 번의 묶음 수로 나눈 것이었다. + 고쳤다: 작은 블록에서 약 2,300 명령(0.33 µs)이다. +- 그래서 사실을 둘로 가른다. **블록의 모양에서 나오는 것**은 로드 때 루프마다 한 번 셈해 둔다(묶음 프로그램). **값에서 나오는 + 것**(레인이 4바이트에 드는지, 열의 폭, 경계, 의존 거리, 고를 레인)만 묶음마다 본다. +- 그 위에서 연산을 꼴과 폭에 맞춘 루프로 돌리고(예: 균일한 값을 더하는 모으기는 레인을 돌지 않고 `v × n`, 4바이트 곱하기), + 읽기를 피연산자로 받아 훑기의 수를 줄인다(배낭 6에서 3). +- 합친 연산의 표, 레지스터 타일, 기계어는 쓰지 않는다. 메모리는 루프마다 블록 길이쯤의 표가 는다. + +## 잰 것: 값이 어디에 있는가 + +방법. `b9`의 코어(`735ba81`; 그 뒤의 커밋은 문서와 헤더 하나)를 묶음 레인 1024와 256으로 빌드해(gcc `-O2 -g`, `module-batch.c`는 +`-O3`), `suite-run`을 `PURE_JIT=0`으로 돌리며 2 kHz로 표본을 떴다. 줄마다의 표본을 같은 프로세스에서 도는 C(6.24 ms)의 표본으로 +ms로 바꾸고, 두 빌드의 차를 묶음 수의 차로 나눴다. 원본은 `041-batches/2026-10-08-batch-costs.jsonl`이다. + +### 배낭: 묶음마다 0.90 µs, 시간의 38% + +배낭은 메시지 하나에 회차 4,949,075개를 레인 1024로 4,886 묶음, 256으로 19,376 묶음에 돈다. 시간은 11.49와 24.56 ms다. +(24.56 − 11.49) / 14,490 = **0.90 µs**가 묶음마다이고, 1024 레인에서 4,886 × 0.90 = 4.4 ms다. 그 13.6 ms(표본의 합)를 나누면: + +| 갈래 | 무엇 | 몫 | +|---|---|---:| +| 블록 다시 읽기 | `recurrences` 1.58, `sums` 0.82, `batch_run`의 쓰는 지역 변수 훑기와 앞뒤 약 1.1, `pass`의 명령마다 찾기(칸에 더하기·점화식·같은 코드의 값·기록) 1.34, `local_load`의 모으기 앞 검사 0.12, 걸러내기 버퍼 놓기 0.30 (`batch_run`의 몫 가운데 일부는 남는다) | **약 39%** | +| 값의 꼴 | `whole`·`whole32` 0.75(`floor`를 PLT로 부른다), `word_op`·`binary`·`affine_op` 1.15, `local_load`·`local_store` 1.0, `item_get` 0.37, `branch`·`arrive` 0.35 | 약 26% | +| 리스트의 사실과 의존 | 리스트 쪽(`pure_list_cells`, 키 찾기) 0.80, `rows_in` 0.57, `find` 0.53, `read_of` 0.47, `settle` 0.39, `reads_set`·`cells_at` 0.28 | 약 22% | +| 명령 디스패치 | `pass`의 나머지 1.40, 그 밖 | 약 14% | + +하나하나는 작고, 다 "블록을 읽어 정해진 사실을 다시 셈하기"이거나 "묶음에 한 번이면 될 것을 명령마다 하기"다. 배낭의 요소마다 +(훑기 여섯)는 회차당 약 2.9 사이클로 이미 꽉 짠 루프에 가깝다(나머지 7.1 ms 가운데 약 1 ms는 항목과 표를 만드는 일). + +### sum0: 묶음마다 0.33 µs + +`costs/sum0`(`total = total + 1`, `let` 둘)을 4M 회차로 돌리면 1024와 256 레인이 8.63과 12.54 ms다. 묶음 11,718개의 차로 나누면 +0.33 µs다(`icount`로는 2,330 명령, 805 사이클). 블록 다시 읽기(`recurrences` 훑기, 쓰는 지역 변수 훑기, `pass`의 찾기, 모으기 앞 +검사)가 약 34%, `whole`이 8%다. 점화식이 없는 블록도 점화식을 찾느라 블록을 두 번 훑는다. + +같은 프로파일이 다른 것도 보인다. 이 루프 시간의 약 80%가 모으기다. `total = total + 1`에 레인마다 부분합을 놓고(`reduction`), +더하고(`reduce_step`), 크기와 함께 접는다(`fold`). 훑기 셋이다. 기계어는 더하기 하나다. + +### matmul: 안쪽 회차마다의 디스패치와 실수 검사 + +matmul은 j를 레인 200개로 묶고 k를 레인이 함께 돈다. 묶음은 200개뿐이지만 `pass`가 안쪽 회차마다 몸체를 다시 해석한다(4만 번). +표본으로 `pass` 16%, `sweep` 4.6%, `find` 2.7%, `affine_of` 2.2%, 리스트의 사실 1.5%, `nested` 1.3%, 합 약 13 ms(안쪽 회차마다 +약 0.3 µs)다. 나머지 큰 몫은 연산이다. 1바이트 열에서 읽은 값을 곱하고 더하는데, `words_op`에 곱하기가 없어 8바이트 실수로 +바꾸고(`numbers` 3 ms) 유한 검사를 하는 실수 연산으로 간다(`binary` 약 17 ms). + +### 다른 일 + +- **BFS**(24.0 ms): 묶음마다의 값이 작다((26.0 − 24.3)/3 = 0.6 ms). 간선당 112 명령은 레인 훑기 약 45, 노드마다 약 20, 후보마다 + 약 26이다(131). +- **roots**(8.97): 묶음마다 약 0.6 ms((10.8 − 8.97)/3). +- **join**(117): 묶음마다 약 3 ms. 점화식 `x`를 회차마다 해석하는 값이 약 20%(차례가 있는 사슬이라 바닥에 가깝다), 칸에 더하기의 + 꼬리가 약 10%(회차마다 열의 폭을 가른다), 키로 찾기(리스트 쪽)가 약 13%다. +- **sort**와 **words**는 리스트 쪽 정렬과 텍스트라 이 설계 밖이다. + +## 사실의 두 갈래 + +| 블록의 모양에서 (로드 때 한 번) | 값에서 (묶음마다) | +|---|---| +| 블록이 쓰는 지역 변수와 쓰는 자리, 항목을 쓰는지 | 레인 값이 4바이트에 드는지(넘치면 8바이트로, 지금처럼 커널이 알린다) | +| 점화식: 갱신과 걸음, 걸음의 피연산자가 어디서 오는지, 기록과 그 짝 | 점화식의 처음 값, LOAD·필드·바깥 지역 변수의 값 | +| 칸에 더하기의 자리(again, add, set) | 열의 폭(묶음 끝에서 넓어질 수 있다), DENSE인지, 개수 | +| 모으기: 어느 `LOCAL_LOAD`가 `x = x op e`의 앞인지 | 균일 값의 부호(아핀 곱), 경계 안인지, 읽기와 쓰기의 의존 거리 | +| 같은 코드의 값(다시 쓰기, 쥐기), 걸러내기, 가드, 펼치기 | 고를 레인(¼ 아래인지), 가드가 허락하는 회차 | +| 명령마다 결과의 꼴: 균일·아핀·레인 (값이 정하는 자리는 "아핀 또는 레인") | 그 꼴에서 고를 커널(꼴 × 폭) | + +## 설계 + +### 1단계: 블록의 사실을 로드 때 (`PureBatchPlan`) + +모듈을 읽을 때 `plan_folds`가 묶음 루프(`PLAN_BATCH`)를 정한 뒤 루프마다 계획 하나를 만든다. 계획은 모듈에 있고(루프의 `LOOP` +명령의 pc로 찾는다), 만든 뒤에는 읽기만 하므로 보기의 스레드들이 함께 쓴다. + +- 블록이 쓰는 지역 변수(비트 256개)와 항목을 쓰는지. `batch_run`의 훑기가 없어진다. +- 점화식: 갱신마다 (from, set, x)와 걸음 (op, a, c). 걸음의 피연산자는 "자리"로 적는다: 상수(값까지 로드 때), 필드, LOAD, 블록이 + 쓰지 않는 지역 변수, 루프 변수, x, 앞 걸음. 묶음을 열 때는 자리에 값만 채운다. `recur`의 `actions[]`도 계획에 있다. 점화식의 + 다른 읽기(기록)의 pc와 함께 쓰는 짝도. +- 칸에 더하기: (again, add, set, 리스트, 필드). +- **블록의 pc마다 몫 한 바이트**: 보통, 칸에 더하기의 again·add·set, 점화식의 from, 기록, 같은 코드의 값(다시 쓰기·쥐기), 모으기의 + 앞(`pure_batch_reduces`의 답은 따로 pc 하나). `pass`는 선형 찾기 넷 대신 이 바이트 하나를 본다. +- 작은 손질: `whole`이 `floor`를 부르지 않게(같은 뜻을 정수 변환으로), 걸러내기 버퍼는 쓴 묶음만 놓는다. + +묶음마다 남는 일: 값 채우기, 버퍼와 마스크, 미룬 효과, 검사. 메모리는 루프마다 블록 길이의 바이트와 점화식 걸음(최대 96개) 등 +수 KB 아래다. + +**맞음.** 1단계는 같은 사실을 다른 때 셈할 뿐이다. 만드는 동안 시험 빌드에서 묶음을 열 때 옛 셈을 함께 하고 계획과 견줘 다르면 +멈추게 한다(`PURE_BATCH_CHECK`). 무작위 시험과 고정 소스가 이 견줌을 다 지나면 옛 셈을 지운다. 두 길을 남기지 않는다. + +### 2단계: 값의 꼴을 로드 때, 리스트의 사실은 묶음에 한 번 + +- **정적 꼴.** 블록의 pc마다 결과가 균일·아핀·레인 가운데 무엇인지 로드 때 셈한다. 루프 변수는 아핀, 블록이 쓰지 않는 지역 + 변수와 LOAD·필드·상수는 균일, 균일과 아핀의 더하기·빼기는 아핀, 양수 균일과 아핀의 곱은 아핀(부호는 값이라 묶음을 열 때 + 확인하고, 아니면 지금처럼 레인), 레인에서 읽은 것은 레인. 지금 `pass`가 묶음마다 하는 꼴의 셈과 같은 규칙이다. +- **균일과 아핀의 조각은 스칼라 걸음으로.** 키의 셈(`c - it.weight`, `i * go.n + k`)처럼 균일과 아핀만으로 된 조각을 점화식의 + 걸음처럼 스칼라 목록으로 만들어 묶음마다 한 번 돈다. 명령마다 `Val`을 만들고 꼴을 묻는 일이 없어진다. +- **리스트의 사실은 묶음에 한 번.** 칸의 자리와 폭, DENSE인지, 개수, 키의 첫 행은 묶음을 열 때 리스트마다 한 번 가져온다. 읽기의 + 기록(`read_of`, 의존 검사에 쓰는 것)도 계획에 자리가 있다. +- **커널은 묶음을 열 때 고른다.** 레인 연산은 지금의 커널을 쓰되, 어느 것인지는 (정적 꼴 × 그 묶음의 폭)으로 정한다. 4바이트 + 커널이 넘침을 알리면 지금처럼 8바이트로 다시 한다. +- **버퍼.** 값마다의 버퍼 자리를 로드 때 정해 `fresh`·`release`·`sweep`이 빈 버퍼를 찾지 않게 한다. 고르기와 같은 코드의 값이 + 버퍼를 쥐는 규칙과 맞물리므로 1단계를 잰 뒤에 정한다. + +### 3단계: 꼴과 폭에 맞춘 커널 + +표가 아니라 연산 하나하나의 타입 변형이다. + +- **4바이트 곱하기.** `words_op`에 곱하기(64비트 곱으로 넘침 검사). matmul의 곱과 더하기가 4바이트 레인에 머문다. +- **모으기.** 균일한 e를 모든 레인에서 더하면 `result += e × n`(e가 정수이고 크기가 2^53 아래일 때. 아니면 지금처럼 레인마다). + 4바이트 레인의 e는 64비트 정수로 더한다(크기 검사 없이 정확). +- **좁은 열.** 1·2바이트 열을 4바이트 레인으로 바로 읽는다(8바이트로 거치지 않는다). +- 점화식은 차례가 있는 사슬이라 그대로 둔다. + +### 4단계: 훑기의 수 + +- **보폭 읽기를 피연산자로.** 열(시작, 보폭, 폭)을 값의 꼴 하나로 두고, 그것을 받는 연산이 열에서 바로 읽는다. 레인 배열로 + 옮기는 훑기가 없어진다. +- **비교가 레인을 센다.** 가르기 앞의 비교가 가는 레인의 수를 같은 루프에서 센다(`branch`의 세는 훑기가 없어진다). +- 배낭은 훑기 6에서 3이다(더하기, 비교와 세기, 마스크 쓰기). 컴파일러가 합친 2(1.87 ms, `042-tiles`)는 천장으로 둔다. + +### 5단계: 꼬리 (132의 E) + +- 걸러내기 후보의 꼬리(후보당 약 250 명령: 기록 50, 결정 90, 넣기 110)를 리스트 쪽에서 한 번에 한다(폭 검사 한 번, 비트와 칸을 함께). +- 칸에 더하기의 꼬리(join): 열의 폭을 묶음에 한 번 정하고 회차마다의 폭 가르기를 뺀다. + +## 하지 않는 것 + +- 합친 연산의 표(사용자, 2026-10-08), 레지스터 타일(133: 모으기가 있는 몸체에서 진다), 기계어. +- **레인 늘리기.** 묶음마다의 값을 레인 수로 나누는 쉬운 길이지만, 레인 버퍼가 스레드마다 24 × 1,048 × 8 B = 201 KB이고 4096이면 + 805 KB다. 메모리를 적게 쓰는 Pure의 생각과 맞지 않고, 묶음마다의 값을 없애면 필요 없다. + +## 막대 + +단계마다 같은 방법으로 잰다(`041-batches/runs.sh`, 11번의 중앙값, 세 길과 명령 수). 묶음마다의 값은 레인 1024와 256 빌드의 차로 잰다. +막대는 위의 몫에서 셈한 것이다. + +| 일 | 지금 (`b9`) | 1단계 | 2단계 | 3–4단계 | 5단계 | 천장 (041) | 기계어 | C | +|---|---:|---:|---:|---:|---:|---:|---:|---:| +| knapsack | 11.5 ms | ≤ 10.3 | ≤ 8.0 | ≤ 6.0 | | 4.55 (꽉 짠 두 훑기 1.87) | 7.9 | 6.25 | +| matmul | 40.0 | ≤ 39 | ≤ 30 | ≤ 17.75 | | 17.75 | 14.2 | 7.6 | +| BFS | 24.0 | ≤ 24 | ≤ 22 | ≤ 21 | ≤ 18 | 10.3 (꽉 짠 9.8) | 7.7 | 9.9 | +| roots | 8.97 | ≤ 9.0 | ≤ 8.6 | | | 6.8 | 9.57 | 6.86 | +| join | 117 | ≤ 116 | ≤ 115 | | ≤ 110 | 57.8 | 84.6 | 31.7 | +| 묶음마다 (배낭) | 0.90 µs | ≤ 0.60 | ≤ 0.15 | | | | | | +| 묶음마다 (sum0, `icount`) | 2,330 명령 | ≤ 1,550 | ≤ 600 | | | | | | + +- **knapsack.** 1단계는 블록 다시 읽기(묶음마다의 3분의 1 남짓, 약 1.5 ms)를 없애 약 10.0 ms다. 2단계는 묶음마다를 0.15 µs(0.7 ms)로 해서 + 11.5 − 4.4 + 0.7 = 7.8 ms다. 4단계의 훑기 셋은 요소마다 약 6 ms를 약 3.5로 줄여 약 5.3 ms다. 막대는 그보다 조금 느슨하다. + 131에서 생긴 10%(b7 10.32)는 1단계에서 되찾는다. +- **matmul.** 안쪽 회차마다의 디스패치 약 13 ms 가운데 1단계는 찾기(`pass`의 몫 일부)만, 2단계가 꼴과 리스트의 사실을 없애 약 + 3 ms로 한다(≤ 30). 3단계는 곱과 더하기를 4바이트로 해서 연산 약 22 ms를 약 9 ms로 한다(요소 8M × 약 2.5 사이클). 막대는 041의 + 천장이다. +- **BFS.** 간선당 112 명령에서 노드마다 20을 약 10으로(1–2단계), 비교와 세기를 합쳐 약 5를(4단계), 후보의 26을 약 10으로(5단계) + 줄이면 약 80 명령, 약 17 ms다. +- **roots, join**은 묶음마다의 몫(0.6, 3 ms)과 join의 칸 꼬리(약 12 ms의 절반)만큼이다. join의 점화식(약 23 ms)은 그대로다. +- **지키는 것.** 묶음 루프가 없는 모듈의 실행기는 명령 수가 그대로(`rounds` 길), TPC-C와 은행 질의는 기준(3%, 1%) 안. + +## 맞음과 단계마다의 시험 + +단계마다 같은 묶음을 돈다: 무작위 프로그램 시드 1, 2, 3, 5, 23(기본과 `PURE_SELECT=all`), 고정 소스 여섯(`BATCH`, `NESTED`, +`RECUR`, `APPEND`, `FRONT`, `GRAPH`)의 세 길, 단위 시험 세 모드와 ASan, sanitized `pure-run`, aup의 검사 두 모드, `make check`, +스위트의 세 길과 명령 수. 1단계는 `PURE_BATCH_CHECK`의 견줌을 더한다. 2단계는 정적 꼴이 지금의 동적 꼴과 같은지를 같은 방법으로 +견준다(시험 빌드에서 둘 다 셈하고, 다르면 멈춘다). 견줌은 단계가 끝나면 지운다. + +## 단계의 차례 + +1단계는 뜻을 바꾸지 않고 묶음마다의 3분의 1을 없앤다. 2단계가 이 설계의 몸통이고, 1단계의 계획 위에 선다. 3–4단계는 커널과 +값의 꼴을 늘리는 일이라 2단계의 정적 꼴이 있어야 깔끔하다. 5단계는 독립이라 언제든 할 수 있다. 1단계를 잰 뒤 2단계의 버퍼와 +조각의 자리를 다시 정하고, 이 문서에 적는다. diff --git a/research/experiments/041-batches/2026-10-08-batch-costs.jsonl b/research/experiments/041-batches/2026-10-08-batch-costs.jsonl new file mode 100644 index 0000000..b3eba50 --- /dev/null +++ b/research/experiments/041-batches/2026-10-08-batch-costs.jsonl @@ -0,0 +1,85 @@ +{"note": "b9 core (735ba81), suite-run knapsack, PURE_JIT=0, BATCH 1024 and 256 builds (gcc -O2 -g, module-batch -O3), a 2 kHz sampled profile, ms a round by the in-process C's samples (6.24 ms); measured times 11.49 and 24.56 ms; batches a round about 4,900 and 19,400", "pure_ms": [11.49, 24.56]} +{"work": "knapsack", "function": "pass.constprop.0", "ms_1024": 1.644, "ms_256": 6.167} +{"work": "knapsack", "function": "batch_run", "ms_1024": 1.999, "ms_256": 6.003} +{"work": "knapsack", "function": "binary.constprop.0", "ms_1024": 3.751, "ms_256": 4.882} +{"work": "knapsack", "function": "rows_in.constprop.0", "ms_1024": 0.149, "ms_256": 0.728} +{"work": "knapsack", "function": "find.constprop.0", "ms_1024": 0.231, "ms_256": 0.806} +{"work": "knapsack", "function": "pure_list_cells", "ms_1024": 0.143, "ms_256": 0.687} +{"work": "knapsack", "function": "affine_of.constprop.0", "ms_1024": 0.141, "ms_256": 0.63} +{"work": "knapsack", "function": "read_of.part.0.constprop.0", "ms_1024": 0.109, "ms_256": 0.516} +{"work": "knapsack", "function": "branch.constprop.0", "ms_1024": 0.96, "ms_256": 1.291} +{"work": "knapsack", "function": "pure_batch_run", "ms_1024": 0.025, "ms_256": 0.326} +{"work": "knapsack", "function": "_init", "ms_1024": 0.026, "ms_256": 0.268} +{"work": "knapsack", "function": "cells_at.constprop.0", "ms_1024": 0.163, "ms_256": 0.332} +{"work": "knapsack", "function": "dense_keys", "ms_1024": 0.042, "ms_256": 0.192} +{"work": "knapsack", "function": "(other)", "ms_1024": 1.21, "ms_256": 1.343} +{"work": "knapsack", "function": "batches.constprop.0", "ms_1024": 0.039, "ms_256": 0.13} +{"work": "knapsack", "function": "pure_list_add_many", "ms_1024": 0.486, "ms_256": 0.562} +{"work": "knapsack", "function": "pure_list_takes", "ms_1024": 0.209, "ms_256": 0.249} +{"work": "knapsack", "function": "pure_list_get", "ms_1024": 0.121, "ms_256": 0.156} +{"work": "knapsack", "function": "pure_list_count", "ms_1024": 0.023, "ms_256": 0.05} +{"work": "knapsack", "function": "rounds_of.constprop.0", "ms_1024": 0.084, "ms_256": 0.102} +{"work": "knapsack", "function": "c_knapsack", "ms_1024": 6.24, "ms_256": 6.24} +{"work": "knapsack", "function": "widen", "ms_1024": 0.105, "ms_256": 0.045} +{"work": "knapsack", "line": "module-batch.c:1761", "ms_1024": 0.189, "ms_256": 0.688} +{"work": "knapsack", "line": "module-batch.c:1590", "ms_1024": 0.161, "ms_256": 0.653} +{"work": "knapsack", "line": "module-batch.c:189", "ms_1024": 0.138, "ms_256": 0.621} +{"work": "knapsack", "line": "module-batch.c:1087", "ms_1024": 0.164, "ms_256": 0.624} +{"work": "knapsack", "line": "module-batch.c:589", "ms_1024": 0.108, "ms_256": 0.519} +{"work": "knapsack", "line": "module-batch.c:1747", "ms_1024": 0.166, "ms_256": 0.501} +{"work": "knapsack", "line": "module-batch.c:1481", "ms_1024": 0.108, "ms_256": 0.408} +{"work": "knapsack", "line": "module-batch.c:468", "ms_1024": 0.074, "ms_256": 0.373} +{"work": "knapsack", "line": "module-batch.c:190", "ms_1024": 0.039, "ms_256": 0.308} +{"work": "knapsack", "line": "module-batch.c:2735", "ms_1024": 0.006, "ms_256": 0.27} +{"work": "knapsack", "line": "module-batch.c:695", "ms_1024": 0.086, "ms_256": 0.349} +{"work": "knapsack", "line": "module-batch.c:1440", "ms_1024": 0.075, "ms_256": 0.336} +{"work": "knapsack", "line": "module-batch.c:460", "ms_1024": 0.039, "ms_256": 0.291} +{"work": "knapsack", "line": "module-batch.c:1742", "ms_1024": 0.061, "ms_256": 0.306} +{"work": "knapsack", "line": "??:0", "ms_1024": 0.026, "ms_256": 0.268} +{"work": "knapsack", "line": "module-batch.c:2780", "ms_1024": 0.094, "ms_256": 0.318} +{"work": "knapsack", "line": "module-batch.c:1911", "ms_1024": 0.059, "ms_256": 0.281} +{"work": "knapsack", "line": "module-batch.c:880", "ms_1024": 0.034, "ms_256": 0.246} +{"work": "knapsack", "line": "module-batch.c:1480", "ms_1024": 0.056, "ms_256": 0.261} +{"work": "knapsack", "line": "module-batch.c:1812", "ms_1024": 0.05, "ms_256": 0.255} +{"work": "knapsack", "line": "module-batch.c:679", "ms_1024": 0.04, "ms_256": 0.233} +{"work": "knapsack", "line": "module-batch.c:1767", "ms_1024": 0.052, "ms_256": 0.238} +{"work": "knapsack", "line": "module-batch.c:491", "ms_1024": 0.037, "ms_256": 0.22} +{"work": "knapsack", "line": "module-batch.c:1589", "ms_1024": 0.064, "ms_256": 0.242} +{"work": "knapsack", "line": "module-batch.c:1834", "ms_1024": 0.056, "ms_256": 0.229} +{"work": "knapsack", "line": "module-batch.c:774", "ms_1024": 0.064, "ms_256": 0.235} +{"work": "knapsack", "line": "natural.h:39", "ms_1024": 4.021, "ms_256": 4.164} +{"work": "knapsack", "line": "module-batch.c:1439", "ms_1024": 0.036, "ms_256": 0.173} +{"work": "knapsack", "line": "module-batch.c:1437", "ms_1024": 0.053, "ms_256": 0.188} +{"work": "knapsack", "line": "module-batch.c:355", "ms_1024": 0.005, "ms_256": 0.14} +{"work": "knapsack", "line": "module-batch.c:617", "ms_1024": 0.058, "ms_256": 0.188} +{"work": "knapsack", "line": "module-batch.c:1751", "ms_1024": 0.031, "ms_256": 0.159} +{"work": "knapsack", "line": "module-list.c:1029", "ms_1024": 0.025, "ms_256": 0.153} +{"work": "knapsack", "line": "module-batch.c:720", "ms_1024": 0.023, "ms_256": 0.149} +{"work": "knapsack", "line": "module-batch.c:864", "ms_1024": 0.024, "ms_256": 0.15} +{"work": "knapsack", "line": "module-batch.c:680", "ms_1024": 0.039, "ms_256": 0.163} +{"work": "knapsack", "line": "module-batch.c:1147", "ms_1024": 0.038, "ms_256": 0.158} +{"work": "knapsack", "line": "module-batch.c:1014", "ms_1024": 0.024, "ms_256": 0.141} +{"work": "knapsack", "line": "module-list.c:1808", "ms_1024": 0.035, "ms_256": 0.152} +{"work": "knapsack", "line": "module-batch.c:1484", "ms_1024": 0.04, "ms_256": 0.156} +{"work": "knapsack", "line": "module-batch.c:328", "ms_1024": 0.008, "ms_256": 0.121} +{"work": "knapsack", "line": "module-batch.c:2206", "ms_1024": 0.048, "ms_256": 0.16} +{"work": "knapsack", "line": "module-batch.c:2782", "ms_1024": 0.049, "ms_256": 0.16} +{"work": "knapsack", "line": "module-batch.c:1478", "ms_1024": 0.034, "ms_256": 0.145} +{"work": "knapsack", "line": "module-batch.c:1723", "ms_1024": 0.088, "ms_256": 0.199} +{"work": "knapsack", "line": "module-batch.c:1438", "ms_1024": 0.041, "ms_256": 0.148} +{"work": "knapsack", "line": "module-list.c:1714", "ms_1024": 0.02, "ms_256": 0.119} +{"work": "knapsack", "line": "module-list.c:1807", "ms_1024": 0.014, "ms_256": 0.109} +{"work": "knapsack", "line": "module-batch.c:497", "ms_1024": 0.007, "ms_256": 0.101} +{"work": "knapsack", "line": "module-batch.c:1588", "ms_1024": 0.018, "ms_256": 0.107} +{"work": "knapsack", "line": "module-batch.c:1120", "ms_1024": 0.009, "ms_256": 0.096} +{"work": "knapsack", "line": "module-batch.c:1757", "ms_1024": 0.036, "ms_256": 0.124} +{"work": "knapsack", "line": "module-batch.c:2871", "ms_1024": 0.013, "ms_256": 0.098} +{"work": "knapsack", "line": "module-batch.c:209", "ms_1024": 0.045, "ms_256": 0.127} +{"work": "knapsack", "line": "module-batch.c:2783", "ms_1024": 0.02, "ms_256": 0.1} +{"work": "knapsack", "line": "module-batch.c:1492", "ms_1024": 0.025, "ms_256": 0.104} +{"work": "knapsack", "line": "module-batch.c:845", "ms_1024": 0.039, "ms_256": 0.115} +{"work": "knapsack", "line": "module-batch.c:1075", "ms_1024": 0.048, "ms_256": 0.121} +{"work": "knapsack", "line": "module-batch.c:1101", "ms_1024": 0.038, "ms_256": 0.106} +{"work": "knapsack", "line": "module-batch.c:1715", "ms_1024": 0.042, "ms_256": 0.103} +{"note":"time.c sum0 n=200000 (4M rounds), 21 rounds median, b9 BATCH 1024 then 256","module":"sum0.pmod","n":200000,"ms":8.633,"work":44000019,"out":4000000} +{"note":"time.c sum0 n=200000 (4M rounds), 21 rounds median, b9 BATCH 1024 then 256","module":"sum0.pmod","n":200000,"ms":12.544,"work":44000019,"out":4000000} diff --git a/research/experiments/041-batches/runs.sh b/research/experiments/041-batches/runs.sh index 6f3a4e8..876f249 100755 --- a/research/experiments/041-batches/runs.sh +++ b/research/experiments/041-batches/runs.sh @@ -47,4 +47,8 @@ esac # 2026-10-08-lanes.jsonl (research 132): b9's code with BATCH 1024, 512 and # 256 (core/module-batch.c's enum), suite-run 5 rounds twice (ms: the two # medians) and costs/time.c's sum0, ops0 and nest under icount 3 rounds: -# a batch's fixed cost is (the instructions' difference) / (the batches'). +# a batch's fixed cost is (the instructions' difference) / (the batches'), +# icount's 3 rounds counted: 3,000 and 12,000 batches for sum0 and ops0. +# 2026-10-08-batch-costs.jsonl (design 025): knapsack's time a round by +# function and line, b9's code at BATCH 1024 and 256 under a 2 kHz sampled +# profile (ms by the in-process C's samples); sum0's times at both. -- cgit v1.2.3