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
|
# 127 — 묶음 실행기 2단계: 중첩 루프를 함께, 모으기, 그리고 roots가 기계어를 넘다
2026-10-05. [024](../design/024-batch-executor.md)의 2단계와 그 뒤의 다듬기(`4a39bf0`, `bec7ce6`). [126](126-batch-executor-stage-one.md)과
같은 방법으로 쟀다(`041-batches/runs.sh`, 빌드 `b2` = `bec7ce6`, 11번의 중앙값).
## 쉬운 말로
- **roots가 기계어 없이 계층보다 빠르다.** 실행기만으로 130.6 ms인 roots가 묶음으로 9.13 ms다. 023의 계층(기계어)은 9.57 ms, C는
6.86 ms다. 기계어를 만들지 않는 실행기가 이 일에서 계층을 넘은 것은 처음이다.
- **matmul은 914.9 ms에서 50.0 ms가 됐다.** 계층은 14.3 ms라 아직 3.5배다. 남은 것은 둘이다. 하나는 행렬을 채우는 루프로, 점화식이
있어 묶지 못하고 실행기에서 약 12 ms가 든다. 다른 하나는 안쪽 루프의 회차마다 명령 15개를 해석하는 값이다(레인이 200개뿐이다).
- **바뀐 것.** 묶음의 몸체 안 루프가 레인마다 함께 돈다. 회차 t는 회차가 t보다 많고 빠져나가지 않은 레인들이 돈다. `BREAK`는 레인마다
빠져나가게 한다. `x = x + e`, `min`, `max`는 모으기다. 레인마다 제 몫을 모으고, 묶음의 끝에서 회차 차례대로 합친다.
- **묶음 루프가 없는 모듈의 실행기는 그대로다.** join과 sort의 명령 수는 묶음을 켜도 같다(76.69억, 15.02억).
## 묶음
| 일 | 기계어 (JIT) | 묶음 (`PURE_JIT=0`) | 실행기만 | C | 묶음의 명령 / 실행기만 |
|---|---:|---:|---:|---:|---:|
| roots | 9.57 ms | **9.13** | 130.6 | 6.86 | 1.73억 / 27.56억 |
| knapsack | 7.52 | 13.80 | 1,040.8 | 6.22 | 4.65억 / 216.88억 |
| matmul | 14.27 | 50.03 | 914.9 | 7.55 | 12.06억 / 214.36억 |
| join | 78.6 | 424.8 | 424.7 | 29.3 | 같다 |
| sort | 36.7 | 78.2 | 79.1 | 26.9 | 같다 |
## 만든 것
- **함께 도는 중첩 루프.** 묶음의 몸체에 있는 `LOOP`의 회차를 레인마다 함께 돈다. 레인마다 회차 수가 다르면(`for k in 0 .. i`)
회차 t의 마스크는 회차가 남은 레인이다. `BREAK`를 탄 레인은 그 루프의 남은 회차에서 빠지고, 루프가 끝나면 다른 레인과 함께 바깥
몸체를 이어 간다. 슬롯은 회차가 열릴 때 쓰인다(회차 0에서는 아래 끝 그대로라서 −0도 그대로다). 안쪽 회차마다 그 루프의 작업량
(블록 길이 + 1)을 레인마다 센다. 묶음의 끝에서 남은 예산과 견주고, 넘으면 아무것도 바꾸지 않고 실행기에 넘긴다. 한 겹까지만 묶는다.
- **모으기.** 몸체에서 `x = x op e`(op는 `+`, `min`, `max`)로만 읽고 쓰는 지역 변수는 모으기다. 레인마다 op의 항등원에서 시작한다.
합의 항등원은 −0이다(−0 + e는 e다). 끝에서 회차 차례대로 합친다. 한 레인이 한 번만 더하면 회차마다 더한 것과 비트까지 같다. 여러
번 더하는 레인이 있으면, 모두 정수이고 2^53 안일 때만 받는다(그래야 묶는 차례가 답을 바꾸지 않는다). 아니면 묶음이 회차들을
돌려준다.
- **계획.** 로드 때 지역 변수마다 그 루프의 범위에서 "확실히 쓴 뒤 읽는가"를 본다. 안쪽 루프의 몸체는 제 범위를 갖는다. 그래서 안쪽
회차를 넘어 이어지는 값(roots의 `r`, matmul의 `s`)은 레인의 상태가 되고, 바깥 회차를 넘는 값은 모으기여야 한다.
- **레인 재사용.** 안쪽 회차가 끝날 때마다, 지역 변수와 모으기와 마스크와 중첩 상태가 쥐지 않은 레인 버퍼와 마스크를 다시 빈 목록에
넣는다(쓸어 담기). 그래서 회차가 64번이어도 레인 버퍼 24개 안에서 돈다.
## 다듬기: 측정이 가리킨 것
2단계를 처음 만들었을 때 roots는 16.8 ms였다. 프로파일에서 가장 큰 것은 유한 검사였다(17%). 벡터화는 돼 있었지만 산수와 따로
한 번 더 도는 루프였다. 검사를 산수 루프 안에서 지수 비트로 하게 했다. 둘째는 수 비교가 8바이트 0/1을 내서, 분기가 레인마다 값의
꼴을 물어 다시 읽던 것이었다(8%). 비교가 4바이트 0/1 레인을 내게 해서 그대로 마스크가 되게 했다. 셋째는 바깥 루프의 값(아핀)을 안쪽
회차마다 수 레인으로 다시 만들던 것이었다(7.6%). 묶음마다 한 번만, 그것도 필요할 때만 만들게 했다. 처음에는 묶음마다 미리 만들게
해서 knapsack이 13.8에서 17.9 ms로 느려졌다(그 루프는 필요 없다). 그 밖에 아무 레인도 빠지지 않은 동안은 살아 있는 레인의 마스크를
만들지 않고, 작은 정수를 세는 모으기는 2^53 검사를 건너뛴다. roots 16.8 → 9.1 ms, matmul 68 → 50 ms.
## 뜻과 맞음
- 생성기에 `nest` 꼴을 더했다. 바깥 루프 안에 회차 수가 레인마다 다른 안쪽 루프가 있고, 그 안에 `break`, 회차를 넘는 지역 변수,
분수가 섞인 안팎의 모으기(`ra`, `rb`, `rc`)가 있다. 시드 1, 2, 3, 5, 23의 프로그램 685개가 세 길(묶음, 실행기만, 기계어)에서 같았다.
시드 23에서는 137개 중 53개 모듈에서 묶음 4만 1,554개(419만 회차)가 돌았다. 그중 4만 142개가 중첩 루프를, 4만 944개가 모으기를
품었다.
- `NESTED_SOURCE`: Newton 걸음과 `break`, 회차마다 분수 하나의 합, 레인마다 0–6회차인 안쪽 루프에서 어떤 레인의 회차에만 나는 0
나누기, `max`와 `min`, 레인마다 분수 여럿의 합(묶음이 돌려준다), −0의 합, 격자의 합을 담았다. 작은 예산 둘도 돈다.
- 단위 시험(실행기 모드)이 통과했다.
## 다음
- **matmul.** 안쪽 회차마다 해석하는 명령을 줄인다. 하나는 회차에 따라 바뀌지 않는 계산(`i * n`)을 루프 밖으로 끌어내는 것이고,
하나는 합친 연산이다. "읽어서 곱해 더하기"는 한 연산이 될 수 있다.
- **점화식(5단계)과 덧붙이기(4단계).** matmul, knapsack, join의 표를 만드는 루프가 여기에 걸린다. 지금은 실행기에서 돈다.
- **join과 BFS.** 키로 모으기와 차례대로 흩어 더하기(3단계), `EACH`와 덧붙이기(4단계)가 필요하다.
|
