From f47f0caa14889013436438f2bcb2c482a58e630b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Fri, 9 Oct 2026 15:41:24 +0100 Subject: Research 138: the batch executor's stage 5, design 025 made: sums into cells at once in integers (join 116.0 to 110.5 ms, short of 108: what is left is the same cells' memory, read, add and write again), decide's bit found once (BFS 23.2, short of 21.5: the tail's time was its loads more than its instructions), and the batch executor's loops aligned to 64-byte lines (the hot loops' placement had swung knapsack 6% at the same instructions; the lists' loops aligned too cost the bank's queries 1-2% more instructions, so not they); against b9 matmul -36%, knapsack -28%, roots -7.6%, join -6.2%, BFS -3.9%, the executor alone, the bank queries and TPC-C (+0.7%) as they were; 025's bars and what each stage measured; 024 and CHECKPOINT say so --- docs/research/138-batch-executor-stage-five.md | 79 ++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) create mode 100644 docs/research/138-batch-executor-stage-five.md (limited to 'docs/research/138-batch-executor-stage-five.md') diff --git a/docs/research/138-batch-executor-stage-five.md b/docs/research/138-batch-executor-stage-five.md new file mode 100644 index 0000000..d3e46bf --- /dev/null +++ b/docs/research/138-batch-executor-stage-five.md @@ -0,0 +1,79 @@ +# 138 — 묶음 실행기 5단계: 꼬리 둘, 그리고 루프의 정렬 + +2026-10-09. [025](../design/025-batch-programs.md)의 마지막 단계다. 걸러내기 후보의 꼬리(BFS)와 칸에 더하기의 꼬리(join)를 줄였고, 뜨거운 루프가 +놓이는 자리가 커밋마다 흔들리던 것을 빌드 플래그 하나로 멈췄다. 코드는 `956a6cf`(칸에 더하기를 한 번에), `ad44b68`(`decide`가 비트를 한 번), +`2ce9ce1`(루프 정렬)과 `3e76a60`(정렬은 묶음 실행기에만)이다. 같은 방법으로 쟀다(`b17`, `b18`, `b18a`, `b19`, `b20`; 번갈아, 명령 수). + +## 쉬운 말로 + +- **막대 셋에 못 미쳤다.** + - join은 116.0에서 110.8 ms다(막대 ≤ 108). 칸에 더하기의 꼬리는 약 17에서 약 12 ms로 줄었다. 회차의 루프는 이제 정수뿐이고 명령이 + 합 하나에 약 20개인데, 회차당 약 30 사이클이 든다. 남은 것은 같은 칸을 읽고 더해 쓰는 메모리의 이어짐이다(16행에 행이 되풀이된다). + 그것을 끊는 범용의 길(묶음 안에서 행마다 먼저 모으고 칸에는 한 번 쓰기)은 행 수만큼의 자리가 있어야 하고, 이 설계 밖이다. + - BFS는 23.98에서 23.17 ms다(막대 ≤ 21.5). `decide`는 2.5에서 1.6 ms가 됐다. 132의 "후보당 250"은 명령이었는데, 꼬리의 시간은 + 대부분 그것이 읽는 메모리(비트, 남긴 회차)였다. 그래서 명령을 반 가까이 덜어도 시간은 3분의 1만 돌아왔다. 남은 꼬리 약 5.2 ms에 + 1.5 ms를 넘는 것이 하나도 없어 멈췄다. + - knapsack은 4단계에서 8.25 ms였는데, 이 단계의 첫 커밋 뒤에 같은 명령으로 8.74 ms가 됐다(사이클 +3.4%). 놓인 자리다. 루프 정렬 뒤 + 8.21 ms다. +- **루프 정렬**(`-falign-loops=64`, `BATCH_OPTIMIZE`). 묶음 실행기의 루프가 각각 64바이트 줄의 처음에서 시작한다. 이것이 없으면 파일의 + 어디를 고쳐도 뜨거운 루프가 움직였다(`words_op`의 더하기 루프가 64바이트 줄의 28, 60, 20 …에서 시작). 정렬하자 묶음으로 도는 일의 + 사이클이 모두 줄었다(knapsack 5.3%, matmul 1.9%, BFS 1.5%, join 1.2%). 명령은 채움 때문에 0.7–2.3% 늘었다. 처음에는 리스트의 루프도 + 정렬했는데(`LIST_OPTIMIZE`를 함께 써서), 은행 질의의 명령이 b9보다 0.8–2.0% 늘고(기준 1%) 사이클은 오르내려 이득이 없었다. 그래서 + 묶음 실행기에만 준다. +- **b9(025를 시작하기 전)와 견주면**(마지막 빌드 b20): matmul 40.0 → 25.8 ms(−36%), knapsack 11.45 → 8.19(−28%), roots 8.97 → 8.29(−7.6%), + join 117.9 → 110.5(−6.2%), BFS 24.15 → 23.21(−3.9%), sort 57.0 → 55.9, words 215.3 → 217.7(묶이지 않는 일). + +## 만든 것 + +- **칸에 더하기를 한 번에**(`sums_in_words`). 회차 0부터, 먼저 행과 e를 4바이트로 바꾸고(벡터 코드) e가 2^32 아래의 정수가 아닌 첫 회차를 + 찾는다. 그 앞의 회차는 회차마다 합을 차례대로 한다: 1·4바이트 칸은 정수로, 제 바이트에 드는 동안. 8바이트 칸은 수로, 유한한 동안. + 실행기의 더하기가 만들 수와 같고, 결함도 넓히기도 없다. 처음으로 아닌 회차와 합에서 지금의 길(회차마다, 넓히기와 결함을 그 회차에서)이 + 이어서 돈다. 그 앞에서 아무것도 넓어지거나 결함이 나지 않았으므로 되돌릴 것이 없다. + - 고정 소스 `SUMS_SOURCE`를 더했다: 16행이 되풀이되는 표, 묶음 중간에 1바이트에서 4바이트로 넓어지는 열, 2^32를 넘어 8바이트로 가는 열, + 가린 회차에 더하는 분수. 메시지 여섯에서 7,912 회차를 한 번에, 3,228 회차를 지금의 길로 돌고, 세 길(묶음, 실행기, 기계어)이 같다. + - 처음 짠 것은 8바이트 칸을 받지 않아 열 하나가 8바이트면 묶음 전체가 지금의 길로 갔다. 이 소스가 그것을 보였다(13 묶음 모두 회차 0에서). +- **`decide`의 비트를 한 번**. 남긴 회차마다 키를 비트 자리로 한 번 바꾸고, 걸러내기가 더하는 키가 물은 키와 같으면 그 자리를 쓴다(걸러내기는 + 그렇다). 우리 비트를 지울 때는 세운 비트의 낱말만 지운다(세울 때 적어 둔다). BFS 명령 −0.4%. +- **루프 정렬**. 위와 같다(묶음 실행기에만). + +## 잰 것 + +| 일 | b9 | b16 (4단계 끝) | b17 (칸) | b18 (`decide`) | b19 (둘 다 정렬) | b20 (묶음만 정렬) | 기계어 | C | +|---|---:|---:|---:|---:|---:|---:|---:|---:| +| matmul | 39.99 ms | 26.27 | 26.36 | 26.24 | 25.76 | **25.77** | 14.2 | 7.6 | +| knapsack | 11.45 | 8.26 | 8.74 | 8.74 | 8.20 | **8.19** | 7.9 | 6.25 | +| roots | 8.97 | 8.28 | 8.29 | 8.28 | 8.30 | **8.29** | 9.57 | 6.86 | +| join | 117.9 | 116.0 | 111.8 | 111.4 | 110.9 | **110.5** | 84.6 | 31.7 | +| BFS | 24.15 | 23.98 | 24.24 | 23.56 | 23.11 | **23.21** | 7.7 | 9.9 | + +- 명령(b9 → b20, 묶음 길): matmul −23.7%, knapsack −11.7%, roots −7.3%, join −4.0%, BFS 0.0%(`decide`의 −0.5%와 정렬의 채움). +- 실행기만의 길: 다섯 일 모두 b9와 같은 명령이다(±0.1%). 리스트의 루프까지 정렬했던 b19에서는 BFS가 +1.0%였다. +- 원본: `041-batches/2026-10-08-pairs.jsonl`과 `2026-10-09-pairs.jsonl`, `2026-10-08-counts.jsonl`과 `2026-10-09-counts.jsonl`(측정이 + 날짜를 넘었다); 은행 질의 `040-against-c/2026-10-09-counts-s19.jsonl`(둘 다 정렬), `2026-10-09-counts-s20.jsonl`(묶음만). + +## 뜻과 맞음 + +- 커밋마다 시드 1, 2, 3, 5, 23의 무작위 프로그램(기본과 `PURE_SELECT=all`), 고정 소스의 세 길(두 모드; GRAPH의 `exists`, `memory`, `work` + 결함이 제 회차에), 단위 시험이 지났다. +- 단계의 끝에서(`2ce9ce1`) 단위 시험 세 모드, ASan 단위 시험(기본과 실행기 모드), sanitized `pure-run`의 고정 소스(두 모드, `SUMS_SOURCE`와 + GRAPH 포함)와 시드 23의 프로그램(두 모드), aup의 검사 두 모드가 지났다. Pure의 `make check`는 다시 `server_view_workers`의 시간 초과로 + 한 번 멈췄고(4단계 끝과 같은 흔들림), 홀로 세 번 지나고 다시 돈 전체가 지났다. 정렬을 묶음 실행기에만 준 `3e76a60`에서 단위 시험 네 + 모드와 고정 소스(두 모드)를 다시 돌렸다. +- 은행 질의의 명령 수(`3e76a60`)는 b9와 ±0.9% 안이다(같은 빌드에서도 1% 안팎 오가는 수). TPC-C(번갈아 여섯 번)는 b9 121.5만 대 지금 + 122.4만 신규 주문/분(+0.7%)이다. + +## 025를 닫으며 + +다섯 단계의 막대와 잰 수: + +| 단계 | 막대 | 잰 수 | +|---|---|---| +| 1. 블록의 사실을 로드 때 | knapsack ≤ 10.3 ms, 묶음마다 ≤ 0.60 µs | 10.34, 0.68 (못 미침) | +| 2. 균일·아핀 조각 | knapsack ≤ 9.2, ≤ 0.45 µs, matmul ≤ 33 | 10.51, 0.63, 36.1 (못 미침) | +| 3. 꼴과 폭에 맞춘 커널 | matmul ≤ 21, sum0 ≤ 1.5 | 26.6 (못 미침), 1.01 | +| 4. 훑기의 수 | knapsack ≤ 8.6 | 8.25 | +| 5. 꼬리 | BFS ≤ 21.5, join ≤ 108 | 23.17, 110.8 (못 미침) | + +못 미친 막대는 모두 셈이 빠뜨린 것이 있었다(1단계: 명령마다의 머리, 2단계: 조각이 덮는 명령의 값, 3단계: 회차마다의 해석과 행렬 만들기, +5단계: 명령과 메모리의 시간). 남은 큰 틈은 둘이다. matmul의 안쪽 회차마다의 해석(약 14 ms)과 BFS(기계어의 3배)의 노드와 간선마다의 해석이다. +둘 다 이 해석기 꼴의 바닥(135)이고, 루프마다 미리 짠 프로그램이 그 수단이다. 025 밖이다. -- cgit v1.2.3