1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
# 129 — 묶음 실행기의 값 줄이기: 한꺼번에 덧붙이기, 점화식을 레지스터 꼴로, 차례 없는 모으기, 그리고 BFS의 산수
2026-10-06. [128](128-batch-executor-tables-and-costs.md)이 잰 값 가운데 셋을 줄였다. 덧붙이기 하나 약 100 ns, 점화식 한 회차 약
60 ns, 모으기의 끝 회차당 4–9 ns다. 코드는 `4791c42`(덧붙이기), `9f0498b`와 `e8558e7`(점화식), `f9e3d22`(모으기)다. 128과 같은
방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b5` = `f9e3d22`, `b6` = `e8558e7`, 11번의 중앙값; 작은 모듈은 `costs/`). 그리고 BFS를
묶는 설계가 기준을 넘을 수 있는지 먼저 셈했다(`041-batches/frontier.c`).
## 쉬운 말로
- **기계어 없이 넷이 빨라졌다.** knapsack 15.1 → 10.8 ms, matmul 46.1 → 36.4, join 161 → 118, sort 74 → 55.5다. roots는 8.87 ms로
기계어(9.57)보다 빠르다. 기계어와의 차이는 knapsack 2.9 ms, matmul 22 ms, join 40 ms, BFS 89 ms로 줄었다.
- **바꾼 것은 셋이다.** 묶음의 덧붙이기를 항목마다 실행기의 걸음으로 하지 않고 리스트의 한 호출로 한다. 점화식의 걸음은 스택이
아니라 번호 붙은 값 사이의 연산이다. 모으기의 끝은 차례가 답을 바꾸지 않는 곳(`min`, `max`, 2^53 안의 정수 합)에서 차례 없이
벡터로 합친다.
- **BFS는 셈해 보니 가능성이 있다.** 프런티어를 묶음으로 돌면, 묶음을 열 때 `has`가 거짓이라 차례대로 다시 물어야 하는 간선이 100만
개 가운데 약 10만 5천 개다. 이 꼬리를 실행기가 아니라 묶음의 C로 하면 1 ms 안팎이다. 다만 레인마다 간선 수가 달라, 간선을 레인으로
펼쳐야 한다(함께 돌면 2.17배를 돈다). 아직 만들지 않았다.
## 묶음
| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만¹ |
|---|---:|---:|---:|---:|---:|
| roots | 9.57 ms | **8.87** | 130.4 | 6.86 | 1.67억 / 27.56억 |
| knapsack | 7.93 | 10.84 | 1,042.9 | 6.24 | 3.76억 / 216.88억 |
| matmul | 14.20 | 36.41 | 912.0 | 7.55 | 9.24억 / 214.37억 |
| join | 78.7 | 118.3 | 422.2 | 30.9 | 19.07억 / 76.70억 |
| sort | 35.6 | 55.5 | 77.3 | 26.9 | 10.13억 / 15.03억 |
| BFS | 7.66 | 96.9 | 92.9 | 9.93 | 46.93억 / 47.16억² |
| words | 215.6 | 215.2 | 207.0 | 37.8 | 39.76억 / 39.34억² |
¹ `suite-run` 세 바퀴의 사용자 모드 명령(C와 읽기 포함, 126과 같다). ² `b5`.
- `b4`(128)에서 `b6`으로 묶음의 시간: knapsack 15.07 → 10.84, matmul 46.07 → 36.41, join 161.2 → 118.3, sort 74.3 → 55.5, roots
9.22 → 8.87 ms. 명령은 knapsack 4.72억 → 3.76억, matmul 11.18억 → 9.24억, join 28.77억 → 19.07억, sort 14.09억 → 10.13억이다.
- 실행기만의 명령은 그대로다(roots 27.56억, knapsack 216.88억, `b4`부터 `b6`까지). 바꾼 것은 묶음과 리스트의 코드뿐이다.
- knapsack은 `b5`에서 10.17 ms였다. 명령이 같고(3.76억) 사이클이 3% 많아, 놓인 자리로 본다. 기계어의 join은 빌드가 같은 코드인데
72.3–78.7 ms로 오간다.
## 바꾼 것
- **한꺼번에 덧붙이기**(`4791c42`). 묶음의 끝에서, 모든 덧붙이기가 이벤트의 리스트에 하나씩이고(색인 없이), 리스트가 그 꼴을
지키며 받을 수 있으면(`pure_list_takes`: 키 없는 FLAT은 끝에, DENSE는 지금의 개수로 담을 수 있는 키로, HASHED는 수 키로; 배열의
한계를 넘지 않게) 128개씩 한 번에 넣는다(`pure_list_add_many`). 메모리 몫은 넣기 전에 끝의 모습으로 셈한다. 항목 하나는 몫이 세는
것을 늘리기만 하므로, 끝이 몫 안이면 그 사이의 어느 회차도 넘지 않는다. 넘으면 지금처럼 회차대로 해서 그 회차에서 결함이 난다.
열은 한 번 늘리고 한 번 넓힌다. 이미 있는 키를 만나면 그 회차의 `EXISTS`다. 리스트의 꼴을 바꾼 회차(키 있는 리스트의 첫 항목이
DENSE나 HASHED를 만든다) 뒤에는 다시 한 번에 넣기를 시도한다. DENSE에 5만 개: 5.18 → 0.65 ms(기계어 0.28).
- **점화식을 레지스터 꼴로**(`9f0498b`, `e8558e7`). 걸음은 스택에 넣고 빼는 대신, 한 회차가 쥐는 수(걸음의 결과, 점화식의 값, 루프의
값, 그대로인 수)에 번호를 매기고 그 두 번호의 연산이다. 한 문장 안에서 두 번 계산하는 연산은 한 번만 한다(문장이 끝나기 전에는
x가 그대로다). 한 회차는 묶음마다 한 번 깔아 둔 동작들을 도는 루프 하나이고, 갱신의 마지막 걸음이 x에 바로 쓴다. 그 사이에 x를
읽는 자리(기록)는 x가 바뀌지 않았으면 레인 배열 하나를 함께 쓴다(join의 네 자리가 한 번 저장). MINSTD 100만 회차: 44.4 → 21.8
ms(기계어 18.5, 실행기만 73.0). x를 네 번 읽어 합하면 50.4 → 36.0 ms(기계어 19.9).
- **차례 없는 모으기**(`f9e3d22`). `min`과 `max`의 합치기는 차례가 답을 바꾸지 않는다(−0이 +0 아래). 정수의 합도 크기의 합이 2^53
아래면 그렇다. 그런 끝은 레인 순서로 넷씩 합친다. 레인마다의 `min`, `max` 걸음과 그 끝은 수를 그 차례의 정수로 바꿔 비교하는
루프라 벡터가 된다. 레인을 비우는 루프는 개수를 지역 변수로 두어 벡터가 됐다. 100만 회차의 `max`: 9.80 → 4.00 ms(기계어
4.27), 회차를 세는 합: 4.51 → 1.61 ms.
## 무엇에 값을 내는가
`costs/time.c`, 세 길, 세 번의 중앙값(`2026-10-06-costs.jsonl`의 `b5`, 점화식은 `b6`; 괄호는 `b4`).
| 모듈 | 기계어 | 묶음 | 실행기만 |
|---|---:|---:|---:|
| `ops` (`max` 모으기) | 4.27 ms | **4.00** (9.81) | 156.3 |
| `nest` | 23.1 | **10.17** (10.20) | 653.0 |
| `adds` | 0.28 | 0.65 (5.18) | 5.17 |
| `probes` | 56.1 | 73.0 (85.1) | 259.7 |
| `recur` | 18.45 | 21.8 | 73.0 |
| `recur4` | 19.9 | 36.0 | 181.4 |
`b6`의 표본(묶음, Pure의 몫 가운데, 대략):
- **join (118 ms)**: 점화식 약 35 ms(회차당 약 33 ns: 연산의 사슬에 나누기가 있고, 값이 메모리를 거쳐 다음 걸음으로 간다), 레인의
산수와 칸 읽기 약 32 ms, HASHED 찾기 약 24 ms, 칸에 더하기와 끝 정리 약 20 ms, 덧붙이기 약 6 ms.
- **matmul (36 ms)**: 중첩 몸체 약 32 ms(안쪽 회차마다 명령 15개를 레인 200개에), 표를 만드는 루프 약 4 ms. 기계어는 전체가 14 ms다.
- **knapsack (11 ms, `b5`)**: 안쪽 루프 약 7 ms, 미룬 쓰기의 정리 약 2 ms, 덧붙이기 1 ms 아래.
- **sort**: 묶음 밖이다. 실행기, 정렬(`make_ordered`), 라이브러리의 몫이 대부분이다.
## BFS의 산수
`frontier.c`는 스위트의 그래프(노드 10만, 간선 100만)로 BFS를 프런티어 묶음처럼 돈다. 회차 `i`부터 묶음을 열 때 큐의 개수까지(최대
B개), 각 간선의 `has`는 묶음을 열 때 묻는다. 거짓이라 한 간선이 후보이고, 후보는 회차 차례대로 다시 물어 더하거나(처음 보는 노드)
버린다(같은 묶음의 앞 회차가 더했다).
| B | 간선 | 후보 | 더하기 | 묶음 | 함께 돌 때의 레인-회차 |
|---:|---:|---:|---:|---:|---:|
| 1024 | 999,913 | 105,232 | 99,997 | 101 | 217만 (간선의 2.17배) |
| 256 | 999,913 | 101,243 | 99,997 | 394 | 200만 (2.00배) |
| 64 | 999,913 | 100,296 | 99,997 | 1,565 | 181만 (1.81배) |
- **꼬리는 작다.** 차례대로 해야 하는 후보가 간선의 약 10%다. 후보 하나에 DENSE 비트를 다시 묻고, 부모의 깊이를 읽고(부모는 묶음을
열 때 이미 있다), 비트와 깊이를 쓰고, 큐에 덧붙인다. 묶음의 C로 하면 하나에 약 10 ns, 1 ms 남짓이다. 실행기의 걸음으로 하면
10만 × 100 ns 이상이라 그것만으로 기계어 전체(7.7 ms)를 넘는다. 그래서 꼬리는 `at_once`처럼 묶음 쪽 C여야 한다.
- **간선은 펼친다.** 레인마다 간선 수가 다르다(평균 10). 중첩 루프처럼 함께 돌면 가장 긴 레인만큼 돌아 2.17배다. 묶음의 노드마다
간선 행의 범위를 구해 간선을 레인으로 이어 붙이면(024가 적은 "펼치기") 간선 하나에 레인 하나다.
- **예상.** 간선 하나에 레인의 일 몇 가지(행의 `to` 읽기, 비트 묻기, 고르기) 약 3–4 ns로 3.5 ms, 노드 하나에 간선 범위 찾기(묶은
리스트의 색인) 약 15–20 ns로 2 ms, 꼬리 1 ms, 해석 값은 묶음 101개라 무시할 만하다. 합해 약 6–7 ms로, 기계어의 7.7 ms(C 9.9)와
겨룰 수 있다. 캐시 미스(간선 열 4 MB)는 C와 기계어도 내는 값이고, 묶음은 레인이 서로 떨어져 있어 미스가 겹친다.
- **필요한 셋.** (1) `if i >= L.count { break }`이고 몸체가 L에 덧붙이기만 하면, 묶음은 열 때의 개수까지다. (2) 레인마다 다른 걷기를
레인으로 펼친다. (3) 커지기만 하는 걸러내기: `if !L.has(k) { … }`이고 L이 몸체에서 더해지기만 하면, 열 때 참인 레인은 건너뛰고,
거짓인 레인은 끝에서 차례대로 다시 묻고 몸체의 덧붙이기를 한다. 몸체가 읽는 것은 열 때 있던 것이어야 한다(BFS의
`seen[q.node]`는 프런티어의 노드라 열 때 있다; 계획이 이것을 알아볼 규칙이 필요하다). (1)과 (2)는 (3) 없이도 시험할 수 있다
(프런티어를 돌며 간선 수를 합하는 루프). 그것부터 만들고 잰다.
## 뜻과 맞음
- `APPEND_SOURCE`: DENSE 리스트에서 회차 q에, HASHED 리스트에서 회차 p에 이미 있는 키(그 회차의 결함), 회차 p부터 DENSE가 담지
못하는 키(그 회차부터 꼴이 바뀐다), 한 리스트에 회차마다 두 번 덧붙이기(회차대로), 넓어지는 열, 덧붙이기 한가운데에서 다하는
메모리 몫 셋. 세 길(묶음, 실행기만, 기계어)이 같고, `exists`, `memory`, `work` 결함이 다 난다.
- 시드 1, 2, 3, 5, 23의 무작위 프로그램(665개)이 커밋마다 다섯 길에서 같았다. 시드 23의 프로그램에서 한꺼번에 덧붙이기가 31,402번
(항목 400만 개) 돌았고, 메모리 몫 때문에 회차대로 간 것이 292번, 이미 있는 키의 결함이 4번이었다.
- 단위 시험이 세 JIT 모드와 ASan(실행기 모드)에서, aup의 검사가 두 모드에서 통과했다. sanitized `pure-run`으로 시드 1, 5, 23의
프로그램과 고정 소스 넷(410개)을 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다.
- Pure의 `make check`가 새벽에 다섯 번 연속 `server_view_workers`(모듈을 바꾼 뒤 스트림이 10초 안에 새 값을 주지 않음)에서
실패했다. 묶음을 꺼도, 바꾸기 전 커밋에서도 실패했고, 같은 코드가 09:50에는 세 번 다 통과했다. 따로 돌리면 늘 통과한다. 다른
세션이 기기를 쓰던 때의 타이밍 문제로 본다(이 시험은 10-05에도 같은 꼴로 한 번 실패했다).
## 다음
- **모으기 인식의 빈틈.** `total = total + A + B`는 `(total + A) + B`라서 지금의 `x = x op e` 인식에 맞지 않고, 루프 전체가
계획에서 빠진다(같은 계산을 `total + (A + B)`로 쓰면 묶인다: 181 → 36 ms). 정수의 합에서는 둘이 같으니, 한 회차에 여러 번 더하는
모으기로 받을 수 있다.
- **BFS**: 위의 (1)과 (2)를 만들고 재고, 그다음 (3).
- **join**: HASHED 찾기를 레인에 대고 바로 하기(약 24 ms), 레인의 산수.
- **matmul**: 레인이 적은 중첩 몸체의 명령당 값(미리 풀어 둔 몸체, 곱해 더하기).
|
