performance/gpu_fit.bend

bend-lint-rules@0.2.0.0 · 352 lines · 26 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.0.0/linter/lint.bend as Lint
23import bend-lint-api@0.2.0.0/shared/lists.bend as Lists
24import bend-lint-api@0.2.0.0/shared/names.bend as Names
25import bend-lint-api@0.2.0.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}}