performance/eager_branch.bend
bend-lint-rules@0.1.1.0 · 180 lines · 0 definitions
1# performance/eager_branch: a value that Bend computes even when it is not needed, and that calls a
2# definition of the file that calls itself outside a tail position: a value of `Bool.pick`, or the right
3# side of `&&` or `||`. These are functions, so their arguments are computed before they choose; a
4# `match` runs only its chosen case.
5# Heuristics: measured on the CPU, a Bool.pick whose unused value called a doubly recursive fib took 0.28
6# s, against 0.055 s for a match. A loop whose calls of itself are all tail calls is not reported: clang
7# drops it when its value is unused (under Bool.pick, a 2G-step loop cost nothing measurable), though the
8# JS lane still runs it. A loop's own call in `&&` or `||` is never a tail call. A call of a definition
9# that does not call itself, or of Base, is cheap and not reported. A value in a lambda, a type or an
10# equation does not run, and is skipped; an erased argument (a proof's) is not told from a live one. A
11# loop that is short in practice makes a finding that costs little to ignore.
12import Base
13import bend-lint-api@0.1.1.0/linter/lint.bend as Lint
14import bend-lint-api@0.1.1.0/shared/lists.bend as Lists
15import bend-lint-rules@0.1.1.0/performance/deep_call_in_fork.bend as Deep
16
17# Types
18# =====
19
20# A value Bend computes whether needed or not: what computes it ("pick", "&&" or "||"), and the value.
21type Eager is Data:
22 Eager{kind: String, value: Maybe<&2, Lint.Node>}
23
24# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
25# position (as the check names them), and the definition, as the check names it.
26type Owner is Data:
27 Owner{deeps: List<&2, String>, target: String}
28
29# Functions
30# =========
31# What an application with the nodes `kids` computes whether needed or not, as its node at `at` is one of its
32# arguments: "pick" for a value of Bool.pick, "&&" or "||" for their right side, "" for none.
33def eager(kids: List<&2, Lint.Node>, +at: U32) -> String:
34 match kids:
35 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, Con{ty, Con{c, Con{x, Con{y, rest}}}}}:
36 Bool.pick(
37 String,
38 String.eq(t, "Bool.pick") && (U32.is_eq(at, 3) || U32.is_eq(at, 4)),
39 "pick",
40 ""
41 )
42 case Con{Lint.Node{Lint.Reference{+t}, n, s, k, f}, Con{left, Con{right, Nil{}}}}:
43 Bool.pick(
44 String,
45 U32.is_eq(at, 2),
46 Bool.pick(
47 String,
48 String.eq(t, "Bool.and"),
49 "&&",
50 Bool.pick(String, String.eq(t, "Bool.or"), "||", "")
51 ),
52 ""
53 )
54 case _:
55 ""
56
57def Eager.of(+kind: String, value: Maybe<&2, Lint.Node>) -> Maybe<&2, Eager>:
58 Lists.when(Eager, Bool.not(String.eq(kind, "")), Eager{kind, value})
59
60# The eager value a call below `path` is in, if one is above it and no lambda comes between. `found` stops the walk
61# once one is found.
62def eagerly(path: List<&2, Lint.Above>, found: Maybe<&2, Eager>) -> Maybe<&2, Eager>:
63 match path found:
64 case _ Some{e}:
65 Some{e}
66 case Con{Lint.Above{Lint.Node{Lint.Application{}, n, s, +kids, f}, +at}, rest} None{}:
67 eagerly(rest, Eager.of(eager(kids, at), List.get(&2, Lint.Node, kids, U32.to_nat(at))))
68 case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} None{}:
69 None{}
70 case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} None{}:
71 None{}
72 case Con{a, rest} None{}:
73 eagerly(rest, None{})
74 case Nil{} None{}:
75 None{}
76
77def why(+kind: String, +callee: String) -> String:
78 Bool.pick(
79 String,
80 String.eq(kind, "pick"),
81 "Bool.pick computes both of its values before it picks one, so this call of "
82 ++ callee
83 ++ " runs even when the condition picks the other value",
84 kind
85 ++ " computes its right side even when its left side decides the result ("
86 ++ Bool.pick(String, String.eq(kind, "&&"), "False", "True")
87 ++ "), so this call of "
88 ++ callee
89 ++ " runs even then"
90 )
91
92def message(kind: String, +callee: String, own: Bool) -> String:
93 why(
94 kind,
95 callee
96 )
97 ++ Bool.pick(
98 String,
99 own,
100 ": it is the loop's own call, so the loop walks to its end instead of stopping where the condition decides",
101 ""
102 )
103 ++ ". 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 "
104 ++ callee
105 ++ " runs only a few steps here, expect this finding."
106
107def judged(eager: Maybe<&2, Eager>, callee: String, own: Bool) -> List<&2, Lint.Finding>:
108 match eager:
109 case Some{Eager{kind, value}}:
110 Lint.finding(Lint.Information{}, True{}, Lint.Node.span(value), message(kind, callee, own))
111 case None{}:
112 []
113
114def looping(
115 hit: Bool,
116 path: List<&2, Lint.Above>,
117 callee: String,
118 own: Bool
119) -> List<&2, Lint.Finding>:
120 match hit:
121 case True{}:
122 judged(eagerly(path, None{}), callee, own)
123 case False{}:
124 []
125
126def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
127 match owner node:
128 case Owner{
129 deeps,
130 target
131 } Lint.Node{
132 Lint.Application{},
133 n,
134 s,
135 Con{Lint.Node{Lint.Reference{+called}, callee, rs, rk, rf}, args},
136 f
137 }:
138 looping(
139 List.contains(~String, ~String.eq, deeps, called) && Lint.is_live(path),
140 path,
141 callee,
142 String.eq(called, target)
143 )
144 case _ _:
145 []
146
147def defs(
148 nodes: List<&2, Lint.Node>,
149 +deeps: List<&2, String>,
150 out: List<&2, Lint.Finding>
151) -> List<&2, Lint.Finding>:
152 match nodes:
153 case Nil{}:
154 List.reverse(&2, Lint.Finding, out)
155 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, k, f}, rest}:
156 defs(
157 rest,
158 deeps,
159 Lists.onto(
160 &2,
161 Lint.Finding,
162 Lint.visit(
163 ~Owner,
164 ~Lint.Finding,
165 ~visit,
166 Owner{deeps, t},
167 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
168 ),
169 out
170 )
171 )
172 case Con{node, rest}:
173 defs(rest, deeps, out)
174
175def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
176 +nodes = Lint.Here.nodes(here)
177 Lint.done(defs(nodes, Deep.deep(nodes, True{}, []), []))
178
179def rule() -> Lint.Rule:
180 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}