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.
21	import Base
22	import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
23	import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
24	import 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).
30	type 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).
34	type 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).
39	type 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 `!(`.
50	type 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).
57	def 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`.
65	def 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.
79	def 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`.
89	def 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`.
99	def 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.
123	def 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 "".
137	def 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`.
147	def 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.
175	def 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.
183	def 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.
188	def 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.
206	def 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	
234	def 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	
241	def 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	
251	def 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	
259	def 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	
266	def 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	
275	def 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.
289	def 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.
303	def 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.
315	def 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	
328	def 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.
336	def 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	
345	def 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	
353	def 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	
362	def 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	
368	def 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.
377	def 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`).
401	def 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.
417	def 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	
436	def 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.
453	def 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	
483	def 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	
499	def rule() -> Lint.Rule:
500	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}