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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
# 132 — 묶음 실행기의 바닥과 그 너머: 비용의 세 자리, 문헌, 근본적인 길 (연구)
2026-10-08. [131](131-batch-executor-general-cuts.md)까지 범용 장치로 깎아 BFS가 기계어의 약 3배에서 멈췄다. 사용자는
더 깎기 전에 근본적인 해법을 Pure의 철학 위에서 묻고, 힘들면 연구를 먼저 하라고 했다. 이 글은 코드를 바꾸지 않는다. 비용이
어디에 있는지를 재고, 같은 문제를 다룬 문헌을 읽고, 길을 셋으로 나누어 철학의 잣대로 재고, 결정할 실험 하나를 적는다.
## 쉬운 말로
- **문제는 "연산마다 레인을 한 번 훑는 꼴" 자체다.** 묶음 실행기는 명령 하나를 레인 1024개에 한 번에 하고, 그 결과를 메모리의
레인 배열에 쓴다. 다음 명령이 그것을 다시 읽는다. 기계어(JIT)는 같은 값을 레지스터에 두고 다음 연산으로 넘긴다. 요소당 명령이
묶음은 4–12개, 기계어는 1–2개다. 이것은 구현의 흠이 아니라 꼴의 값이고, 데이터베이스 쪽 문헌이 같은 수를 잰다(아래).
- **비용의 자리는 셋이다.** 요소마다(레인 훑기), 묶음마다(묶음을 열 때마다 블록을 다시 읽고 꼴을 정하는 값, 약 6,500 명령),
후보마다(걸러내기 뒤 차례대로 하는 꼬리, 약 250 명령). 셋 가운데 범용으로 거의 다 없앨 수 있는 것이 둘째다. 셋째는 리스트 쪽
C라 줄일 수 있다. 첫째가 바닥이다.
- **근본적인 길은 "레지스터 타일"이다.** 레인 1024개를 명령마다 훑는 대신, 레인 4–16개를 레지스터에 올려 두고 몸체의 명령을 그
타일에 차례로 다 적용한 뒤 다음 타일로 간다. 값이 메모리를 오가지 않는다. 명령마다 내는 디스패치는 타일마다 내므로 그 값이
관건이다(Ertl & Gregg가 잰 것). 실행 시간에 코드를 만들지 않고, C 컴파일러가 가는 곳 어디서나 같다. 실행기(타일 1)와
묶음 실행기(타일 N)가 한 기계가 된다. 그러나 C 컴파일러가 타일을 레지스터에 붙들어 두는지는 재 보기 전에는 모른다.
- **그래서 결정할 실험 하나를 제안한다.** 041처럼 작은 C 시제품으로 세 몸체(배낭의 안쪽, BFS의 프런티어, roots의 뉴턴)를 타일로
돌려 요소당 사이클을 기계어와 견준다. 기준은 셋 모두 기계어의 1.3배 안이다. 넘지 못하면 이 길은 답이 아니다. 반나절이다.
## 잰 것: 비용의 세 자리
빌드 `b9`(`735ba81`), [131](131-batch-executor-general-cuts.md)과 같은 방법.
### 요소마다
BFS 간선당 112개 가운데 약 45개가 레인 훑기다(`to` 모으기 12, 비트로 묻기 11, 뒤집어 가르기와 고르기 7, 덩어리 만들기 7,
나머지). 각각은 요소마다 적재, 검사, 저장을 하는 범용 루프다. 기계어는 간선당 38.5개로 몸체 전체를 한다. matmul의 안쪽 몸체는
명령 15개를 레인 200개에 하는데, 명령마다 레인 배열을 읽고 쓰므로 15번 오간다. 기계어는 레지스터에서 한다(14 ms 대 40 ms).
### 묶음마다
같은 몸체를 레인 1024개와 256개로 돌려 명령의 차를 묶음 수의 차로 나눴다(`costs/sum0`, `ops0`: 회차 1,024,000, 묶음 1,000과
4,000).
| 모듈 | 1024 레인 | 256 레인 | 묶음마다 |
|---|---:|---:|---:|
| `sum0` (회차를 세는 합) | 4,789만 명령 / 1,621만 사이클 | 6,886만 / 2,345만 | **6,990 명령 / 2,410 사이클** |
| `ops0` (`let` 하나와 `max`) | 6,641만 / 3,036만 | 8,534만 / 3,683만 | 6,310 / 2,160 |
묶음 하나를 여는 데 약 6,500 명령, 약 1 µs다. 블록을 다시 읽어 지역 변수의 꼴을 정하고(`batch_run`의 앞머리, `recurrences`,
`sums`), 명령마다 값의 꼴(균일·아핀·레인)을 물어 가르고(`pass`), 끝에서 검사하고 쓴다(`settle`). 024는 처음부터 "묶음 프로그램은
루프마다 한 번 만든다"고 했는데, 그 단계를 만들지 않았다. 배낭에서는 이 값이 시간의 약 20%다(`batch_run` 10.7%, `pass` 8.5%).
**레인을 줄이면 느려진다.** 024는 레인 자리를 L1(64 KB) 안에 두려고 256 레인을 적었고, 1단계에서 디스패치 값을 나누려고
1024로 늘렸다. 지금 디스패치는 명령당 약 20 ns라 다시 256으로 줄여 봤다(`b9`의 코드, `BATCH`만 바꿈, 5번의 중앙값).
| 일 | 1024 | 512 | 256 |
|---|---:|---:|---:|
| knapsack | 11.4 ms | 15.7 | 24.5 |
| roots | 8.97 | 9.51 | 10.8 |
| join | 117 | 121 | 126 |
| matmul | 40.0 | 40.0 | 40.0 |
| BFS | 24.3 | 24.7 | 26.0 |
L1 가설은 틀렸다. 한 번의 훑기가 닿는 버퍼는 둘셋(24 KB)이라 어차피 L1 안이고, 느려지는 것은 묶음마다의 고정 값이 네 배가
되기 때문이다. Kersten 등도 벡터 크기 1K–4K가 가장 좋고 64 아래와 64K 위가 많이 나쁘다고 잰다(아래).
### 후보마다
걸러내기 뒤 차례대로 하는 꼬리(모은 회차의 기록 50, 결정 90, 넣기 110)가 후보 하나에 약 250 명령이다. 기계어는 같은 일(비트
묻기, DENSE에 더하기, 큐에 덧붙이기)을 약 100개로 한다. 리스트 쪽 C의 일이라 줄일 수 있지만, 간선당 26개 몫이다.
### knapsack과 matmul의 10%
131에서 두 일이 약 10% 느려진 것도 둘째 자리의 일이다. `pass`가 커져 인라인과 배치가 바뀌었다. 묶음 프로그램을 한 번 만들면
`pass`의 꼴 묻기가 사라져 이 값도 같이 사라진다.
## 문헌: 같은 문제를 다룬 곳
묶음 실행기는 데이터베이스의 "벡터 단위 실행"(vector-at-a-time)과 같은 꼴이다. 그쪽은 20년을 쟀다.
- **MonetDB/X100**(Boncz, Zukowski, Nes, CIDR 2005). 튜플 하나씩의 해석 값을 벡터(약 1,000개, 캐시 안)로 나누고, 연산마다
타입에 특화한 원시 루프를 돈다. 우리의 레인 배열은 그들의 벡터, 우리의 `binary`·`find`는 그들의 원시 루프다. 그들도 벡터가
캐시를 넘으면 느려진다고 적었다.
- **Kersten, Leis, Kemper, Neumann, Pavlo, Boncz**(VLDB 2018, "Everything You Always Wanted to Know About Compiled and
Vectorized Queries"). 같은 시스템 안에 벡터 해석(Tectorwise)과 코드 생성(Typer, HyPer 꼴)을 둘 다 만들어 견줬다. TPC-H SF=1,
튜플당 사이클/명령: Q1 Typer 34/68 대 TW 59/162, Q6 11/20 대 11/15, Q3 25/21 대 24/42, Q9 74/42 대 56/76, Q18 30/46 대 48/102.
결론은 "둘 다 효율적이고 꽤 가깝다. 코드 생성은 계산이 많고 캐시에 드는 일에서 명령이 적다(중간값을 레지스터에 둔다). 벡터
해석은 캐시 미스를 숨기는 데 조금 낫다." 벡터 해석의 남는 명령은 "원시 루프의 결과를 벡터에 쓰고 읽는 적재·저장"이라고 명시한다.
우리 BFS의 112 대 38.5(2.9배)는 그들의 Q1(2.4배)과 같은 결이다. 벡터 크기는 1K–4K가 가장 좋다고 잰다.
- **Sompolski, Zukowski, Boncz**(DaMoN 2011, "Vectorization vs. Compilation in Query Execution"). 루프 전체를 컴파일하는 쪽이
벡터 해석보다 못한 경우 셋을 들고, 둘을 섞으라고 한다. 컴파일한 조각을 벡터 처리의 벽돌로 쓰거나, 벡터의 원칙을 컴파일한
계획에 넣거나.
- **Gubner, Boncz**(ADMS 2017, "Exploring Query Execution Strategies for JIT, Vectorization and SIMD"). 벡터 해석에서 집계를
메모리의 집계 표가 아니라 레지스터에서 하는 "in-register aggregation"으로 Q1에서 HyPer의 JIT보다 빨라졌다고 적는다. 값을
레지스터에 두는 것이 벡터 해석의 남은 길이라는 뜻이다.
- **Photon**(Databricks, SIGMOD 2022). 코드 생성 대신 벡터 해석을 택했고, 묶음마다 데이터의 성질을 보고 특화한 길을 고른다
(우리의 값 꼴 균일·아핀·레인과 4바이트 열이 그것이다).
- **Ertl, Gregg**(JILP 2003, "The Structure and Performance of Efficient Interpreters"). 해석기의 시간 절반 이상이 간접 분기의
예측에 달려 있고, 스레디드 코드(핸들러 끝마다 다음으로 뛰기)가 switch보다 거의 두 배 빠르다. 레지스터 타일 해석의 디스패치
값은 여기서 나온다.
Pure가 그들과 다른 것: 회차 사이의 의존(쓰기를 끝으로 미루고 검사한다), 결함이 제 회차에서 나야 한다, 작업량을 회차마다 센다,
질의 최적화기가 없다. 그래서 그들의 수를 그대로 가져올 수는 없지만, 꼴의 값(요소마다의 적재·저장)은 같다.
## 길들과 철학의 잣대
잣대는 둘이다. "어떤 관습적인 층을 없애는가"([000](000-working-method.md), 추상의 압축)와 "실행 시간에 코드를 만들지 않고,
C 컴파일러가 가는 곳 어디서나 같고, 메모리를 적게 쓴다"([024](../design/024-batch-executor.md)).
### A. 묶음 프로그램을 로드 때 한 번 (024의 못 만든 단계)
루프마다 로드 때 한 번, 명령마다 피연산자의 꼴과 폭, 묶음마다 할 검사, 미룬 효과의 차례를 정해 둔다. 묶음을 열 때는 그 프로그램을
돈다. 둘째 자리(묶음마다 약 6,500 명령)가 거의 사라지고 `pass`의 꼴 묻기도 사라진다. 범용이고, 아래 B의 전제이기도 하다
(B도 프로그램이 있어야 한다). 바닥(첫째 자리)은 건드리지 않는다.
### B. 레지스터 타일 해석 (근본적인 길)
몸체의 명령을 레인 4–16개의 타일에 차례로 적용한다. 타일은 NEON 레지스터(4바이트 넷, 8바이트 둘)에 있고, 몸체의 임시 값은
고정된 레지스터 더미(v0..v7)에 있다. 명령은 C의 레이블이고(계산된 goto), 레이블은 더미의 깊이마다 하나씩 빌드 때 스크립트가
만든다(연산 40 × 깊이 8). 분기는 타일의 마스크다. 레인마다 다른 읽기(모으기, 비트 묻기, 찾기)는 타일 안에서 스칼라 넷이다.
- 없애는 층: 실행기(회차마다 해석)와 묶음 실행기(명령마다 훑기)가 "타일 크기"의 차이로 한 기계가 된다. 기계어는 필요 없어진다.
024가 바란 그림이다.
- 지키는 것: 실행 시간에 코드를 만들지 않는다. 메모리는 레인 배열 200 KB 대신 레지스터와 작은 타일 버퍼다.
- 셈: 몸체 15 명령, 타일 8이면 디스패치 15 × 약 5 사이클(Ertl & Gregg, 잘 예측될 때) / 8 레인 ≈ 9 사이클/레인, 연산 15 × 약
1 = 15, 합 약 24 사이클/레인. 타일 16이면 약 20. 기계어의 BFS는 간선당 19 사이클, 지금 묶음은 57이다. 되면 기계어의
1.1–1.4배다. 안 되는 경우: C 컴파일러가 레이블 사이에서 더미를 레지스터에 두지 못하고 스택으로 내리면 요소마다 적재·저장이
돌아와 지금과 같아진다. 그래서 재 보기 전에는 모른다.
- 뜻은 그대로다: 타일마다의 깃발(검사), 미룬 쓰기, 결함의 회차. 묶음 실행기의 규칙(의존 거리, 걸러내기, 고르기)은 타일에도
그대로 든다.
### C. 합친 연산의 표
자주 나오는 명령 짝을 빌드 때 C 루프 하나로 만든다. 바닥을 짝의 수만큼만 낮춘다. 사용자가 범용이 아니라고 했다. 제외한다.
### D. 모듈을 C로 미리 컴파일
`aup`가 C를 내고 기기의 C 컴파일러로 묶는다. 기계어를 싣는 셈이라 ".pmod 하나가 어디서나 같다"와 안전의 자리를 바꾼다. 제외한다.
### E. 후보 꼬리의 C
리스트 쪽에서 폭 검사를 한 번에 하고 비트와 칸을 함께 쓰면 후보당 250을 100 가까이로 줄일 수 있다. 범용이지만 간선당 26개의
몫이다. A, B와 독립이다.
## 결정할 실험
기준을 먼저 적는다. **세 몸체 모두에서 요소당 사이클이 기계어의 1.3배 안이면 B를 만든다. 하나라도 넘으면 B는 답이 아니고,
A와 E를 만들고 기계어를 남긴다.**
`research/experiments/042-tiles/`에 041처럼 런타임을 건드리지 않는 C 시제품을 둔다.
1. 몸체 셋: 배낭의 안쪽 루프(아핀 읽기, 비교, 마스크 쓰기), BFS의 프런티어(행 모으기, 비트 묻기, 가르기, 후보 모으기),
roots의 뉴턴 걸음(레인마다 다른 횟수, `break`).
2. 타일 4, 8, 16. 디스패치는 계산된 goto. 더미는 고정 변수. 빈 연산만 돌려 디스패치의 바닥을 따로 잰다.
3. 같은 프로세스에서 지금의 묶음 방식(연산마다 훑기)과 C 바닥을 함께 돌린다. 기계어의 수는 `search-run`과 스위트의 것이다.
요소당 명령과 사이클(`icount`).
4. `objdump`로 더미가 레지스터에 있는지, 스택으로 내려가는지 본다. 내려가면 함수를 나누거나 더미를 줄여 다시 잰다.
반나절이다. 결과가 기준을 넘으면 B의 설계(025)를 쓰고, 넘지 못하면 그 수를 적고 A와 E로 간다.
## 결과 (2026-10-08, [133](133-register-tiles-measured.md))
실험을 돌렸다. roots는 기계어의 0.71배로 기준을 넘었고, 배낭은 4배, BFS는 2.4배로 넘지 못했다(NEON에 모아 읽기가 없어 레인마다
꺼내고 넣는 값). 같은 실험에서 지금의 꼴(연산마다 훑기)을 꽉 짜면 BFS가 기계어의 1.2배, 배낭이 0.4배였다. 그래서 B는 접고 A를
끝까지 간다: 꼴이 아니라 구현이 3배였다.
## 추천 (실험 전에 적은 것)
A는 어느 길에서나 필요하고 범용이므로 먼저 만들어도 된다. B는 실험 뒤에 정한다. 지금 가진 수로 보면 B가 유일한 근본적인 길이고,
문헌(Gubner & Boncz의 레지스터 집계, Sompolski의 "벽돌")은 값을 레지스터에 두는 것이 벡터 해석의 남은 길이라는 데 모인다.
## 출처
- [MonetDB/X100: Hyper-Pipelining Query Execution](https://www.cidrdb.org/cidr2005/papers/P19.pdf)
- [Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask](https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf)
- [Vectorization vs. Compilation in Query Execution](https://dl.acm.org/doi/10.1145/1995441.1995446)
- [Exploring Query Execution Strategies for JIT, Vectorization and SIMD](https://t1mm3.github.io/assets/papers/adms17.pdf)
- [Photon: A Fast Query Engine for Lakehouse Systems](https://people.eecs.berkeley.edu/~matei/papers/2022/sigmod_photon.pdf)
- [The Structure and Performance of Efficient Interpreters](https://jilp.org/vol5/v5paper12.pdf)
|
