performance/missed_fork.bend
bend-lint-rules@0.1.0.0 · 513 lines · 0 definitions
1# performance/missed_fork: calls of a definition to itself that could run in parallel, but run one after
2# the other: two or more in one expression (`f(x) + f(y)`, `Node{f(x), f(y)}`), or in lets that follow
3# each other (`l = f(x)`, then `r = f(y)`), where no call uses the result of another.
4# Heuristics: Bend forks only the values of a parallel let (`a b = f(x) f(y)`), and its calls are
5# independent, as Bend is pure. Whether a fork pays depends on how much work each call does, which the
6# rule cannot see: measured on the CPU, forking a walk of a 1M-leaf tree, called 10 times, made it 2.5x
7# faster; forking the same walk of 1k-leaf trees, called 100,000 times in a loop, made it 3.9x slower;
8# forking a small expression tree that BendSR evaluates once per data point made it 230x slower. The JS
9# lane runs on one thread, so it does not gain. Calls in different values of Bool.pick, or on the two
10# sides of `&&` or `||`, are alternatives, not both needed (see performance/eager_branch): they do not
11# count together. Calls written the same way compute the same value, so they are left to
12# performance/repeated_call, which asks to compute it once (pow2(30): 0.1 s, against 0.6 s forked). It
13# skips a definition that returns IO: its calls build effects, they do not run them. A call inside
14# another call of itself, inside a lambda, or in a type, does not count.
15import Base
16import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
17import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
18import bend-lint-api@0.1.0.0/shared/strings.bend as Strings
19
20# Types
21# =====
22
23# What judging one definition reads: its name as the check names it and as written, whether it returns IO (its calls
24# build effects, they do not run them), and the file's text.
25type Owner is Data:
26 Owner{target: String, name: String, io: Bool, text: String}
27
28# A let that binds one name to a call of its definition to itself: where its binder starts, the binder as written, the
29# binder, and the call.
30type Bound is Data:
31 Bound{from: U32, written: String, binder: U32, call: Lint.Node}
32
33# The lets of a run so far (last first), their binders, and the findings so far (last first).
34type Run is Data:
35 Run{bounds: List<&2, Bound>, binders: List<&2, U32>, out: List<&2, Lint.Finding>}
36
37# Functions
38# =========
39def trim.go(cs: List<&2, Char>) -> List<&2, Char>:
40 match cs:
41 case Con{' ', rest}:
42 trim.go(rest)
43 case _:
44 cs
45
46def trimmed(s: String) -> String:
47 String.from_list(List.reverse(&2, Char, trim.go(List.reverse(&2, Char, String.to_list(s)))))
48
49# Whether an application's nodes call Bool.pick, Bool.and or Bool.or: its arguments are alternatives, each an
50# expression of its own.
51def is_choice(kids: List<&2, Lint.Node>) -> Bool:
52 match kids:
53 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
54 List.contains(~String, ~String.eq, ["Bool.pick", "Bool.and", "Bool.or"], t)
55 case _:
56 False{}
57
58# Whether a node of this syntax ends the expression a call is in.
59def is_boundary(syntax: Lint.Syntax) -> Bool:
60 match syntax:
61 case Lint.Application{}:
62 False{}
63 case Lint.Construction{t}:
64 False{}
65 case Lint.Annotation{}:
66 False{}
67 case _:
68 True{}
69
70# Whether a definition's nodes say it returns IO, as written.
71def returns_io(nodes: List<&2, Lint.Node>) -> Bool:
72 match nodes:
73 case Nil{}:
74 False{}
75 case Con{
76 Lint.Node{Lint.Returns{}, n, s, Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, k}, f},
77 rest
78 }:
79 String.eq(t, "IO")
80 case Con{
81 Lint.Node{
82 Lint.Returns{},
83 n,
84 s,
85 Con{
86 Lint.Node{
87 Lint.Application{},
88 an,
89 as,
90 Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, ak},
91 af
92 },
93 k
94 },
95 f
96 },
97 rest
98 }:
99 String.eq(t, "IO")
100 case Con{node, rest}:
101 returns_io(rest)
102
103# Whether an application's nodes call `target`: its function is a reference to it.
104def calls.to(kids: List<&2, Lint.Node>, target: String) -> Bool:
105 match kids:
106 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
107 String.eq(t, target)
108 case _:
109 False{}
110
111# `out` with the span of a call of `target` (if `call`), where the call is.
112def called.at(
113 call: Bool,
114 span: Maybe<&2, Lint.Span>,
115 out: List<&2, Lint.Span>
116) -> List<&2, Lint.Span>:
117 match call:
118 case True{}:
119 Lists.push(Lint.Span, span, out)
120 case False{}:
121 out
122
123# Where the calls of `target` among `nodes` and under them are (onto `out`, last first), in the expression they start:
124# a node that ends it starts another, and so does each argument of a choice (Bool.pick, Bool.and, Bool.or); a call
125# inside another call of `target` does not count: none does if `nodes` are the parts of one, or of a choice (`inside`).
126def calls(
127 nodes: List<&2, Lint.Node>,
128 +target: String,
129 out: List<&2, Lint.Span>,
130 inside: Bool
131) -> List<&2, Lint.Span>:
132 match nodes inside:
133 case _ True{}:
134 out
135 case Nil{} False{}:
136 out
137 case Con{Lint.Node{Lint.Application{}, n, span, +kids, f}, rest} False{}:
138 +call = calls.to(kids, target)
139 calls(
140 rest,
141 target,
142 calls(kids, target, called.at(call, span, out), call || is_choice(kids)),
143 False{}
144 )
145 case Con{Lint.Node{Lint.Construction{t}, n, s, kids, f}, rest} False{}:
146 calls(rest, target, calls(kids, target, out, False{}), False{})
147 case Con{Lint.Node{Lint.Annotation{}, n, s, kids, f}, rest} False{}:
148 calls(rest, target, calls(kids, target, out, False{}), False{})
149 case Con{node, rest} False{}:
150 calls(rest, target, out, False{})
151
152def texts(spans: List<&2, Lint.Span>, +text: String, out: List<&2, String>) -> List<&2, String>:
153 match spans:
154 case Nil{}:
155 out
156 case Con{s, rest}:
157 texts(rest, text, Lint.Span.text(text, Some{s}) <> out)
158
159def names() -> List<&2, String>:
160 ["a", "b", "c", "d", "e", "g", "h", "k"]
161
162# Fresh names for `n` values, as a parallel let binds them.
163def binders(
164 texts: List<&2, String>,
165 ns: List<&2, String>,
166 out: List<&2, String>
167) -> List<&2, String>:
168 match texts ns:
169 case Con{t, rest} Con{n, more}:
170 binders(rest, more, n <> out)
171 case Con{t, rest} Nil{}:
172 binders(rest, [], "x" <> out)
173 case Nil{} _:
174 List.reverse(&2, String, out)
175
176def quoted(texts: List<&2, String>, out: List<&2, String>) -> List<&2, String>:
177 match texts:
178 case Nil{}:
179 List.reverse(&2, String, out)
180 case Con{t, rest}:
181 quoted(rest, ("`" ++ t ++ "`") <> out)
182
183def costs() -> String:
184 "Bend runs calls in parallel only as the values of a parallel let. CPU, and GPU under a `!`: measured 2.5x faster for a few calls over a 1M-leaf tree, but 3.9x slower for 100,000 calls over 1k-leaf trees, and 230x slower for a small tree walked once per data point. JS: one thread, so no gain. Confidence: low, as it depends on how much work each call does."
185
186def expected() -> String:
187 " If this definition runs once per item of a loop, or below a fork that already fills the cores, expect this finding."
188
189def count(texts: List<&2, String>) -> String:
190 U32.show(U32.from_nat(Lists.length(&2, String, texts)))
191
192def Call.message(loop: String, +texts: List<&2, String>) -> String:
193 loop
194 ++ " calls itself "
195 ++ count(texts)
196 ++ " times in this expression ("
197 ++ String.join(quoted(texts, []), ", ")
198 ++ "), and these calls run one after the other. "
199 ++ costs()
200 ++ " To run them in parallel, bind them first with one parallel let of fresh names, such as `"
201 ++ String.join(binders(texts, names(), []), " ")
202 ++ " = "
203 ++ String.join(texts, " ")
204 ++ "`, and use those names here."
205 ++ expected()
206
207# The finding about an expression at `span` that holds the calls at `spans` (last first), if they are two or more.
208def alike.go(texts: List<&2, String>, +first: String, ok: Bool) -> Bool:
209 match texts ok:
210 case _ False{}:
211 False{}
212 case Nil{} True{}:
213 True{}
214 case Con{t, rest} True{}:
215 alike.go(rest, first, String.eq(t, first))
216
217# Whether `texts`, the calls of one finding, are all written the same way.
218def is_alike(texts: List<&2, String>) -> Bool:
219 match texts:
220 case Con{t, rest}:
221 alike.go(rest, t, True{})
222 case Nil{}:
223 True{}
224
225def Call.finding.of(
226 many: Bool,
227 +spans: List<&2, Lint.Span>,
228 span: Maybe<&2, Lint.Span>,
229 +owner: Owner
230) -> List<&2, Lint.Finding>:
231 match many owner:
232 case True{} Owner{target, name, io, +text}:
233 Lint.finding(
234 Lint.Hint{},
235 Bool.not(is_alike(texts(spans, text, []))),
236 span,
237 Call.message(name, texts(spans, text, []))
238 )
239 case _ _:
240 []
241
242def Call.finding(
243 +spans: List<&2, Lint.Span>,
244 span: Maybe<&2, Lint.Span>,
245 owner: Owner
246) -> List<&2, Lint.Finding>:
247 Call.finding.of(Nat.is_gt(Lists.length(&2, Lint.Span, spans), 1n), spans, span, owner)
248
249# Whether the node below `path` starts an expression: the node above it ends one, or is a choice.
250def starts(path: List<&2, Lint.Above>) -> Bool:
251 match path:
252 case Nil{}:
253 True{}
254 case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, kids, f}, at}, rest}:
255 is_choice(kids)
256 case Con{Lint.Above{Lint.Node{syntax, n, s, k, f}, at}, rest}:
257 is_boundary(syntax)
258
259# The call of a let's value, if the value is a call of `target`, typed or not.
260def called(value: Lint.Node, target: String) -> Maybe<&2, Lint.Node>:
261 match value:
262 case Lint.Node{Lint.Application{}, n, s, +kids, f}:
263 Lists.when(Lint.Node, calls.to(kids, target), Lint.Node{Lint.Application{}, n, s, kids, f})
264 case Lint.Node{
265 Lint.Annotation{},
266 n,
267 s,
268 Con{Lint.Node{Lint.Application{}, cn, cs, +kids, cf}, k},
269 f
270 }:
271 Lists.when(Lint.Node, calls.to(kids, target), Lint.Node{Lint.Application{}, cn, cs, kids, cf})
272 case _:
273 None{}
274
275# A let that binds one name to a call of `target`, if `node` is one.
276def bound(+node: Lint.Node, +owner: Owner) -> Maybe<&2, Bound>:
277 match node owner:
278 case Lint.Node{
279 Lint.Destructure{q},
280 n,
281 s,
282 Con{
283 Lint.Node{Lint.PatternVariable{b, pq}, pn, Some{Lint.Span{p, +from, end}}, pk, pf},
284 Con{value, Con{rest, Nil{}}}
285 },
286 f
287 } Owner{target, name, io, text}:
288 Maybe.map(
289 &2,
290 Lint.Node,
291 Bound,
292 call => Bound{from, trimmed(Strings.slice(text, from, end)), b, call},
293 called(value, target)
294 )
295 case _ _:
296 None{}
297
298# Whether a variable the file writes, of one of `binders`, is among `nodes` or under them, or `found`.
299def uses(nodes: List<&2, Lint.Node>, +binders: List<&2, U32>, found: Bool) -> Bool:
300 match nodes found:
301 case _ True{}:
302 True{}
303 case Nil{} False{}:
304 False{}
305 case Con{Lint.Node{Lint.Variable{v}, n, Some{s}, k, f}, rest} False{}:
306 uses(rest, binders, List.contains(~U32, ~U32.is_eq, binders, v))
307 case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
308 uses(rest, binders, uses(kids, binders, False{}))
309
310def Bound.texts(
311 bounds: List<&2, Bound>,
312 +text: String,
313 written: List<&2, String>,
314 called: List<&2, String>
315) -> List<&2, String>
316 & List<&2, String>:
317 match bounds:
318 case Nil{}:
319 (written, called)
320 case Con{Bound{f, w, b, Lint.Node{s, n, span, k, fs}}, rest}:
321 Bound.texts(rest, text, w <> written, Lint.Span.text(text, span) <> called)
322
323def Run.lets(
324 written: List<&2, String>,
325 called: List<&2, String>,
326 out: List<&2, String>
327) -> List<&2, String>:
328 match written called:
329 case Con{w, rest} Con{c, more}:
330 Run.lets(rest, more, ("`" ++ w ++ " = " ++ c ++ "`") <> out)
331 case _ _:
332 List.reverse(&2, String, out)
333
334def Run.message(loop: String, texts: List<&2, String> & List<&2, String>) -> String:
335 match texts:
336 case Tuple{+written, +called}:
337 loop
338 ++ " calls itself in "
339 ++ count(called)
340 ++ " lets that follow each other ("
341 ++ String.join(Run.lets(written, called, []), ", ")
342 ++ "), and these calls run one after the other. "
343 ++ costs()
344 ++ " To run them in parallel, merge the lets into one: `"
345 ++ String.join(written, " ")
346 ++ " = "
347 ++ String.join(called, " ")
348 ++ "`."
349 ++ expected()
350
351# Whether the calls of a run of lets are all written the same way.
352def Run.alike(texts: List<&2, String> & List<&2, String>) -> Bool:
353 match texts:
354 case Tuple{written, called}:
355 is_alike(called)
356
357def Bound.from(bound: Maybe<&2, Bound>) -> U32:
358 match bound:
359 case Some{Bound{from, w, b, c}}:
360 from
361 case None{}:
362 0
363
364# The finding about a run of lets (last first), if it has two lets or more: from the first's binder to the last's call.
365def Run.finding(+bounds: List<&2, Bound>, +owner: Owner) -> List<&2, Lint.Finding>:
366 match bounds owner:
367 case Con{
368 Bound{f, w, b, Lint.Node{s, n, Some{Lint.Span{path, beg, end}}, k, fs}},
369 Con{second, more}
370 } Owner{target, name, io, +text}:
371 Lint.finding(
372 Lint.Hint{},
373 Bool.not(Run.alike(Bound.texts(bounds, text, [], []))),
374 Some{Lint.Span{path, Bound.from(List.last(&2, Bound, bounds)), end}},
375 Run.message(name, Bound.texts(bounds, text, [], []))
376 )
377 case _ _:
378 []
379
380# The run after a let (`bound`, if it is one): the let joins it if its call uses no binder of the run; else the run
381# ends, and the let starts the next.
382def Run.add(bound: Maybe<&2, Bound>, owner: Owner, run: Run) -> Run:
383 match bound run:
384 case Some{Bound{+f, +w, +b, +c}} Run{+bounds, +binders, +out}:
385 Bool.pick(
386 Run,
387 uses([c], binders, False{}),
388 Run{
389 [Bound{f, w, b, c}],
390 [b],
391 Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out)
392 },
393 Run{Bound{f, w, b, c} <> bounds, b <> binders, out}
394 )
395 case None{} Run{bounds, binders, out}:
396 Run{[], [], Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out)}
397
398def Run.finding.end(run: Run, owner: Owner) -> List<&2, Lint.Finding>:
399 match run:
400 case Run{bounds, binders, out}:
401 List.reverse(&2, Lint.Finding, Lists.onto(&2, Lint.Finding, Run.finding(bounds, owner), out))
402
403# The findings about the runs of lets that follow each other from `node`, a let, after `run`: each next let is the rest
404# of block of the one before, while its call uses no binder of the run.
405def chain(node: Lint.Node, +owner: Owner, run: Run) -> List<&2, Lint.Finding>:
406 match node:
407 case Lint.Node{Lint.Destructure{q}, n, s, Con{binder, Con{value, Con{+rest, Nil{}}}}, f}:
408 chain(
409 rest,
410 owner,
411 Run.add(
412 bound(Lint.Node{Lint.Destructure{q}, n, s, [binder, value, rest], f}, owner),
413 owner,
414 run
415 )
416 )
417 case _:
418 Run.finding.end(run, owner)
419
420# Whether a let below `path` goes on a run from the let above it: it is that let's rest of block, and that let binds
421# one name to a call.
422def follows(path: List<&2, Lint.Above>, owner: Owner) -> Bool:
423 match path:
424 case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, at}, rest}:
425 U32.is_eq(
426 (at + 1: U32),
427 U32.from_nat(Lists.length(&2, Lint.Node, kids))
428 )
429 && Maybe.is_some(&2, Bound, bound(Lint.Node{Lint.Destructure{q}, n, s, kids, f}, owner))
430 case _:
431 False{}
432
433# The finding about the calls of the expression a node starts, if it starts one (`root`).
434def roots(
435 root: Bool,
436 node: Lint.Node,
437 span: Maybe<&2, Lint.Span>,
438 +owner: Owner
439) -> List<&2, Lint.Finding>:
440 match root owner:
441 case True{} Owner{target, name, io, text}:
442 Call.finding(calls([node], target, [], False{}), span, owner)
443 case _ _:
444 []
445
446# The findings about the runs of lets from a node, if it starts one (`head`).
447def lets(head: Bool, node: Lint.Node, owner: Owner) -> List<&2, Lint.Finding>:
448 match head:
449 case True{}:
450 chain(node, owner, Run{[], [], []})
451 case False{}:
452 []
453
454# The findings at a node of a definition below `path`: about the calls of the expression it starts, and about the runs
455# of lets from it, if it starts one.
456def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
457 match owner node:
458 case Owner{target, name, io, text} Lint.Node{syntax, n, span, k, f}:
459 Lists.append(
460 &2,
461 Lint.Finding,
462 roots(
463 Bool.not(io) && Bool.not(is_boundary(syntax)) && starts(path) && Lint.is_live(path),
464 node,
465 span,
466 owner
467 ),
468 lets(
469 Maybe.is_some(
470 &2,
471 Bound,
472 bound(node, owner)
473 )
474 && Bool.not(follows(path, owner))
475 && Lint.is_live(path),
476 node,
477 owner
478 )
479 )
480
481def defs(
482 nodes: List<&2, Lint.Node>,
483 +text: String,
484 out: List<&2, Lint.Finding>
485) -> List<&2, Lint.Finding>:
486 match nodes:
487 case Nil{}:
488 List.reverse(&2, Lint.Finding, out)
489 case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, +k, f}, rest}:
490 defs(
491 rest,
492 text,
493 Lists.onto(
494 &2,
495 Lint.Finding,
496 Lint.visit(
497 ~Owner,
498 ~Lint.Finding,
499 ~visit,
500 Owner{t, n, returns_io(k), text},
501 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
502 ),
503 out
504 )
505 )
506 case Con{node, rest}:
507 defs(rest, text, out)
508
509def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
510 Lint.done(defs(Lint.Here.nodes(here), Lint.Here.text(here), []))
511
512def rule() -> Lint.Rule:
513 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}