diff options
| -rw-r--r-- | CHECKPOINT.md | 2 | ||||
| -rw-r--r-- | docs/design/024-batch-executor.md | 2 | ||||
| -rw-r--r-- | docs/research/132-batch-executor-floor-and-the-way-past.md | 8 | ||||
| -rw-r--r-- | docs/research/133-register-tiles-measured.md | 82 |
4 files changed, 91 insertions, 3 deletions
diff --git a/CHECKPOINT.md b/CHECKPOINT.md index 6d3759a..d60a126 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). 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) | +| 수명과 계산 | 값의 수명은 선언이 말한다: `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) | | 보기 밀기 | 보기의 `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 2ed21f5..26a4fb7 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배로 보인다. +작성일: 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)): 꼴은 옳고, 묶음 프로그램을 로드 때 한 번 만들고 루프를 타입·폭·보폭으로 꽉 짜는 것이 길이다. [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/132-batch-executor-floor-and-the-way-past.md b/docs/research/132-batch-executor-floor-and-the-way-past.md index c526f05..dafb7d8 100644 --- a/docs/research/132-batch-executor-floor-and-the-way-past.md +++ b/docs/research/132-batch-executor-floor-and-the-way-past.md @@ -151,7 +151,13 @@ A와 E를 만들고 기계어를 남긴다.** 반나절이다. 결과가 기준을 넘으면 B의 설계(025)를 쓰고, 넘지 못하면 그 수를 적고 A와 E로 간다. -## 추천 +## 결과 (2026-10-08, [133](133-register-tiles-measured.md)) + +실험을 돌렸다. roots는 기계어의 0.71배로 기준을 넘었고, 배낭은 4배, BFS는 2.4배로 넘지 못했다(NEON에 모아 읽기가 없어 레인마다 +꺼내고 넣는 값). 같은 실험에서 지금의 꼴(연산마다 훑기)을 꽉 짜면 BFS가 기계어의 1.2배, 배낭이 0.4배였다. 그래서 B는 접고 A를 +끝까지 간다: 꼴이 아니라 구현이 3배였다. + +## 추천 (실험 전에 적은 것) A는 어느 길에서나 필요하고 범용이므로 먼저 만들어도 된다. B는 실험 뒤에 정한다. 지금 가진 수로 보면 B가 유일한 근본적인 길이고, 문헌(Gubner & Boncz의 레지스터 집계, Sompolski의 "벽돌")은 값을 레지스터에 두는 것이 벡터 해석의 남은 길이라는 데 모인다. diff --git a/docs/research/133-register-tiles-measured.md b/docs/research/133-register-tiles-measured.md new file mode 100644 index 0000000..de478da --- /dev/null +++ b/docs/research/133-register-tiles-measured.md @@ -0,0 +1,82 @@ +# 133 — 레지스터 타일을 재다: 산수에는 이기고 모으기에는 지며, 훑기의 꼴은 옳았다 + +2026-10-08. [132](132-batch-executor-floor-and-the-way-past.md)가 정한 실험. 런타임은 건드리지 않고 +`research/experiments/042-tiles/`의 C 시제품으로 세 몸체(배낭의 안쪽, BFS의 프런티어, roots의 뉴턴)를 레지스터 타일로 돌려 +요소당 사이클을 기계어와 견줬다. 기준은 "셋 모두 기계어의 1.3배 안". 결과는 **roots는 0.71배로 넘고, 배낭은 4배, BFS는 2.4배로 +못 넘는다.** 같은 실험이 덤으로 보인 것이 더 중요하다. **지금의 꼴(연산마다 레인을 훑기)을 꽉 짜면 BFS가 기계어의 1.2배, 배낭은 +0.4배다.** 묶음 실행기의 3배는 꼴의 값이 아니라 구현의 값이다. + +## 쉬운 말로 + +- **레지스터 타일은 범용의 답이 아니다.** 값을 NEON 레지스터에 두면 산수의 사슬(roots)은 C보다 빨라진다. 그러나 레인마다 다른 + 자리를 읽고 쓰는 일(배낭의 표, BFS의 `to`와 비트)은 레인 하나씩 꺼내고 넣어야 한다. 이 기기(Cortex-A76)의 NEON에는 모아 + 읽기(gather)가 없다. 그래서 모으기가 있는 몸체는 레지스터를 거치는 것이 메모리의 배열을 스칼라로 훑는 것보다 느리다. +- **그 자리에서 잰 "꽉 짠 훑기"가 기계어에 닿았다.** BFS의 프런티어를 훑기 셋(`to` 모으기, 비트 묻기, 후보 고르기)과 꼬리로 돌리면 + 9.8 ms다. 기계어 7.7, C 8.6, 지금의 묶음 실행기 24.0이다. 배낭을 4바이트 레인과 보폭 읽기의 훑기 둘로 돌리면 2.9 ms다(clang). + 기계어 7.9, C 6.2, 묶음 실행기 11.4다. +- **그러니 근본적인 길은 꼴을 바꾸는 것이 아니라 꼴을 끝까지 짜는 것이다.** 묶음 프로그램을 로드 때 한 번 만들어 묶음마다의 + 고정 값을 없애고, 레인의 타입과 폭과 보폭이 정해진 꽉 짠 루프를 묶음마다 고르고, 검사를 요소에서 묶음으로 올린다. 132의 + A다. 레지스터 타일은 산수의 사슬에만 쓸 수 있는 선택지로 남긴다. + +## 시제품 + +- **첫 꼴**(`make.py`): 함수 하나 안의 계산된 goto. 슬롯 여섯(벡터 변수)에 깊이마다 레이블. GCC가 레이블 사이에서 슬롯을 모두 + 스택에 내렸다(`ldp q.. [sp]`, `stp`). 연산마다 적재·저장이 돌아와 훑기보다 느렸다(배낭 43 ms, roots 11.6, BFS 15.6). 간접 + 분기 뒤에서 레지스터를 지키지 않는 컴파일러의 값이다. +- **둘째 꼴**(`make2.py`): 연산마다 함수, 슬롯은 인자(동질 벡터 집합: AAPCS64가 v0–v7에 넘긴다), 다음 연산으로 꼬리 호출 + (clang `musttail`, GCC 형제 호출). 연산이 벡터 명령 몇 개, 다음 주소 적재, 분기로 끝난다(`fadd, fadd, ldr, br`). 슬롯 넷에 + 레지스터 둘씩(레인 4, `2 4`), 또는 슬롯 여덟에 하나씩(레인 2, `1 8`). 연산은 슬롯을 이름으로 부르는 3주소 꼴이라 (연산, 슬롯들) + 마다 함수를 만든다(프로그램이 쓰는 것만). +- 몸체 셋은 Pure의 뜻 그대로다(수는 double, 레인마다의 결함 검사는 뺐다). 답을 C와 견줘 같았다. + +## 잰 것 + +Pi 5, 3번 중 가장 짧은 것. 기계어는 스위트의 수다(배낭 7.9 ms, roots 9.57, BFS 7.7). + +| 몸체 | 타일 (레인 4, clang) | 타일 (레인 4, gcc) | 타일 (레인 2) | 꽉 짠 훑기 | C | 기계어 | 묶음 실행기 | +|---|---:|---:|---:|---:|---:|---:|---:| +| roots | **5.8 ms** | 6.7 | 9.7 | — | 6.9 | 9.57 | 8.97 | +| knapsack | 29.4 | 41.6 | 35.8 | **2.9** (gcc 9.6) | 6.2 | 7.9 | 11.4 | +| BFS | 18.1 | 23.7 | 19.6 | **9.8** | 8.6 | 7.7 | 24.0 | + +요소당(명령/사이클, `icount`, 11번과 1번의 차): + +| 몸체 | 타일 (레인 4, clang) | 기계어 | 묶음 실행기 | +|---|---:|---:|---:| +| roots, 뉴턴 걸음 하나 | — / 13 | — / 18.6 | — / 17.4 | +| knapsack, 회차 하나 | 35 / 15 | 8 / 3.8 | — / 5.7 | +| BFS, 간선 하나 | — / 47 | 38.5 / 19 | 112 / 57 | + +- **roots가 이기는 이유.** 레인 넷의 나눗셈 사슬이 레지스터 둘에서 함께 돌아 나눗셈의 지연을 겹친다. C는 사슬 하나씩이다. + 디스패치는 걸음마다 10번, 4레인이라 걸음당 2.5번이고 한 번이 명령 4개다. +- **배낭이 지는 이유.** `GATHER4` 하나가 레인 넷에 명령 18개다. 벡터에서 꺼내(`fmov`, `mov`), 정수로 바꾸고(`fcvtzu`), 읽고, + 다시 넣는다(`ucvtf`, `mov v.d[1]`). 회차마다 모으기 둘과 마스크 쓰기 하나라 회차당 35개다. 기계어는 스칼라 8개다. +- **BFS가 지는 이유.** 같다. `to` 모으기, 비트 묻기, 후보 고르기가 레인마다 꺼내고 넣는다. 꽉 짠 훑기 셋은 스칼라 루프라 컴파일러가 + 잘 짜고, 간선당 약 23 사이클이다(기계어 19). +- **꽉 짠 훑기가 배낭에서 C를 이기는 이유.** 4바이트 레인을 보폭 −1로 읽어 더하는 훑기 하나, 읽어 견줘 큰 쪽을 쓰는 훑기 하나. + clang이 둘 다 벡터로 짠다(gcc는 거꾸로 가는 색인을 벡터로 짜지 못해 9.6 ms: 묶음 실행기가 레인을 거꾸로 번호 매기는 까닭이 + 여기 있다). 묶음 실행기는 같은 회차를 훑기 여섯으로 하고 묶음마다 6,500 명령을 더 내서 5.7 사이클이다. + +## 뜻 + +1. **꼴은 옳다.** 연산마다 레인을 훑는 묶음 실행기의 꼴은 이 기기에서 모으기가 있는 몸체에 가장 알맞다. 레지스터 타일은 산수의 + 사슬에만 낫다(roots). 그러나 roots는 묶음 실행기도 이미 기계어보다 빠르다. 타일을 두 번째 기계로 더할 까닭이 지금은 없다. +2. **3배는 구현이다.** 같은 훑기라도 범용 루프(값의 꼴을 레인마다 묻고, 범위를 레인마다 보고, 8바이트로 넓히고, 마스크를 따로 + 만드는)와 꽉 짠 루프(타입·폭·보폭이 정해진)의 차가 2–4배다. 그 위에 묶음마다의 고정 값(6,500 명령)과 훑기의 수(배낭 6 대 2, + BFS 10여 대 3)가 얹힌다. +3. **합치기 없이 어디까지.** 꽉 짠 훑기의 배낭 2.9 ms는 컴파일러가 연산 둘셋을 훑기 하나에 합친 값이다. 합치지 않으면 훑기 여섯에 + 회차당 약 5–6 사이클로 기계어의 1.5배다. BFS는 훑기 셋이 이미 연산 셋이라 1.2배다. 범용의 길로는 "기계어의 1.2–1.5배"가 + 배낭과 BFS의 바닥이고, roots처럼 사슬이 있는 일은 기계어 아래다. + +## 다음: 132의 A를 끝까지 + +- **묶음 프로그램을 로드 때 한 번.** 블록을 묶음마다 다시 읽지 않는다. 명령마다 피연산자의 꼴(균일·아핀·레인)과 폭, 읽기의 보폭, + 쓰기의 마스크, 미룬 효과의 차례, 검사(2^53, 범위, 유한)의 자리를 정해 둔다. 묶음을 열 때는 그 프로그램대로 꽉 짠 루프를 고른다. +- **꽉 짠 루프.** 타입과 폭과 보폭이 정해진 루프를 빌드 때 C로 둔다(표가 아니라 연산 하나하나의 타입 변형이다). 범위 검사는 레인의 + 최소·최대로 묶음에 한 번. 거꾸로 가는 읽기는 레인의 번호를 거꾸로 매겨 메모리의 차례로(이미 한다). +- **훑기의 수.** 즉시 피연산자(`ADDK`), 보폭 읽기를 피연산자로(열에서 바로), 비교를 마스크로 바로 쓰기(이미 한다), 고르기(이미 + 한다). 합친 연산의 표는 두지 않는다. +- **후보의 꼬리**(132의 E)는 그대로 유효하다. +- **레지스터 타일**은 접어 둔다. 산수의 사슬이 긴 일이 기계어보다 느려지면 그때 꺼낸다. + +측정의 원본은 `042-tiles/2026-10-08-tiles.jsonl`이다(`make.py`와 `make2.py`로 다시 만들 수 있다). |