performance/gpu_fit.bend
bend-lint-rules@0.2.1.0 · 352 lines · 0 definitions
1# performance/gpu_fit: a call that may run faster on the CPU than on the GPU, or the reverse: a `!` call
2# (it runs on the GPU, if there is one) of a definition under which no parallel let runs, so one GPU
3# thread runs it alone; a `!` call of a definition that forks but receives data, not only numbers; or a
4# call of a definition that forks over numbers only, made without `!`, from a definition that does not
5# fork.
6# Heuristics: measured on a discrete GPU (CUDA) against its machine's CPU (`--gpu off`): a `!` on
7# BendSR's compute_mae, a list walk that never forks, took 6.5 s against 0.08 s without the `!` (0.11 s
8# against 0.07 s on the CPU); Bend's slash boss draw, which forks over data, took 10.5 ms against 7.4 ms;
9# the GPU also costs a fixed 0.3 to 0.8 s to start there, after which numeric work is nearly free: a
10# numeric fork tree of 16,384 leaves took 0.95 s against 3.6 s on the CPU, but one that took 0.06 s on
11# the CPU took 0.49 s. The same draw takes 8 ms on an Apple M-series GPU (unified memory), and a high-end
12# desktop GPU drew it at 17 to 19 FPS ("bend guide shaders"): a discrete GPU pays for each page it reads
13# across PCIe, whatever its speed. The JS lane has no GPU. The hint to add a `!` does not see a `!` in a
14# caller: in Bend's benchmarks, which run under a `!` at their top, its 7 hints were all wrong, and a `!`
15# in a `!` was up to 4.6x slower. Nor does it see a fork before the call in the caller's evaluation,
16# which keeps the `!` on the CPU (performance/bang_after_fork). It follows calls through the program's
17# files; a definition outside them is Base's, where only Image.free (and Image.drop, through it) forks.
18# Numbers are U32, I32, F32, Nat, Bool, Char (and their 64-bit forms), and a record of numbers only,
19# defined in the program's files; anything else is data. Erased and template parameters do not count. A
20# `!` call of a definition that returns Unit is left to performance/drop_in_bang.
21import Base
22import bend-lint-api@0.2.1.0/linter/lint.bend as Lint
23import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
24import bend-lint-api@0.2.1.0/shared/names.bend as Names
25import bend-lint-api@0.2.1.0/shared/sets.bend as Sets
26
27# Types
28# =====
29
30# A field of a datatype: the datatype, and the field's type as one name ("" if it is not one name).
31type Slot is Data:
32 Slot{owner: String, ty: String}
33
34# What judging a file's calls reads: the program's definitions, by the name the check gives them; those under which a
35# parallel let runs (see program.under); the fields of its datatypes; and where the file writes `!(`.
36type Program is Data:
37 Program{
38 defs: Map<&2, Maybe<&2, Lint.Def>>,
39 under: Set(),
40 slots: List<&2, Slot>,
41 bangs: List<&2, U32>
42 }
43
44# Functions
45# =========
46
47# The fields of the datatypes among `nodes` and under them (of `current`, the datatype they are under), onto `out`.
48def slots(nodes: List<&2, Lint.Node>, +current: String, out: List<&2, Slot>) -> List<&2, Slot>:
49 match nodes:
50 case Nil{}:
51 out
52 case Con{Lint.Node{Lint.Datatype{t}, n, s, kids, f}, rest}:
53 slots(rest, current, slots(kids, t, out))
54 case Con{Lint.Node{Lint.Constructor{t}, n, s, kids, f}, rest}:
55 slots(rest, current, slots(kids, current, out))
56 case Con{Lint.Node{Lint.Field{b, q}, n, s, kids, f}, rest}:
57 slots(rest, current, Slot{current, Lint.type_name(kids)} <> out)
58 case Con{node, rest}:
59 slots(rest, current, out)
60
61# Whether a call of `t` (`info`, if the program defines it) only frees its inputs: it returns Unit, as Base's
62# Image.drop, Image.free and Image.sink do.
63def is_drop(info: Maybe<&2, Lint.Def>, t: String) -> Bool:
64 match info:
65 case Some{Lint.Def{d, ps, fs, cs, r}}:
66 String.eq(r, "Unit")
67 case None{}:
68 List.contains(~String, ~String.eq, ["Image.drop", "Image.free", "Image.sink"], t)
69
70def program.slots(sources: List<&2, Lint.Source>, out: List<&2, Slot>) -> List<&2, Slot>:
71 match sources:
72 case Nil{}:
73 out
74 case Con{Lint.Source{path, ns, text, nodes}, rest}:
75 program.slots(rest, slots(nodes, "", out))
76
77def is_scalar(t: String) -> Bool:
78 List.contains(
79 ~String,
80 ~String.eq,
81 ["U32", "I32", "F32", "Nat", "Bool", "Char", "U64", "I64", "F64", "Unit"],
82 t
83 )
84
85def fields(slots: List<&2, Slot>, +t: String, out: List<&2, String>) -> List<&2, String>:
86 match slots:
87 case Nil{}:
88 out
89 case Con{Slot{o, ty}, rest}:
90 fields(rest, t, Lists.push(String, Lists.when(String, String.eq(o, t), ty), out))
91
92def is_known(slots: List<&2, Slot>, hit: Bool, +t: String) -> Bool:
93 match slots hit:
94 case _ True{}:
95 True{}
96 case Nil{} False{}:
97 False{}
98 case Con{Slot{o, ty}, rest} False{}:
99 is_known(rest, String.eq(o, t), t)
100
101def is_flat.expand(
102 known: Bool,
103 t: String,
104 rest: List<&2, String>,
105 slots: List<&2, Slot>
106) -> Maybe<&2, List<&2, String>>:
107 match known:
108 case True{}:
109 Some{fields(slots, t, rest)}
110 case False{}:
111 None{}
112
113# What is left to check after `t`: its fields, if it is a datatype; nothing more, if it is a number;
114# none (data), else.
115def is_flat.next(
116 number: Bool,
117 +t: String,
118 rest: List<&2, String>,
119 +slots: List<&2, Slot>
120) -> Maybe<&2, List<&2, String>>:
121 match number:
122 case True{}:
123 Some{rest}
124 case False{}:
125 is_flat.expand(is_known(slots, False{}, t), t, rest, slots)
126
127# Whether the types of `todo` are numbers, or records of numbers. `fuel` bounds the steps, so a
128# recursive type, which never ends, is data.
129def is_flat(fuel: Nat, todo: Maybe<&2, List<&2, String>>, +slots: List<&2, Slot>) -> Bool:
130 match fuel todo:
131 case _ None{}:
132 False{}
133 case _ Some{Nil{}}:
134 True{}
135 case 0n _:
136 False{}
137 case 1n+f Some{Con{+t, rest}}:
138 is_flat(f, is_flat.next(is_scalar(t), t, rest, slots), slots)
139
140# The first parameter of `params` that is data, if one is.
141def data(
142 params: List<&2, Lint.Param>,
143 found: Maybe<&2, Lint.Param>,
144 +slots: List<&2, Slot>
145) -> Maybe<&2, Lint.Param>:
146 match params found:
147 case _ Some{param}:
148 Some{param}
149 case Nil{} None{}:
150 None{}
151 case Con{Lint.Param{n, +ty}, rest} None{}:
152 data(
153 rest,
154 Lists.when(Lint.Param, Bool.not(is_flat(64n, Some{[ty]}, slots)), Lint.Param{n, ty}),
155 slots
156 )
157
158# The definitions among `names` that a parallel let is in, onto `out`.
159def forking(
160 names: List<&2, String>,
161 +defs: Map<&2, Maybe<&2, Lint.Def>>,
162 out: List<&2, String>
163) -> List<&2, String>:
164 match names:
165 case Nil{}:
166 out
167 case Con{+t, rest}:
168 forking(
169 rest,
170 defs,
171 Lists.push(
172 String,
173 Lists.when(String, Lint.Def.forks(Names.find(Lint.Def, defs, t)), t),
174 out
175 )
176 )
177
178# The definitions under which a parallel let runs: in them, or under what they call. Of Base's, Image.free forks, and
179# Image.drop, through it.
180def program.under(sources: List<&2, Lint.Source>, +defs: Map<&2, Maybe<&2, Lint.Def>>) -> Set():
181 Lint.Program.callers(
182 sources,
183 defs,
184 Set.from_list(
185 forking(Map.keys(&2, Maybe<&2, Lint.Def>, defs), defs, ["Image.free", "Image.drop"])
186 )
187 )
188
189# Where `text` writes `!(`, from offset `at`: the end of each bang's name.
190def bangs(s: String, +at: U32, out: List<&2, U32>) -> List<&2, U32>:
191 match s:
192 case SNil{}:
193 out
194 case SCon{'!', SCon{'(', rest}}:
195 bangs(rest, (at + 2: U32), at <> out)
196 case SCon{c, rest}:
197 bangs(rest, (at + 1: U32), out)
198
199def alone(+callee: String) -> String:
200 callee
201 ++ "! runs on one GPU thread, alone: no parallel let runs under "
202 ++ callee
203 ++ ". GPU: measured 6.5 s for a list walk of BendSR, against 0.08 s without the `!`. CPU (`--gpu off`): 1.6x slower with the `!`. JS: no GPU, so no change. Confidence: high, as one GPU thread is much slower than a CPU core. Remove the `!`, or fork inside "
204 ++ callee
205 ++ " with a parallel let. If a timing shows the `!` faster here, expect this finding."
206
207def slower(callee: String, param: Lint.Param) -> String:
208 match param:
209 case Lint.Param{name, +ty}:
210 callee
211 ++ "! receives data ("
212 ++ name
213 ++ Bool.pick(String, String.is_empty(ty), "", ": " ++ ty)
214 ++ "), which a discrete GPU reads across PCIe, page by page. GPU: on discrete GPUs (CUDA), measured slower than `--gpu off` for Bend's slash boss draw (1.4x) and for portal-bend; with unified memory (Apple M-series), the GPU wins that draw. CPU (`--gpu off`): not measured. JS: no GPU, so no change. Confidence: medium, as it depends on the machine. Time the program with and without `--gpu off`. If the GPU wins, expect this finding."
215
216def faster(+callee: String) -> String:
217 callee
218 ++ " forks over numbers only, so `"
219 ++ callee
220 ++ "!(..)` can run faster on the GPU, if the call is long: a discrete GPU costs a fixed 0.3 to 0.8 s to start, then numeric work is nearly free. GPU: measured 3.8x faster for a fork tree that took 3.6 s on the CPU, and 8x slower for one that took 0.06 s. CPU (`--gpu off`): not measured. JS: no GPU, so no change. Confidence: low, as it depends on how long this call runs, and on the machine. Add the `!` if this call takes over a second on the CPU, and time both; a fork before it in the same evaluation keeps it on the CPU (performance/bang_after_fork). If the call is short, or already runs under a `!` of a caller (a `!` in a `!` measured up to 4.6x slower), expect this finding."
221
222def Def.target(info: Maybe<&2, Lint.Def>) -> String:
223 match info:
224 case Some{Lint.Def{t, params, forks, calls, r}}:
225 t
226 case None{}:
227 ""
228
229# The finding about a call of `info` without `!`, if it forks over numbers only and the caller does not
230# fork.
231def unbanged(
232 info: Maybe<&2, Lint.Def>,
233 callee: String,
234 +caller: Maybe<&2, Lint.Def>,
235 slots: List<&2, Slot>,
236 span: Maybe<&2, Lint.Span>
237) -> List<&2, Lint.Finding>:
238 match info:
239 case Some{Lint.Def{t, params, True{}, calls, r}}:
240 Lint.finding(
241 Lint.Hint{},
242 Bool.not(
243 Maybe.is_some(&2, Lint.Param, data(params, None{}, slots))
244 )
245 && Bool.not(Lint.Def.forks(caller))
246 && Bool.not(String.eq(t, Def.target(caller))),
247 span,
248 faster(callee)
249 )
250 case _:
251 []
252
253# The finding about a `!` call: of a definition under which no parallel let runs (`forks` is false), or of one that
254# forks and receives data (`param`).
255def banged.of(
256 forks: Bool,
257 param: Maybe<&2, Lint.Param>,
258 callee: String,
259 span: Maybe<&2, Lint.Span>
260) -> List<&2, Lint.Finding>:
261 match forks param:
262 case False{} _:
263 Lint.finding(Lint.Warning{}, True{}, span, alone(callee))
264 case True{} Some{p}:
265 Lint.finding(Lint.Information{}, True{}, span, slower(callee, p))
266 case True{} None{}:
267 []
268
269# The finding about a `!` call of a definition of the program (`info`), unless the call only frees (`drop`):
270# performance/drop_in_bang reports that.
271def banged(
272 info: Maybe<&2, Lint.Def>,
273 drop: Bool,
274 callee: String,
275 under: Set(),
276 slots: List<&2, Slot>,
277 span: Maybe<&2, Lint.Span>
278) -> List<&2, Lint.Finding>:
279 match info drop:
280 case Some{Lint.Def{t, params, forks, calls, r}} False{}:
281 banged.of(Sets.has(under, t), data(params, None{}, slots), callee, span)
282 case _ _:
283 []
284
285def judged(
286 bang: Bool,
287 info: Maybe<&2, Lint.Def>,
288 drop: Bool,
289 callee: String,
290 caller: Maybe<&2, Lint.Def>,
291 under: Set(),
292 slots: List<&2, Slot>,
293 span: Maybe<&2, Lint.Span>
294) -> List<&2, Lint.Finding>:
295 match bang:
296 case True{}:
297 banged(info, drop, callee, under, slots, span)
298 case False{}:
299 unbanged(info, callee, caller, slots, span)
300
301# The finding about an application below `path`, if its function is a definition of the program.
302def visit(
303 +program: Program,
304 +path: List<&2, Lint.Above>,
305 +node: Lint.Node
306) -> List<&2, Lint.Finding>:
307 match program node:
308 case Program{
309 +defs,
310 under,
311 slots,
312 bangs
313 } Lint.Node{
314 Lint.Application{},
315 n,
316 span,
317 Con{Lint.Node{Lint.Reference{t}, callee, Some{Lint.Span{p, beg, end}}, k, f}, args},
318 facts
319 }:
320 judged(
321 List.contains(~U32, ~U32.is_eq, bangs, end),
322 Names.find(Lint.Def, defs, t),
323 is_drop(Names.find(Lint.Def, defs, t), t),
324 callee,
325 Names.find(Lint.Def, defs, Lint.Node.target(Lint.top(path, node))),
326 under,
327 slots,
328 span
329 )
330 case _ _:
331 []
332
333def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
334 +sources = Lint.Here.sources(here)
335 +defs = Lint.Program.defs(sources, Map.new(&2, Maybe<&2, Lint.Def>))
336 Lint.done(
337 Lint.visit(
338 ~Program,
339 ~Lint.Finding,
340 ~visit,
341 Program{
342 defs,
343 program.under(sources, defs),
344 program.slots(sources, []),
345 bangs(Lint.Here.text(here), 0, [])
346 },
347 Lint.Here.nodes(here)
348 )
349 )
350
351def rule() -> Lint.Rule:
352 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}