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.2.2.0/linter/lint.bend as Lint
23	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
24	import bend-lint-api@0.2.2.0/shared/names.bend as Names
25	import bend-lint-api@0.2.2.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).
31	type 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 `!(`.
36	type 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`.
48	def 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.
63	def 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	
70	def 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	
77	def 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	
85	def 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	
92	def 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	
101	def 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.
115	def 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.
129	def 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.
141	def 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`.
159	def 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.
180	def 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.
190	def 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	
199	def 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	
207	def 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	
216	def 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	
222	def 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.
231	def 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`).
255	def 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.
271	def 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	
285	def 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.
302	def 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	
333	def 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	
351	def rule() -> Lint.Rule:
352	  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}