performance/gpu_fit.bend
bend-lint-rules@0.1.0.0 · 500 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.1.0.0/linter/lint.bend as Lint
23import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
24import bend-lint-api@0.1.0.0/shared/names.bend as Names
25
26# Types
27# =====
28
29# A field of a datatype: the datatype, and the field's type as one name ("" if it is not one name).
30type Slot is Data:
31 Slot{owner: String, ty: String}
32
33# A runtime parameter of a definition: its name, and its type as one name ("" if it is not one name).
34type Param is Data:
35 Param{name: String, ty: String}
36
37# A definition of the program: its name as the check names it, its runtime parameters, whether it forks, the
38# definitions it calls by name, and the type it returns, as one name ("" if it is not one name).
39type Def is Data:
40 Def{
41 target: String,
42 params: List<&2, Param>,
43 forks: Bool,
44 calls: List<&2, String>,
45 returns: String
46 }
47
48# What judging a file's calls reads: the program's definitions, by the name the check gives them; the fields of its
49# datatypes; and where the file writes `!(`.
50type Program is Data:
51 Program{defs: Map<&2, Maybe<&2, Def>>, slots: List<&2, Slot>, bangs: List<&2, U32>}
52
53# Functions
54# =========
55
56# The type the first of `nodes` writes, as one name, or "" for another form (an application, a list).
57def plain(nodes: List<&2, Lint.Node>) -> String:
58 match nodes:
59 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
60 t
61 case _:
62 ""
63
64# The fields of the datatypes among `nodes` and under them (of `current`, the datatype they are under), onto `out`.
65def slots(nodes: List<&2, Lint.Node>, +current: String, out: List<&2, Slot>) -> List<&2, Slot>:
66 match nodes:
67 case Nil{}:
68 out
69 case Con{Lint.Node{Lint.Datatype{t}, n, s, kids, f}, rest}:
70 slots(rest, current, slots(kids, t, out))
71 case Con{Lint.Node{Lint.Constructor{t}, n, s, kids, f}, rest}:
72 slots(rest, current, slots(kids, current, out))
73 case Con{Lint.Node{Lint.Field{b, q}, n, s, kids, f}, rest}:
74 slots(rest, current, Slot{current, plain(kids)} <> out)
75 case Con{node, rest}:
76 slots(rest, current, out)
77
78# Whether a parameter of this quantity is there at run time.
79def is_runtime(quantity: Lint.Quantity) -> Bool:
80 match quantity:
81 case Lint.Erased{}:
82 False{}
83 case Lint.Template{}:
84 False{}
85 case _:
86 True{}
87
88# The runtime parameters among a definition's nodes, in order, onto `out`.
89def params(nodes: List<&2, Lint.Node>, out: List<&2, Param>) -> List<&2, Param>:
90 match nodes:
91 case Nil{}:
92 List.reverse(&2, Param, out)
93 case Con{Lint.Node{Lint.Parameter{b, q}, n, s, kids, f}, rest}:
94 params(rest, Lists.push(Param, Lists.when(Param, is_runtime(q), Param{n, plain(kids)}), out))
95 case Con{node, rest}:
96 params(rest, out)
97
98# Whether a parallel let (two binders, at least) is among `nodes` or under them, or `found`.
99def forks(nodes: List<&2, Lint.Node>, found: Bool) -> Bool:
100 match nodes found:
101 case _ True{}:
102 True{}
103 case Nil{} False{}:
104 False{}
105 case Con{
106 Lint.Node{
107 Lint.Destructure{q},
108 n,
109 s,
110 Con{
111 Lint.Node{Lint.PatternVariable{a, aq}, an, as, ak, af},
112 Con{Lint.Node{Lint.PatternVariable{b, bq}, bn, bs, bk, bf}, more}
113 },
114 f
115 },
116 rest
117 } False{}:
118 True{}
119 case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
120 forks(rest, forks(kids, False{}))
121
122# The definition an application below `path` calls by name.
123def called.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, String>:
124 match node:
125 case Lint.Node{
126 Lint.Application{},
127 n,
128 s,
129 Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
130 f
131 }:
132 [t]
133 case _:
134 []
135
136# The type a definition's nodes say it returns, as one name, or "".
137def returned(nodes: List<&2, Lint.Node>) -> String:
138 match nodes:
139 case Nil{}:
140 ""
141 case Con{Lint.Node{Lint.Returns{}, n, s, kids, f}, rest}:
142 plain(kids)
143 case Con{node, rest}:
144 returned(rest)
145
146# The definitions among a file's nodes, by the name the check gives them, onto `out`.
147def defs(nodes: List<&2, Lint.Node>, out: Map<&2, Maybe<&2, Def>>) -> Map<&2, Maybe<&2, Def>>:
148 match nodes:
149 case Nil{}:
150 out
151 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +kids, f}, rest}:
152 defs(
153 rest,
154 Map.set(
155 &2,
156 Maybe<&2, Def>,
157 out,
158 t,
159 Some{
160 Def{
161 t,
162 params(kids, []),
163 forks(kids, False{}),
164 Lint.visit(~Unit, ~String, ~called.visit, Unit{}, kids),
165 returned(kids)
166 }
167 }
168 )
169 )
170 case Con{node, rest}:
171 defs(rest, out)
172
173# Whether a call of `t` (`info`, if the program defines it) only frees its inputs: it returns Unit, as Base's
174# Image.drop, Image.free and Image.sink do.
175def is_drop(info: Maybe<&2, Def>, t: String) -> Bool:
176 match info:
177 case Some{Def{d, ps, fs, cs, r}}:
178 String.eq(r, "Unit")
179 case None{}:
180 List.contains(~String, ~String.eq, ["Image.drop", "Image.free", "Image.sink"], t)
181
182# Whether Base's definition `t` forks: Image.free does, and Image.drop, through it.
183def is_base_fork(t: String) -> Bool:
184 List.contains(~String, ~String.eq, ["Image.free", "Image.drop"], t)
185
186# What is left to visit after `t`: none if a parallel let runs in it (the answer is found); `rest` if it was seen;
187# else `rest` and what `t` calls. A definition outside the program is Base's.
188def reaches.next(
189 info: Maybe<&2, Def>,
190 seen: Bool,
191 t: String,
192 rest: List<&2, String>
193) -> Maybe<&2, List<&2, String>>:
194 match info seen:
195 case _ True{}:
196 Some{rest}
197 case None{} False{}:
198 Bool.pick(Maybe<&2, List<&2, String>>, is_base_fork(t), None{}, Some{rest})
199 case Some{Def{d, ps, True{}, cs, r}} False{}:
200 None{}
201 case Some{Def{d, ps, False{}, cs, r}} False{}:
202 Some{Lists.onto(&2, String, cs, rest)}
203
204# Whether a parallel let runs under the definitions of `todo` (none: one was found): in them, or in what they call.
205# `fuel` bounds the steps; when it runs out, the answer is `unknown`, the one that makes the caller report nothing.
206def reaches(
207 fuel: Nat,
208 todo: Maybe<&2, List<&2, String>>,
209 +seen: List<&2, String>,
210 +defs: Map<&2, Maybe<&2, Def>>,
211 unknown: Bool
212) -> Bool:
213 match fuel todo:
214 case _ None{}:
215 True{}
216 case _ Some{Nil{}}:
217 False{}
218 case 0n _:
219 unknown
220 case 1n+f Some{Con{+t, rest}}:
221 reaches(
222 f,
223 reaches.next(
224 Names.find(Def, defs, t),
225 List.contains(~String, ~String.eq, seen, t),
226 t,
227 rest
228 ),
229 t <> seen,
230 defs,
231 unknown
232 )
233
234def program.slots(sources: List<&2, Lint.Source>, out: List<&2, Slot>) -> List<&2, Slot>:
235 match sources:
236 case Nil{}:
237 out
238 case Con{Lint.Source{path, ns, text, nodes}, rest}:
239 program.slots(rest, slots(nodes, "", out))
240
241def program.defs(
242 sources: List<&2, Lint.Source>,
243 out: Map<&2, Maybe<&2, Def>>
244) -> Map<&2, Maybe<&2, Def>>:
245 match sources:
246 case Nil{}:
247 out
248 case Con{Lint.Source{path, ns, text, nodes}, rest}:
249 program.defs(rest, defs(nodes, out))
250
251def is_scalar(t: String) -> Bool:
252 List.contains(
253 ~String,
254 ~String.eq,
255 ["U32", "I32", "F32", "Nat", "Bool", "Char", "U64", "I64", "F64", "Unit"],
256 t
257 )
258
259def fields(slots: List<&2, Slot>, +t: String, out: List<&2, String>) -> List<&2, String>:
260 match slots:
261 case Nil{}:
262 out
263 case Con{Slot{o, ty}, rest}:
264 fields(rest, t, Lists.push(String, Lists.when(String, String.eq(o, t), ty), out))
265
266def is_known(slots: List<&2, Slot>, hit: Bool, +t: String) -> Bool:
267 match slots hit:
268 case _ True{}:
269 True{}
270 case Nil{} False{}:
271 False{}
272 case Con{Slot{o, ty}, rest} False{}:
273 is_known(rest, String.eq(o, t), t)
274
275def is_flat.expand(
276 known: Bool,
277 t: String,
278 rest: List<&2, String>,
279 slots: List<&2, Slot>
280) -> Maybe<&2, List<&2, String>>:
281 match known:
282 case True{}:
283 Some{fields(slots, t, rest)}
284 case False{}:
285 None{}
286
287# What is left to check after `t`: its fields, if it is a datatype; nothing more, if it is a number;
288# none (data), else.
289def is_flat.next(
290 number: Bool,
291 +t: String,
292 rest: List<&2, String>,
293 +slots: List<&2, Slot>
294) -> Maybe<&2, List<&2, String>>:
295 match number:
296 case True{}:
297 Some{rest}
298 case False{}:
299 is_flat.expand(is_known(slots, False{}, t), t, rest, slots)
300
301# Whether the types of `todo` are numbers, or records of numbers. `fuel` bounds the steps, so a
302# recursive type, which never ends, is data.
303def is_flat(fuel: Nat, todo: Maybe<&2, List<&2, String>>, +slots: List<&2, Slot>) -> Bool:
304 match fuel todo:
305 case _ None{}:
306 False{}
307 case _ Some{Nil{}}:
308 True{}
309 case 0n _:
310 False{}
311 case 1n+f Some{Con{+t, rest}}:
312 is_flat(f, is_flat.next(is_scalar(t), t, rest, slots), slots)
313
314# The first parameter of `params` that is data, if one is.
315def data(
316 params: List<&2, Param>,
317 found: Maybe<&2, Param>,
318 +slots: List<&2, Slot>
319) -> Maybe<&2, Param>:
320 match params found:
321 case _ Some{param}:
322 Some{param}
323 case Nil{} None{}:
324 None{}
325 case Con{Param{n, +ty}, rest} None{}:
326 data(rest, Lists.when(Param, Bool.not(is_flat(64n, Some{[ty]}, slots)), Param{n, ty}), slots)
327
328def Def.forks(info: Maybe<&2, Def>) -> Bool:
329 match info:
330 case Some{Def{t, params, forks, calls, r}}:
331 forks
332 case None{}:
333 False{}
334
335# Where `text` writes `!(`, from offset `at`: the end of each bang's name.
336def bangs(s: String, +at: U32, out: List<&2, U32>) -> List<&2, U32>:
337 match s:
338 case SNil{}:
339 out
340 case SCon{'!', SCon{'(', rest}}:
341 bangs(rest, (at + 2: U32), at <> out)
342 case SCon{c, rest}:
343 bangs(rest, (at + 1: U32), out)
344
345def alone(+callee: String) -> String:
346 callee
347 ++ "! runs on one GPU thread, alone: no parallel let runs under "
348 ++ callee
349 ++ ". 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 "
350 ++ callee
351 ++ " with a parallel let. If a timing shows the `!` faster here, expect this finding."
352
353def slower(callee: String, param: Param) -> String:
354 match param:
355 case Param{name, +ty}:
356 callee
357 ++ "! receives data ("
358 ++ name
359 ++ Bool.pick(String, String.is_empty(ty), "", ": " ++ ty)
360 ++ "), 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."
361
362def faster(+callee: String) -> String:
363 callee
364 ++ " forks over numbers only, so `"
365 ++ callee
366 ++ "!(..)` 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."
367
368def Def.target(info: Maybe<&2, Def>) -> String:
369 match info:
370 case Some{Def{t, params, forks, calls, r}}:
371 t
372 case None{}:
373 ""
374
375# The finding about a call of `info` without `!`, if it forks over numbers only and the caller does not
376# fork.
377def unbanged(
378 info: Maybe<&2, Def>,
379 callee: String,
380 +caller: Maybe<&2, Def>,
381 slots: List<&2, Slot>,
382 span: Maybe<&2, Lint.Span>
383) -> List<&2, Lint.Finding>:
384 match info:
385 case Some{Def{t, params, True{}, calls, r}}:
386 Lint.finding(
387 Lint.Hint{},
388 Bool.not(
389 Maybe.is_some(&2, Param, data(params, None{}, slots))
390 )
391 && Bool.not(Def.forks(caller))
392 && Bool.not(String.eq(t, Def.target(caller))),
393 span,
394 faster(callee)
395 )
396 case _:
397 []
398
399# The finding about a `!` call: of a definition under which no parallel let runs (`forks` is false), or of one that
400# forks and receives data (`param`).
401def banged.of(
402 forks: Bool,
403 param: Maybe<&2, Param>,
404 callee: String,
405 span: Maybe<&2, Lint.Span>
406) -> List<&2, Lint.Finding>:
407 match forks param:
408 case False{} _:
409 Lint.finding(Lint.Warning{}, True{}, span, alone(callee))
410 case True{} Some{p}:
411 Lint.finding(Lint.Information{}, True{}, span, slower(callee, p))
412 case True{} None{}:
413 []
414
415# The finding about a `!` call of a definition of the program (`info`), unless the call only frees (`drop`):
416# performance/drop_in_bang reports that.
417def banged(
418 info: Maybe<&2, Def>,
419 drop: Bool,
420 callee: String,
421 defs: Map<&2, Maybe<&2, Def>>,
422 slots: List<&2, Slot>,
423 span: Maybe<&2, Lint.Span>
424) -> List<&2, Lint.Finding>:
425 match info drop:
426 case Some{Def{t, params, forks, calls, r}} False{}:
427 banged.of(
428 reaches(4096n, Some{[t]}, [], defs, True{}),
429 data(params, None{}, slots),
430 callee,
431 span
432 )
433 case _ _:
434 []
435
436def judged(
437 bang: Bool,
438 info: Maybe<&2, Def>,
439 drop: Bool,
440 callee: String,
441 caller: Maybe<&2, Def>,
442 defs: Map<&2, Maybe<&2, Def>>,
443 slots: List<&2, Slot>,
444 span: Maybe<&2, Lint.Span>
445) -> List<&2, Lint.Finding>:
446 match bang:
447 case True{}:
448 banged(info, drop, callee, defs, slots, span)
449 case False{}:
450 unbanged(info, callee, caller, slots, span)
451
452# The finding about an application below `path`, if its function is a definition of the program.
453def visit(
454 +program: Program,
455 +path: List<&2, Lint.Above>,
456 +node: Lint.Node
457) -> List<&2, Lint.Finding>:
458 match program node:
459 case Program{
460 +defs,
461 slots,
462 bangs
463 } Lint.Node{
464 Lint.Application{},
465 n,
466 span,
467 Con{Lint.Node{Lint.Reference{t}, callee, Some{Lint.Span{p, beg, end}}, k, f}, args},
468 facts
469 }:
470 judged(
471 List.contains(~U32, ~U32.is_eq, bangs, end),
472 Names.find(Def, defs, t),
473 is_drop(Names.find(Def, defs, t), t),
474 callee,
475 Names.find(Def, defs, Lint.Node.target(Lint.top(path, node))),
476 defs,
477 slots,
478 span
479 )
480 case _ _:
481 []
482
483def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
484 +sources = Lint.Here.sources(here)
485 Lint.done(
486 Lint.visit(
487 ~Program,
488 ~Lint.Finding,
489 ~visit,
490 Program{
491 program.defs(sources, Map.new(&2, Maybe<&2, Def>)),
492 program.slots(sources, []),
493 bangs(Lint.Here.text(here), 0, [])
494 },
495 Lint.Here.nodes(here)
496 )
497 )
498
499def rule() -> Lint.Rule:
500 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}