performance/deep_call_in_fork.bend
bend-lint-rules@0.2.2.0 · 257 lines · 0 definitions
1# performance/deep_call_in_fork: a fork that calls a definition that calls itself outside a tail
2# position. A value of a parallel let (`a b = f(x) g(y)`), or of a let just before it, calls a definition
3# of the file whose call of itself is not the last thing it does.
4# Heuristics: Bend gives a call of itself that is not a tail call a frame per call ("bend guide
5# shaders"). In bend-lint's benchmark (Bend 2.0.36, on the CPU), such a call at each fork cut the speedup
6# from 10x to 1.9x; the same definition with a tail call kept the 10x. In a raytracer that splits its
7# rows that way at each of 9 fork levels, tail-recursive splits made it 4% to 8% faster on the CPU; in
8# Bend's slash boss demo, the same change changed no timing, as its list was short. The JS lane is not
9# measured. A tail position is the body of a definition, a case, or the rest of a block after its lets,
10# through annotations. A definition with a parallel let is a fork tree: its calls of itself are the
11# values of its forks, not frames, and it is not reported (Bend's matrix and Merkle benchmarks call such
12# trees in their forks).
13import Base
14import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
15import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
16
17# Types
18# =====
19
20# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
21# position (as the check names them), and the definition, by the name the check gives it and as written.
22type Owner is Data:
23 Owner{deeps: List<&2, String>, target: String, name: String}
24
25# Functions
26# =========
27
28# Whether `at` is the place of the last of `nodes`.
29def is_last(nodes: List<&2, Lint.Node>, at: U32) -> Bool:
30 U32.is_eq((at + 1: U32), U32.from_nat(Lists.length(&2, Lint.Node, nodes)))
31
32# Whether the node below `path` is in a tail position, if it ends the node above it (`ends`): the body of a definition
33# or a case, or the rest of a block after its lets, through annotations.
34def is_tail(path: List<&2, Lint.Above>, ends: Bool) -> Bool:
35 match path ends:
36 case _ False{}:
37 False{}
38 case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} True{}:
39 True{}
40 case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest} True{}:
41 is_tail(rest, True{})
42 case Con{Lint.Above{Lint.Node{Lint.Match{}, n, s, k, f}, at}, rest} True{}:
43 is_tail(rest, True{})
44 case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, at}, rest} True{}:
45 is_tail(rest, True{})
46 case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, kids, f}, at}, rest} True{}:
47 is_tail(rest, is_last(kids, at))
48 case Con{Lint.Above{Lint.Node{Lint.Let{}, n, s, kids, f}, at}, rest} True{}:
49 is_tail(rest, is_last(kids, at))
50 case _ _:
51 False{}
52
53# Whether a call of its definition to itself below `path` is outside a tail position.
54def deep.of(recursive: Bool, path: List<&2, Lint.Above>) -> List<&2, Bool>:
55 match recursive:
56 case True{}:
57 [Bool.not(is_tail(path, True{}))]
58 case False{}:
59 []
60
61def deep.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Bool>:
62 deep.of(Lint.is_recursive(path, node), path)
63
64# Whether a definition with the nodes `k` counts, if it calls itself outside a tail position (`found`): each does if
65# `forking`, else one without a parallel let.
66def deep.if(found: Bool, forking: Bool, k: List<&2, Lint.Node>) -> Bool:
67 match found forking:
68 case False{} _:
69 False{}
70 case True{} True{}:
71 True{}
72 case True{} False{}:
73 Bool.not(Lint.forks(k, False{}))
74
75# The definitions among `nodes` that call themselves outside a tail position, as the check names them, onto `out`;
76# with `forking` false, not those with a parallel let, whose such calls are the values of their forks.
77def deep(nodes: List<&2, Lint.Node>, +forking: Bool, out: List<&2, String>) -> List<&2, String>:
78 match nodes:
79 case Nil{}:
80 out
81 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +k, f}, rest}:
82 deep(
83 rest,
84 forking,
85 Lists.push(
86 String,
87 Lists.when(
88 String,
89 deep.if(
90 List.contains(
91 ~Bool,
92 ~Bool.and,
93 Lint.visit(
94 ~Unit,
95 ~Bool,
96 ~deep.visit,
97 Unit{},
98 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
99 ),
100 True{}
101 ),
102 forking,
103 k
104 ),
105 t
106 ),
107 out
108 )
109 )
110 case Con{node, rest}:
111 deep(rest, forking, out)
112
113def is_pattern(syntax: Lint.Syntax) -> Bool:
114 match syntax:
115 case Lint.PatternVariable{b, q}:
116 True{}
117 case Lint.PatternConstructor{t}:
118 True{}
119 case _:
120 False{}
121
122def binders(nodes: List<&2, Lint.Node>, n: Nat) -> Nat:
123 match nodes:
124 case Nil{}:
125 n
126 case Con{Lint.Node{Lint.PatternVariable{b, q}, nm, s, k, f}, rest}:
127 binders(rest, 1n+n)
128 case Con{node, rest}:
129 binders(rest, n)
130
131# Whether a let leads to a fork: it is one (it binds `many` names), or it binds one (`one`), and the last of `nodes`,
132# the rest of its block, is a let that leads to one. The values of these lets are what a fork runs, or what runs just
133# before it.
134def leads(nodes: List<&2, Lint.Node>, many: Bool, one: Bool) -> Bool:
135 match nodes many one:
136 case _ True{} _:
137 True{}
138 case _ False{} False{}:
139 False{}
140 case Con{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, Nil{}} False{} True{}:
141 +count = binders(kids, 0n)
142 leads(kids, Nat.is_gt(count, 1n), Nat.is_eq(count, 1n))
143 case Con{x, Nil{}} False{} True{}:
144 False{}
145 case Con{x, rest} False{} True{}:
146 leads(rest, False{}, True{})
147 case Nil{} False{} True{}:
148 False{}
149
150# Whether `x`, the node at `at` under `parent`, is a value of a fork, or of a let just before one: not a binder, nor the
151# rest of the block.
152def is_value(x: Lint.Node, +parent: Lint.Node, at: U32) -> Bool:
153 match x parent:
154 case Lint.Node{s, n, sp, k, f} Lint.Node{ps, pn, psp, +kids, pf}:
155 leads([parent], False{}, Bool.not(is_pattern(s)) && Bool.not(is_last(kids, at)))
156
157# Whether `x`, below `path`, or a node above it, is a value of a fork, or `found`.
158def is_inside(path: List<&2, Lint.Above>, x: Lint.Node, found: Bool) -> Bool:
159 match path found:
160 case _ True{}:
161 True{}
162 case Nil{} False{}:
163 False{}
164 case Con{Lint.Above{+p, at}, rest} False{}:
165 is_inside(rest, p, is_value(x, p, at))
166
167def message(+callee: String, loop: String) -> String:
168 callee
169 ++ " calls itself outside a tail position, so Bend gives each of its calls a frame, and "
170 ++ loop
171 ++ " calls it in a fork (a value of its parallel let, or of a let just before it). CPU: measured 4% to 8% faster for a raytracer after the fix; in a benchmark, such a call at each fork cut a 10x speedup to 1.9x. GPU: such a recursion in a `!` made a draw 2.3x slower (\"bend guide shaders\"). JS: not measured. Confidence: medium, as the cost grows with the depth of the recursion. Make "
172 ++ callee
173 ++ " tail-recursive with an accumulator, compute its value with native operations (such as U32.shln), or compute it once and pass it down as a parameter. If its input is short, expect this finding."
174
175# The finding about a call of a deep definition (if `deep`), when the call is in a fork.
176def judge.deep(
177 deep: Bool,
178 path: List<&2, Lint.Above>,
179 +node: Lint.Node,
180 callee: String,
181 name: String
182) -> List<&2, Lint.Finding>:
183 match deep:
184 case True{}:
185 Lint.finding(
186 Lint.Information{},
187 is_inside(path, node, False{}),
188 Lint.Node.span(Some{node}),
189 message(callee, name)
190 )
191 case False{}:
192 []
193
194def judge.call(
195 +owner: Owner,
196 path: List<&2, Lint.Above>,
197 node: Lint.Node,
198 callee: String,
199 +called: String
200) -> List<&2, Lint.Finding>:
201 match owner:
202 case Owner{deeps, target, name}:
203 judge.deep(
204 List.contains(~String, ~String.eq, deeps, called) && Bool.not(String.eq(called, target)),
205 path,
206 node,
207 callee,
208 name
209 )
210
211def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
212 match node:
213 case Lint.Node{
214 Lint.Application{},
215 n,
216 s,
217 Con{Lint.Node{Lint.Reference{called}, callee, rs, rk, rf}, args},
218 f
219 }:
220 judge.call(owner, path, node, callee, called)
221 case _:
222 []
223
224def defs(
225 nodes: List<&2, Lint.Node>,
226 +deeps: List<&2, String>,
227 out: List<&2, Lint.Finding>
228) -> List<&2, Lint.Finding>:
229 match nodes:
230 case Nil{}:
231 List.reverse(&2, Lint.Finding, out)
232 case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, k, f}, rest}:
233 defs(
234 rest,
235 deeps,
236 Lists.onto(
237 &2,
238 Lint.Finding,
239 Lint.visit(
240 ~Owner,
241 ~Lint.Finding,
242 ~visit,
243 Owner{deeps, t, n},
244 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
245 ),
246 out
247 )
248 )
249 case Con{node, rest}:
250 defs(rest, deeps, out)
251
252def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
253 +nodes = Lint.Here.nodes(here)
254 Lint.done(defs(nodes, deep(nodes, False{}, []), []))
255
256def rule() -> Lint.Rule:
257 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}