From be51c8a15d4f220ea8322f3c562f1f0c51b1e8e7 Mon Sep 17 00:00:00 2001
From: eunhhu <necpition205@gmail.com>
Date: Thu, 8 Oct 2026 16:53:29 +0100
Subject: Research 136: the batch executor's stage 3 (four-byte MUL, reductions
 with no lanes while every lane's e is the same, a list's cells once a batch):
 against b9, interleaved, matmul 40.01 to 25.97 ms, knapsack 11.47 to 10.07,
 roots 8.97 to 8.29, join 117.2 to 115.8, BFS and sort the same; sum0 8.69 to
 1.01 (bar 1.5); matmul short of its bar (21): the nested rounds'
 interpretation (about 14 ms) and the matrices' making (4-5) were left out of
 the arithmetic; the executor alone and the bank queries' instructions as b9
 (0.08%), TPC-C +0.7%; stage 4 next (knapsack's six passes to three)

---
 docs/design/025-batch-programs.md               |  5 +-
 docs/research/136-batch-executor-stage-three.md | 65 +++++++++++++++++++++++++
 2 files changed, 69 insertions(+), 1 deletion(-)
 create mode 100644 docs/research/136-batch-executor-stage-three.md

(limited to 'docs')

diff --git a/docs/design/025-batch-programs.md b/docs/design/025-batch-programs.md
index d7f9fd3..c3123b7 100644
--- a/docs/design/025-batch-programs.md
+++ b/docs/design/025-batch-programs.md
@@ -6,7 +6,10 @@
 10.51 ms(놓인 자리); 막대 ≤ 9.2 ms, ≤ 0.45 µs, ≤ 33 ms에 못 미쳤다. 조각은 중첩 회차의 수단이고, 묶음마다 값은 키로 찾기와 레인
 연산의 준비에 있어 이 꼴로는 약 0.6 µs에서 멈춘다. 리스트의 칸 캐시는 3%라 하지 않았다). 다음은 요소마다다(3단계: 4바이트 곱하기,
 matmul ≤ 21 ms). 4바이트 곱하기 뒤 matmul은 26.57 ms다(명령 −20%). 막대의 셈은 "실수 연산 22 ms 밖은 14 ms 그대로"였는데, 그 밖은
-안쪽 회차마다의 해석 약 15 ms와 행렬 만들기(점화식과 덧붙이기 8만 개) 약 4–5 ms였다: 26.6 ≈ 커널 8 + 회차마다 15 + 만들기 4–5. [024](024-batch-executor.md)가 처음에 적고 만들지 않은 단계("묶음 프로그램은 루프마다 한 번
+안쪽 회차마다의 해석 약 15 ms와 행렬 만들기(점화식과 덧붙이기 8만 개) 약 4–5 ms였다: 26.6 ≈ 커널 8 + 회차마다 15 + 만들기 4–5. 3단계를
+닫았다([136](../research/136-batch-executor-stage-three.md): 곱하기, 레인 없이 시작하는 모으기(sum0 6.09 → 1.01 ms, 막대 ≤ 1.5),
+리스트의 칸을 묶음에 한 번; b9 대비 matmul −35%, knapsack −12%, roots −7.6%; 실행기, 은행 질의, TPC-C는 그대로). 다음은 4단계(knapsack의
+훑기 여섯을 셋으로). [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).
 
diff --git a/docs/research/136-batch-executor-stage-three.md b/docs/research/136-batch-executor-stage-three.md
new file mode 100644
index 0000000..9252469
--- /dev/null
+++ b/docs/research/136-batch-executor-stage-three.md
@@ -0,0 +1,65 @@
+# 136 — 묶음 실행기 3단계: 4바이트 곱하기, 레인 없이 시작하는 모으기, 리스트의 칸 한 번
+
+2026-10-08. [025](../design/025-batch-programs.md)의 3단계다. 요소마다의 값을 연산의 꼴과 폭에 맞춘 루프로 줄였다. 코드는 `5ffae0b`
+(4바이트 곱하기), `c74bb65`(레인 없이 시작하는 모으기), `79d016c`(리스트의 칸을 묶음에 한 번)이고, 같은 방법으로 쟀다(`b12`, `b13`,
+`b14`; 11번의 중앙값을 번갈아 다섯 번씩, b9와도 세 번씩; 명령 수).
+
+## 쉬운 말로
+
+- **matmul의 막대에 못 미쳤다.** 4바이트 곱하기 뒤 matmul은 26.57 ms다(막대 ≤ 21). 막대의 셈이 실수 연산(약 22 ms) 밖을 14 ms로 두었는데,
+  그 밖은 안쪽 회차마다의 해석 약 15 ms와 행렬 만들기 약 4–5 ms였다. 지금 matmul은 커널 약 8 ms + 회차마다 약 14 ms + 만들기 약
+  4–5 ms다.
+- **sum0의 막대는 넘었다.** `total = total + 1`의 모으기가 레인을 만들지 않게 하자 sum0이 6.09에서 1.01 ms가 됐다(막대 ≤ 1.5). 명령은
+  85% 줄었다. 이제 sum0의 시간은 거의 묶음마다의 값이다: 묶음 3,907개 × 약 0.25 µs. 세 줄의 블록에 묶음마다 약 1,666 명령이 이 해석기
+  꼴의 바닥이다(레인의 일이 없어진 뒤에 남는 것).
+- **b9와 견주면**(같은 조용한 기기, 번갈아): matmul 40.01 → 25.97 ms(−35%, 명령 −26%), knapsack 11.47 → 10.07(−12%, 명령 −5.6%),
+  roots 8.97 → 8.29(−7.6%, 명령 −7.5%), join 117.2 → 115.8(−1.2%), BFS 24.07 → 24.10, sort 57.0 → 56.8. words는 묶이지 않는 일이고
+  215.4 → 219.2(+1.8%, 놓인 자리의 폭).
+- **지키는 것은 지켰다.** 실행기만의 길은 다섯 일 모두 명령 수가 b9와 같다. 은행 질의의 명령 수는 b9와 ±0.08% 안이다. TPC-C(창고 1,
+  단말 64, 20초, 번갈아 여섯 번)는 b9 116.3만 대 지금 117.1만 신규 주문/분(+0.7%)이다.
+
+## 만든 것
+
+- **4바이트 곱하기**(`words_op`). 2^32 아래의 정수 레인끼리의 곱이 2^32 아래면 4바이트에 그대로 둔다. 2^32 아래 정수의 곱은 실수의
+  곱과 비트까지 같다. 넘으면(64비트 곱의 위쪽 절반) 더하기처럼 레인을 실수로 돌려 다시 한다. 레인 넷에 `umull`, `umull2`, `uzp1`,
+  `uzp2`로 명령 10개다. matmul의 곱과 합이 4바이트에 머물러 명령이 20% 줄었다. BFS의 `q.node * 1048576`은 2^32를 넘어 한 번 해 보고
+  실수로 가는데, 명령으로 0.05%다.
+- **레인 없이 시작하는 모으기.** 모으기는 레인 배열 없이 수 둘(모든 레인에 같은 부분합과 같은 횟수)로 시작한다. 걸음마다 e가 모든
+  레인에 같은 값이고 가린 레인이 없으면, 각 레인이 할 계산(같은 차례의 같은 연산)을 한 번만 한다. 처음으로 다른 걸음(가린 레인,
+  레인마다 다른 e, 고르기, 펼친 걷기)이 오면 그때 레인을 그 수로 채운다. 끝에서는 정수이고 크기가 2^53 아래면 n × 그 수를 더하고(레인의
+  합과 같다), 아니면 회차의 차례대로 접는다. 지금의 검사(정수인지, 2^53, 여러 번 더한 레인)가 그대로다.
+  - 고정 소스 `REDUCE_SOURCE`를 더했다. 같은 e, 균일한 최대·최소, 분수, 2^53 너머, 중첩 루프 안의 횟수, 같은 e 다음의 가린 걸음과
+    레인마다의 걸음(양쪽 차례)이다. 이 소스가 레인을 그 수로 채우는 길을 56번, 그 수로 접는 길을 77번 지난다. 시드 23의 무작위
+    프로그램은 각각 6번과 53번의 실행에서 지났다.
+- **리스트의 칸을 묶음에 한 번**(`cells_of`). `pass`는 리스트를 바꾸지 않는다(grep: 바꾸는 호출 `widen`, `add_many`, `touched`는
+  `settle`, 묶음의 끝, 덧붙이기와 걸러내기에만 있다). 그래서 `find`와 `item_get`이 묶음마다 처음 읽는 리스트 넷의 칸을 한 번 가져와
+  쓴다. matmul은 안쪽 회차마다 찾기 둘이라 명령 2.3%, knapsack과 BFS는 0.4%다. 135에서 3%라 미뤘지만 matmul에서는 9%였다.
+- **하지 않은 것.** `sweep`(matmul의 회차마다 약 130 사이클)은 1단계부터 블록이 쓰는 지역 변수만 돌고, matmul의 회차는 매번 버퍼를
+  새로 쓰므로 건너뛸 수 없다. 025의 "좁은 열을 4바이트로 바로"는 이미 그렇다(`cells_at`이 1바이트 열을 4바이트 레인으로 읽는다).
+
+## 잰 것
+
+| 일 | b9 | b12 (곱하기) | b13 (모으기) | b14 (칸) | 기계어 | C |
+|---|---:|---:|---:|---:|---:|---:|
+| matmul | 40.01 ms | 26.56 | 26.76 | **25.97** | 14.2 | 7.6 |
+| knapsack | 11.47 | 10.52 | 10.56 | **10.07** | 7.9 | 6.25 |
+| roots | 8.97 | 8.82 | 8.31 | **8.29** | 9.57 | 6.86 |
+| join | 117.2 | 116.4 | 116.0 | 115.8 | 84.6 | 31.7 |
+| BFS | 24.07 | 24.31 | 24.03 | 24.10 | 7.7 | 9.9 |
+| sum0 (time.c) | 8.69 | | **1.01** | | | |
+
+- 실행기만의 join은 한 번의 `icount`에서 사이클이 +11%였는데, 다시 두 번 재니 b9와 ±2% 안이었다(명령은 같다).
+
+원본: `041-batches/2026-10-08-pairs.jsonl`, `2026-10-08-counts.jsonl`, `040-against-c/2026-10-08-counts.jsonl`(은행 질의),
+`2026-10-08-tpcc-*`, `2026-10-08-queries-*`.
+
+## 뜻과 맞음
+
+- 커밋마다 시드 1, 2, 3, 5, 23의 무작위 프로그램(기본과 `PURE_SELECT=all`), 고정 소스의 세 길(두 모드), 단위 시험이 지났다.
+- 단계의 끝(`79d016c`와 `REDUCE_SOURCE`)에서 단위 시험 세 모드, ASan 단위 시험(기본과 실행기 모드), sanitized `pure-run`의 고정 소스
+  (두 모드)와 시드 23의 프로그램(두 모드), Pure의 `make check`, aup의 검사 두 모드가 지났다.
+
+## 다음
+
+knapsack의 요소마다(약 6 ms, 훑기 여섯)가 이제 스위트에서 손대지 않은 가장 큰 덩어리다. 4단계: 열을 피연산자로 읽기(보폭 읽기가
+레인 배열로 옮기는 훑기 없이), 비교가 가는 레인을 세기(가르기의 세는 훑기 없이). 배낭은 훑기 여섯에서 셋이다.
-- 
cgit v1.2.3