From 3e3f008b942106cedb59ebca760376274c2fcb84 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Thu, 8 Oct 2026 14:36:27 +0100 Subject: Research 132 and 133 corrected: the per-batch cost was icount's three rounds over one round's batches, 3x too high; about 2,300 instructions (0.33 us) in a small block, 0.90 us in knapsack's (38% of its time, not 20%) --- .../132-batch-executor-floor-and-the-way-past.md | 20 ++++++++++++-------- docs/research/133-register-tiles-measured.md | 4 ++-- 2 files changed, 14 insertions(+), 10 deletions(-) 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 dafb7d8..fb31176 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 @@ -9,7 +9,7 @@ - **문제는 "연산마다 레인을 한 번 훑는 꼴" 자체다.** 묶음 실행기는 명령 하나를 레인 1024개에 한 번에 하고, 그 결과를 메모리의 레인 배열에 쓴다. 다음 명령이 그것을 다시 읽는다. 기계어(JIT)는 같은 값을 레지스터에 두고 다음 연산으로 넘긴다. 요소당 명령이 묶음은 4–12개, 기계어는 1–2개다. 이것은 구현의 흠이 아니라 꼴의 값이고, 데이터베이스 쪽 문헌이 같은 수를 잰다(아래). -- **비용의 자리는 셋이다.** 요소마다(레인 훑기), 묶음마다(묶음을 열 때마다 블록을 다시 읽고 꼴을 정하는 값, 약 6,500 명령), +- **비용의 자리는 셋이다.** 요소마다(레인 훑기), 묶음마다(묶음을 열 때마다 블록을 다시 읽고 꼴을 정하는 값, 작은 블록에서 약 2,200 명령, 배낭의 블록에서 약 0.9 µs), 후보마다(걸러내기 뒤 차례대로 하는 꼬리, 약 250 명령). 셋 가운데 범용으로 거의 다 없앨 수 있는 것이 둘째다. 셋째는 리스트 쪽 C라 줄일 수 있다. 첫째가 바닥이다. - **근본적인 길은 "레지스터 타일"이다.** 레인 1024개를 명령마다 훑는 대신, 레인 4–16개를 레지스터에 올려 두고 몸체의 명령을 그 @@ -31,17 +31,21 @@ BFS 간선당 112개 가운데 약 45개가 레인 훑기다(`to` 모으기 12, ### 묶음마다 -같은 몸체를 레인 1024개와 256개로 돌려 명령의 차를 묶음 수의 차로 나눴다(`costs/sum0`, `ops0`: 회차 1,024,000, 묶음 1,000과 -4,000). +같은 몸체를 레인 1024개와 256개로 돌려 명령의 차를 묶음 수의 차로 나눴다(`costs/sum0`, `ops0`: 메시지 하나에 회차 1,024,000, +`icount`가 세 번 돌아 묶음 3,000과 12,000). | 모듈 | 1024 레인 | 256 레인 | 묶음마다 | |---|---:|---:|---:| -| `sum0` (회차를 세는 합) | 4,789만 명령 / 1,621만 사이클 | 6,886만 / 2,345만 | **6,990 명령 / 2,410 사이클** | -| `ops0` (`let` 하나와 `max`) | 6,641만 / 3,036만 | 8,534만 / 3,683만 | 6,310 / 2,160 | +| `sum0` (회차를 세는 합) | 4,789만 명령 / 1,621만 사이클 | 6,886만 / 2,345만 | **2,330 명령 / 805 사이클** | +| `ops0` (`let` 하나와 `max`) | 6,641만 / 3,036만 | 8,534만 / 3,683만 | 2,100 / 720 | -묶음 하나를 여는 데 약 6,500 명령, 약 1 µs다. 블록을 다시 읽어 지역 변수의 꼴을 정하고(`batch_run`의 앞머리, `recurrences`, +(2026-10-08 고침: 처음에는 `icount`의 세 번을 한 번의 묶음 수(1,000과 4,000)로 나눠 6,990 / 2,410과 6,310 / 2,160, "약 +6,500 명령, 약 1 µs"로 적었다. 세 배였다. 시간으로 따로 재도 `sum0`은 묶음마다 0.34 µs다([025](../design/025-batch-programs.md)).) + +작은 블록의 묶음 하나를 여는 데 약 2,200 명령, 약 0.3 µs다. 블록이 크면 더 든다(배낭은 약 0.9 µs, 025). 블록을 다시 읽어 지역 변수의 꼴을 정하고(`batch_run`의 앞머리, `recurrences`, `sums`), 명령마다 값의 꼴(균일·아핀·레인)을 물어 가르고(`pass`), 끝에서 검사하고 쓴다(`settle`). 024는 처음부터 "묶음 프로그램은 -루프마다 한 번 만든다"고 했는데, 그 단계를 만들지 않았다. 배낭에서는 이 값이 시간의 약 20%다(`batch_run` 10.7%, `pass` 8.5%). +루프마다 한 번 만든다"고 했는데, 그 단계를 만들지 않았다. 배낭에서는 이 값이 시간의 약 38%다(아래 표의 1024와 256의 차를 셋으로 나눈 4.4 ms; 처음에는 표본의 `batch_run` 10.7%와 `pass` +8.5%로 약 20%라 적었지만, 묶음마다의 값은 다른 함수에도 흩어져 있다). **레인을 줄이면 느려진다.** 024는 레인 자리를 L1(64 KB) 안에 두려고 256 레인을 적었고, 1단계에서 디스패치 값을 나누려고 1024로 늘렸다. 지금 디스패치는 명령당 약 20 ns라 다시 256으로 줄여 봤다(`b9`의 코드, `BATCH`만 바꿈, 5번의 중앙값). @@ -103,7 +107,7 @@ C 컴파일러가 가는 곳 어디서나 같고, 메모리를 적게 쓴다"([0 ### A. 묶음 프로그램을 로드 때 한 번 (024의 못 만든 단계) 루프마다 로드 때 한 번, 명령마다 피연산자의 꼴과 폭, 묶음마다 할 검사, 미룬 효과의 차례를 정해 둔다. 묶음을 열 때는 그 프로그램을 -돈다. 둘째 자리(묶음마다 약 6,500 명령)가 거의 사라지고 `pass`의 꼴 묻기도 사라진다. 범용이고, 아래 B의 전제이기도 하다 +돈다. 둘째 자리(묶음마다 약 2,200 명령에서 배낭의 0.9 µs)가 거의 사라지고 `pass`의 꼴 묻기도 사라진다. 범용이고, 아래 B의 전제이기도 하다 (B도 프로그램이 있어야 한다). 바닥(첫째 자리)은 건드리지 않는다. ### B. 레지스터 타일 해석 (근본적인 길) diff --git a/docs/research/133-register-tiles-measured.md b/docs/research/133-register-tiles-measured.md index de478da..4496d64 100644 --- a/docs/research/133-register-tiles-measured.md +++ b/docs/research/133-register-tiles-measured.md @@ -55,14 +55,14 @@ Pi 5, 3번 중 가장 짧은 것. 기계어는 스위트의 수다(배낭 7.9 ms 잘 짜고, 간선당 약 23 사이클이다(기계어 19). - **꽉 짠 훑기가 배낭에서 C를 이기는 이유.** 4바이트 레인을 보폭 −1로 읽어 더하는 훑기 하나, 읽어 견줘 큰 쪽을 쓰는 훑기 하나. clang이 둘 다 벡터로 짠다(gcc는 거꾸로 가는 색인을 벡터로 짜지 못해 9.6 ms: 묶음 실행기가 레인을 거꾸로 번호 매기는 까닭이 - 여기 있다). 묶음 실행기는 같은 회차를 훑기 여섯으로 하고 묶음마다 6,500 명령을 더 내서 5.7 사이클이다. + 여기 있다). 묶음 실행기는 같은 회차를 훑기 여섯으로 하고 묶음마다 약 0.9 µs를 더 내서 5.7 사이클이다. ## 뜻 1. **꼴은 옳다.** 연산마다 레인을 훑는 묶음 실행기의 꼴은 이 기기에서 모으기가 있는 몸체에 가장 알맞다. 레지스터 타일은 산수의 사슬에만 낫다(roots). 그러나 roots는 묶음 실행기도 이미 기계어보다 빠르다. 타일을 두 번째 기계로 더할 까닭이 지금은 없다. 2. **3배는 구현이다.** 같은 훑기라도 범용 루프(값의 꼴을 레인마다 묻고, 범위를 레인마다 보고, 8바이트로 넓히고, 마스크를 따로 - 만드는)와 꽉 짠 루프(타입·폭·보폭이 정해진)의 차가 2–4배다. 그 위에 묶음마다의 고정 값(6,500 명령)과 훑기의 수(배낭 6 대 2, + 만드는)와 꽉 짠 루프(타입·폭·보폭이 정해진)의 차가 2–4배다. 그 위에 묶음마다의 고정 값(배낭에서 약 0.9 µs, 시간의 38%; 132를 고쳤다)과 훑기의 수(배낭 6 대 2, BFS 10여 대 3)가 얹힌다. 3. **합치기 없이 어디까지.** 꽉 짠 훑기의 배낭 2.9 ms는 컴파일러가 연산 둘셋을 훑기 하나에 합친 값이다. 합치지 않으면 훑기 여섯에 회차당 약 5–6 사이클로 기계어의 1.5배다. BFS는 훑기 셋이 이미 연산 셋이라 1.2배다. 범용의 길로는 "기계어의 1.2–1.5배"가 -- cgit v1.2.3