performance/eager_branch.bend
bend-lint-rules@0.2.2.0 · 307 lines · 0 definitions
1# performance/eager_branch: a value that Bend computes even when it is not needed, and that runs a loop
2# of the program to its end: a value of `Bool.pick`, or the right side of `&&` or `||`. These are
3# functions, so their arguments are computed before they choose; a `match` runs only its chosen case.
4# Heuristics: measured on the CPU, a Bool.pick whose unused value called a doubly recursive fib took 0.28
5# s, against 0.055 s for a match. clang drops an unused loop that compiles to one native loop: under
6# Bool.pick, a 2G-step tail loop cost nothing measurable, and under `&&`, a 400M-step one; the JS lane
7# still runs it. A tail loop that called Base's List.contains, which applies a closure, at each step did
8# not drop: 0.86 s for 40M steps, against 0.09 s for a match. So a call is reported when it is of a loop
9# that calls itself outside a tail position, or of one under which a parallel let, a closure's
10# application (not a `~` parameter's) or such a loop runs, or of a definition that calls such a loop,
11# through the program's files. A loop's own call in `&&` or `||` is never a tail call. Base's
12# definitions are not seen: a call of one counts as one native loop, so a loop slow only through Base is
13# not reported. A call under a lambda counts, though it runs only when the lambda does. A value in a
14# lambda, a type or an equation does not run, and is skipped; an erased argument (a proof's) is not told
15# from a live one. A loop that is short in practice makes a finding that costs little to ignore.
16import Base
17import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
18import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
19import bend-lint-api@0.2.2.0/shared/names.bend as Names
20import bend-lint-api@0.2.2.0/shared/sets.bend as Sets
21import bend-lint-rules@0.2.2.0/performance/deep_call_in_fork.bend as Deep
22
23# Types
24# =====
25
26# A value Bend computes whether needed or not: what computes it ("pick", "&&" or "||"), and the value.
27type Eager is Data:
28 Eager{kind: String, value: Maybe<&2, Lint.Node>}
29
30# What judging the calls in one definition reads: the definitions of the program a call of which runs a loop to its end
31# (see costly), and the definition, as the check names them.
32type Owner is Data:
33 Owner{costly: Set(), target: String}
34
35# Functions
36# =========
37# What an application with the nodes `kids` computes whether needed or not, as its node at `at` is one of its
38# arguments: "pick" for a value of Bool.pick, "&&" or "||" for their right side, "" for none.
39def eager(kids: List<&2, Lint.Node>, +at: U32) -> String:
40 match kids:
41 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, Con{ty, Con{c, Con{x, Con{y, rest}}}}}:
42 Bool.pick(
43 String,
44 String.eq(t, "Bool.pick") && (U32.is_eq(at, 3) || U32.is_eq(at, 4)),
45 "pick",
46 ""
47 )
48 case Con{Lint.Node{Lint.Reference{+t}, n, s, k, f}, Con{left, Con{right, Nil{}}}}:
49 Bool.pick(
50 String,
51 U32.is_eq(at, 2),
52 Bool.pick(
53 String,
54 String.eq(t, "Bool.and"),
55 "&&",
56 Bool.pick(String, String.eq(t, "Bool.or"), "||", "")
57 ),
58 ""
59 )
60 case _:
61 ""
62
63def Eager.of(+kind: String, value: Maybe<&2, Lint.Node>) -> Maybe<&2, Eager>:
64 Lists.when(Eager, Bool.not(String.eq(kind, "")), Eager{kind, value})
65
66# The eager value a call below `path` is in, if one is above it and no lambda comes between. `found` stops the walk
67# once one is found.
68def eagerly(path: List<&2, Lint.Above>, found: Maybe<&2, Eager>) -> Maybe<&2, Eager>:
69 match path found:
70 case _ Some{e}:
71 Some{e}
72 case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, +kids, f}, +at}, rest} None{}:
73 eagerly(rest, Eager.of(eager(kids, at), List.get(&2, Lint.Node, kids, U32.to_nat(at))))
74 case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} None{}:
75 None{}
76 case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} None{}:
77 None{}
78 case Con{a, rest} None{}:
79 eagerly(rest, None{})
80 case Nil{} None{}:
81 None{}
82
83def why(+kind: String, +callee: String) -> String:
84 Bool.pick(
85 String,
86 String.eq(kind, "pick"),
87 "Bool.pick computes both of its values before it picks one, so this call of "
88 ++ callee
89 ++ " runs even when the condition picks the other value",
90 kind
91 ++ " computes its right side even when its left side decides the result ("
92 ++ Bool.pick(String, String.eq(kind, "&&"), "False", "True")
93 ++ "), so this call of "
94 ++ callee
95 ++ " runs even then"
96 )
97
98def message(kind: String, +callee: String, own: Bool) -> String:
99 why(
100 kind,
101 callee
102 )
103 ++ Bool.pick(
104 String,
105 own,
106 ": it is the loop's own call, so the loop walks to its end instead of stopping where the condition decides",
107 ""
108 )
109 ++ ". CPU and GPU: measured 5x slower than a match, for an unused call that calls itself outside a tail position. JS: computes both values too. Confidence: medium, as the cost is what the unneeded call computes. Choose with a match: pass the condition to a helper whose match runs only the needed value; inside a loop, where that helper would call the loop back (Bend refuses mutual recursion), pass the condition to the next call, and match on it there. If "
110 ++ callee
111 ++ " runs only a few steps here, expect this finding."
112
113def judged(eager: Maybe<&2, Eager>, callee: String, own: Bool) -> List<&2, Lint.Finding>:
114 match eager:
115 case Some{Eager{kind, value}}:
116 Lint.finding(Lint.Information{}, True{}, Lint.Node.span(value), message(kind, callee, own))
117 case None{}:
118 []
119
120def looping(
121 hit: Bool,
122 path: List<&2, Lint.Above>,
123 callee: String,
124 own: Bool
125) -> List<&2, Lint.Finding>:
126 match hit:
127 case True{}:
128 judged(eagerly(path, None{}), callee, own)
129 case False{}:
130 []
131
132def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
133 match owner node:
134 case Owner{
135 costly,
136 target
137 } Lint.Node{
138 Lint.Application{},
139 n,
140 s,
141 Con{Lint.Node{Lint.Reference{+called}, callee, rs, rk, rf}, args},
142 f
143 }:
144 looping(
145 Sets.has(costly, called) && Lint.is_live(path),
146 path,
147 callee,
148 String.eq(called, target)
149 )
150 case _ _:
151 []
152
153def defs(
154 nodes: List<&2, Lint.Node>,
155 +costly: Set(),
156 out: List<&2, Lint.Finding>
157) -> List<&2, Lint.Finding>:
158 match nodes:
159 case Nil{}:
160 List.reverse(&2, Lint.Finding, out)
161 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, k, f}, rest}:
162 defs(
163 rest,
164 costly,
165 Lists.onto(
166 &2,
167 Lint.Finding,
168 Lint.visit(
169 ~Owner,
170 ~Lint.Finding,
171 ~visit,
172 Owner{costly, t},
173 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
174 ),
175 out
176 )
177 )
178 case Con{node, rest}:
179 defs(rest, costly, out)
180
181# The binders of the `~` parameters among a definition's nodes, onto `out`: a call of one is inlined, not a closure's.
182def templates(nodes: List<&2, Lint.Node>, out: List<&2, U32>) -> List<&2, U32>:
183 match nodes:
184 case Nil{}:
185 out
186 case Con{Lint.Node{Lint.Parameter{b, Lint.Template{}}, n, s, k, f}, rest}:
187 templates(rest, b <> out)
188 case Con{node, rest}:
189 templates(rest, out)
190
191# A closure's application: of a variable that no `~` parameter (`templates`) binds.
192def applies.visit(
193 +templates: List<&2, U32>,
194 +path: List<&2, Lint.Above>,
195 +node: Lint.Node
196) -> List<&2, Unit>:
197 match node:
198 case Lint.Node{
199 Lint.Application{},
200 n,
201 s,
202 Con{Lint.Node{Lint.Variable{b}, vn, vs, vk, vf}, args},
203 f
204 }:
205 Lists.push(
206 Unit,
207 Lists.when(Unit, Bool.not(List.contains(~U32, ~U32.is_eq, templates, b)), Unit{}),
208 []
209 )
210 case _:
211 []
212
213# Whether a definition's nodes apply a closure, or `found`.
214def applies(+kids: List<&2, Lint.Node>, found: Bool) -> Bool:
215 match found:
216 case True{}:
217 True{}
218 case False{}:
219 Bool.not(
220 List.is_empty(
221 &2,
222 Unit,
223 Lint.visit(~List<&2, U32>, ~Unit, ~applies.visit, templates(kids, []), kids)
224 )
225 )
226
227# The definitions among a file's `nodes` whose own body keeps them from compiling to a native loop, onto `out`: a
228# parallel let is in them, or a closure's application.
229def unflat(nodes: List<&2, Lint.Node>, out: List<&2, String>) -> List<&2, String>:
230 match nodes:
231 case Nil{}:
232 out
233 case Con{Lint.Node{Lint.Definition{t, u}, n, s, +kids, f}, rest}:
234 unflat(
235 rest,
236 Lists.push(String, Lists.when(String, applies(kids, Lint.forks(kids, False{})), t), out)
237 )
238 case Con{node, rest}:
239 unflat(rest, out)
240
241# The definitions of the program whose own body keeps them from compiling to a native loop, onto `out`: those of
242# `unflat`, and those that call themselves outside a tail position.
243def program.unflat(sources: List<&2, Lint.Source>, out: List<&2, String>) -> List<&2, String>:
244 match sources:
245 case Nil{}:
246 out
247 case Con{Lint.Source{path, ns, text, +nodes}, rest}:
248 program.unflat(rest, unflat(nodes, Deep.deep(nodes, True{}, out)))
249
250def calls_itself(info: Maybe<&2, Lint.Def>) -> Bool:
251 match info:
252 case Some{Lint.Def{t, ps, forks, calls, r}}:
253 List.contains(~String, ~String.eq, calls, t)
254 case None{}:
255 False{}
256
257# The definitions among `names` that call themselves and are in `unflat`, onto `out`.
258def loops(
259 names: List<&2, String>,
260 +defs: Map<&2, Maybe<&2, Lint.Def>>,
261 +unflat: Set(),
262 out: List<&2, String>
263) -> List<&2, String>:
264 match names:
265 case Nil{}:
266 out
267 case Con{+t, rest}:
268 loops(
269 rest,
270 defs,
271 unflat,
272 Lists.push(
273 String,
274 Lists.when(String, Sets.has(unflat, t) && calls_itself(Names.find(Lint.Def, defs, t)), t),
275 out
276 )
277 )
278
279# The definitions of the program a call of which runs a loop to its end, even when its value is unused: a loop that does
280# not compile to a native loop, as its body, or one it calls, keeps it from that (see program.unflat); or a definition
281# that calls such a loop.
282def costly(+sources: List<&2, Lint.Source>, +defs: Map<&2, Maybe<&2, Lint.Def>>) -> Set():
283 Lint.Program.callers(
284 sources,
285 defs,
286 Set.from_list(
287 loops(
288 Map.keys(&2, Maybe<&2, Lint.Def>, defs),
289 defs,
290 Lint.Program.callers(sources, defs, Set.from_list(program.unflat(sources, []))),
291 []
292 )
293 )
294 )
295
296def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
297 +sources = Lint.Here.sources(here)
298 Lint.done(
299 defs(
300 Lint.Here.nodes(here),
301 costly(sources, Lint.Program.defs(sources, Map.new(&2, Maybe<&2, Lint.Def>))),
302 []
303 )
304 )
305
306def rule() -> Lint.Rule:
307 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}