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
|
# 130 — 묶음 실행기로 BFS를: 가드, 묶음 안의 걷기, 걸러내기, 그리고 이 설계의 바닥
2026-10-08. [129](129-batch-executor-costs-cut.md)가 BFS에 필요하다고 적은 세 조각을 만들었다. 코드는 `33c6ef5`(가드와 묶음 안의
걷기)와 `9b0b23f`(걸러내기)다. 같은 방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b7` = `9b0b23f`, 11번의 중앙값). 탐색만의 명령은
`041-batches/search/`의 드라이버로 셌다(그래프를 읽은 뒤 탐색을 1번과 11번 돌려 뺐다, `2026-10-08-search-counts.jsonl`).
## 쉬운 말로
- **BFS가 묶음으로 돈다.** 실행기만 93.4 ms이던 것이 묶음으로 41.0 ms다. 답(홉, 닿은 노드 수)은 C와 같다. 그러나 기계어는 7.66 ms,
C는 10.0 ms다. 기계어의 5.4배다.
- **어디에 드는지 셌다.** 탐색 하나에 묶음은 간선당 명령 211개(사이클 81개), 기계어는 38.5개(17개)다. 가장 큰 낭비는 걸러내기의
몸체다. 후보(간선의 약 10%)에만 필요한 명령 약 12개를 1024 레인 모두에 돈다.
- **이 설계의 바닥은 기계어보다 조금 위다.** 후보만 골라 몸체를 돌게 해도, 연산 하나가 레인을 한 번 훑는 방식으로는 간선당 약 50개로
셈된다. 기계어의 약 1.3배다. 기계어와 같거나 넘으려면 024의 표에 있던 합친 연산("칸을 모아 묻기", "묻고 고르기")이 있어야 한다.
이것을 할지가 JIT를 걷어낼지를 정한다(아래, 판단할 것).
## 묶음
| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C |
|---|---:|---:|---:|---:|
| roots | 9.57 ms | **8.95** | 130.5 | 6.86 |
| knapsack | 7.94 | 10.32 | 1,053.9 | 6.24 |
| matmul | 14.89 | 36.51 | 914.8 | 7.81 |
| join | 78.75 | 117.8 | 427.6 | 34.7 |
| sort | 35.5 | 56.8 | 78.3 | 26.9 |
| BFS | 7.66 | **41.0** (b6 97.0) | 93.4 | 10.0 |
| words | 216.4 | 214.3 | 209.7 | 38.1 |
- BFS 말고는 b6과 같다. 실행기만의 명령도 같다(roots 27.56억, knapsack 216.88억, matmul 214.37억, join 76.70억, sort 15.03억).
바꾼 것은 묶음과 리스트, 그리고 로드 때의 계획이다.
- BFS의 묶음 명령은 `suite-run` 세 바퀴(C와 읽기 포함)로 46.93억(b5)에서 37.64억이 됐다.
## 만든 것
- **가드**(`33c6ef5`). 세는 루프의 블록이 `if i >= L.count { break }`로 시작하고 블록이 L에 더하기만 하면(`PLAN_GUARD`), 묶음은 열 때의
L의 개수까지만 돈다. 그 회차들에서 실행기의 시험도 거짓이다(개수는 커지기만 한다). 남은 회차가 최소(16)에 못 미치면 그 회차들은
실행기가 돌고, 그 뒤에 다시 묶음을 시도한다(BFS의 처음 몇 층).
- **묶음 안의 걷기**(`33c6ef5`). 묶음의 블록에 있는 `EACH`(조각이면 레인마다의 조각, where의 범위는 없음)는 레인마다 제 항목들을 걷는다.
작업량은 각 걷기가 열릴 때 센다. 두 가지로 돈다.
- **함께**: 중첩 LOOP처럼 회차 t를 항목이 t개보다 많은 레인들이 돈다. `break`가 있으면 이 길이다.
- **펼치기**(`PLAN_SPREAD`): `break`가 없고 걷기가 정하는 지역 변수가 모으기이거나 항목 자신의 것이면, 항목들을 회차 차례대로
레인으로 펼쳐 1024개씩 돈다. 바깥 레인의 값은 각 항목의 바깥 레인에서 모아 읽는다. 모으기는 바깥 레인의 몫에 항목 차례대로
더한다. 항목 자신의 변수는 그것을 쓴 마지막 항목의 값을 남긴다(루프의 블록 다른 곳에서는 읽지 않는다). 함께 돌면 레인-회차가
간선의 2.17배라서(129) 펼치기가 기본이다.
- **걸러내기**(`9b0b23f`). `if !L.has(k) { 덧붙이는 곧은 코드 }`이고 L이 그 코드에서만 커지면(`PLAN_FILTER`; 리스트 하나에 걸러내기
하나, 중첩 LOOP 안에는 없음) 이렇게 한다.
1. 묶음을 열 때의 L로 레인마다 묻는다. 참인 회차는 실행기도 건너뛴다(L은 커지기만 한다).
2. 거짓인 회차에서 몸체를 돌리고, 그 회차들을 (회차, k, 덧붙이기의 칸들)로 모아 둔다. 펼친 걷기에서는 덩어리마다 모은다.
3. 끝에서 회차 차례대로 다시 묻는다. 기준은 지금의 L과, 앞서 모은 회차가 더하는 키다. 그사이 더해졌으면 그 회차는 뺀다.
4. 남은 것을 리스트마다 한꺼번에 넣는다(`pure_list_add_many`).
다시 묻고 결정하고 메모리 몫을 셈하는 일은 어떤 것도 바꾸기 전에 한다. 이미 있는 키를 더하려 하거나, 리스트가 그 꼴로 받지 못하거나,
몫이 모자라면 묶음이 회차들을 돌려준다. 그러면 실행기가 정확한 회차에서 결함을 낸다.
- **커지는 리스트 읽기.** 걸러내기가 키우는 리스트는 앞 회차의 항목이 바꾸지 않는 꼴로만 읽는다. 가드의 개수, `first`, 키 없는
리스트의 자리, 키로 찾은 필드가 그렇다. 키로 찾아 없으면 묶음이 돌려준다.
- **키의 비트맵.** 키가 비트로 있는 리스트(`pure_list_bits`)의 `has`와, DENSE 리스트(모든 키가 있지는 않은 것도, `pure_list_dense`)의
키로 찾기를 레인 루프 하나로 한다. 4바이트 행과 키는 따로 빠른 루프를 쓴다.
## 무엇에 값을 내는가 (BFS)
| | 묶음 | 기계어 |
|---|---:|---:|
| 탐색 하나의 명령 | 2억 1,130만 | 3,850만 |
| 간선당 명령 / 사이클 | 211 / 81 | 38.5 / 17 |
| 프런티어 합(간선의 `to`를 더하기만)의 간선당 명령 / 사이클 | 70 / 26 | 35 / 15 |
표본(탐색만, 묶음)으로 나누면 이렇다.
- 걸러내기 몸체를 모든 레인에 도는 값이 가장 크다. 키로 찾기, 칸 모으기 둘, 바깥 값 모으기, 행 검사가 대부분 여기서 난다(약 40%).
- 간선마다 하는 일(덩어리 만들기, `to` 모으기, `has`, `NOT`, 마스크)이 약 25%다.
- 후보를 모으고 다시 묻고 넣는 일(`keep_filtered`, `decide`, `apply_filters`와 그 리스트 호출)이 약 25%다.
- 노드마다 조각 경계를 두 번 찾는 일(`pack_seek`)이 약 6%다.
**바닥의 셈.** 후보만 골라 몸체를 돌게 하면(고르기) 간선마다 남는 것은 레인 훑기 일곱 번쯤이다. 덩어리 만들기, `to` 모으기, `has`, `NOT`,
마스크, 후보 고르기가 그렇다. 훑기 한 번이 요소당 명령 3–5개이니 간선당 약 25개다. 여기에 다음이 더해진다.
- 노드마다: 경계 찾기와 바깥 연산, 간선 10개로 나누면 약 14개
- 후보마다: 몸체와 다시 묻기와 넣기, 후보가 10%라 약 11개
합해 간선당 약 50개, 사이클로 약 23개다. 기계어의 1.3배쯤이다. 프런티어 합이 70개(기계어 35개)인 것도 같은 결을 보인다. 연산마다
레인을 따로 훑는 값이 기계어의 레지스터 안 계산보다 크다. 이 바닥을 넘으려면 자주 나오는 연산의 짝을 빌드 때 C로 만든 합친 연산으로
해야 한다. "행에서 `to`를 모아 비트에 묻기"를 하나로, "묻고 거짓인 레인 고르기"를 하나로 하는 식이다. 024가 처음부터 표로 두자고 한
것이고, 묶음에서 나오는 꼴을 세어 정하기로 했던 것이다.
## 뜻과 맞음
- 생성기에 `front` 꼴을 더했다. 가드 루프 안에 걷기(조각과 통째, 빈 조각 포함)가 있고, 그 안에 다음이 섞인다.
- 모으기, 분수, 항목 자신의 `let`, 바깥 변수 읽기
- `break`(함께 도는 길)
- 걸러내기 `if !d.has(k) { d.add(...); e.append(...) }`(가끔 다른 키를 더해 부딪침)
시드 1, 2, 3, 5, 23의 프로그램이 다섯 길에서 같았다. 시드 23의 프로그램에서 펼친 걷기 8,819번, 함께 도는 걷기 7,651번이 돌았고,
걸러내기는 5,806번 결정해 38번 돌려줬다(`33c6ef5` 때와 `9b0b23f` 때의 생성기 기준).
- 고정 소스는 둘이다.
- `FRONT_SOURCE`: 목록보다 긴 가드 루프, 레인마다 다른 조각, `break`가 있는 걷기, 분수의 합, 0 나누기, 작업량 예산
- `GRAPH_SOURCE`: 걸러내기로 만든 그래프, 같은 그래프로 두 번의 BFS, 묻는 키와 다른 키를 더해 `EXISTS`가 나는 루프, 걸러내기의
넣기 한가운데에서 다하는 작업량·메모리 몫. 이 소스에서 걸러내기가 662번 결정하고 123번 돌려줬다.
세 길이 바이트까지 같다.
- 단위 시험 세 모드, ASan(실행기 모드), aup의 검사 두 모드, Pure의 `make check`가 통과했다. sanitized `pure-run`으로 시드 23의 프로그램과
고정 소스 여섯을 돌려도 오류가 없었고 출력은 실행기만으로 돈 것과 같았다.
- ASan이 처음에 누수를 찾았다. 보기의 스레드에서 돈 걸러내기가 스레드 지역 버퍼를 남긴 것이다. 이제 묶음이 끝날 때마다 그 버퍼들을
놓는다. 메모리를 쥐고 있지 않는 쪽이기도 하다.
- `make check`에서 `server_clocks`와 `server_view_workers`가 한 번씩 실패했고, 다시 돌리자 통과했다(알려진 타이밍 문제).
## 판단할 것
BFS는 기계어를 걷어내는 기준의 마지막 일이다. 셈으로는 지금의 꼴(연산마다 레인을 한 번 훑기)이 기계어의 약 1.3배에서 멈춘다. 길은
둘이다.
1. **합친 연산의 표를 만든다.** 빌드 때 C로 만드는 작은 연산 묶음이다. 실행 시간에 코드를 만들지 않는다는 원칙은 그대로다. 묶음에서
자주 나오는 짝을 세어 고르고, 계획이 그 짝을 알아보면 쓴다. 표는 유한하고, 맞지 않는 꼴은 지금처럼 따로 돈다.
2. **기계어를 BFS 같은 일에 남긴다.** 묶음 실행기가 덮지 못하는 곳에서만 쓴다.
어느 쪽이든 다음 일은 같다. 걸러내기 몸체와 `if`/`else`의 갈래, roots의 빠진 레인처럼 레인이 적게 도는 곳을 위한 고르기다. 레인이 적을 때
그 레인만 모아 돈다. 그것을 만들어 재고, 이 셈과 견준다.
|
