performance/eager_branch.bend

bend-lint-rules@0.2.0.0 · 307 lines · 21 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.0.0/linter/lint.bend as Lint
18import bend-lint-api@0.2.0.0/shared/lists.bend as Lists
19import bend-lint-api@0.2.0.0/shared/names.bend as Names
20import bend-lint-api@0.2.0.0/shared/sets.bend as Sets
21import bend-lint-rules@0.2.0.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}}