performance/deep_call_in_fork.bend
bend-lint-rules@0.1.1.0 · 244 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.1.1.0/linter/lint.bend as Lint
15import bend-lint-api@0.1.1.0/shared/lists.bend as Lists
16import bend-lint-rules@0.1.1.0/performance/gpu_fit.bend as GpuFit
17
18# Types
19# =====
20
21# What judging the calls in one definition reads: the definitions of the file that call themselves outside a tail
22# position (as the check names them), and the definition, by the name the check gives it and as written.
23type Owner is Data:
24 Owner{deeps: List<&2, String>, target: String, name: String}
25
26# Functions
27# =========
28
29# Whether `at` is the place of the last of `nodes`.
30def is_last(nodes: List<&2, Lint.Node>, at: U32) -> Bool:
31 U32.is_eq((at + 1: U32), U32.from_nat(Lists.length(&2, Lint.Node, nodes)))
32
33# Whether the node below `path` is in a tail position, if it ends the node above it (`ends`): the body of a definition
34# or a case, or the rest of a block after its lets, through annotations.
35def is_tail(path: List<&2, Lint.Above>, ends: Bool) -> Bool:
36 match path ends:
37 case _ False{}:
38 False{}
39 case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} True{}:
40 True{}
41 case Con{Lint.Above{Lint.Node{Lint.Case{}, n, s, k, f}, at}, rest} True{}:
42 is_tail(rest, True{})
43 case Con{Lint.Above{Lint.Node{Lint.Match{}, n, s, k, f}, at}, rest} True{}:
44 is_tail(rest, True{})
45 case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, at}, rest} True{}:
46 is_tail(rest, True{})
47 case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, kids, f}, at}, rest} True{}:
48 is_tail(rest, is_last(kids, at))
49 case Con{Lint.Above{Lint.Node{Lint.Let{}, n, s, kids, f}, at}, rest} True{}:
50 is_tail(rest, is_last(kids, at))
51 case _ _:
52 False{}
53
54# Whether a call of its definition to itself below `path` is outside a tail position.
55def deep.of(recursive: Bool, path: List<&2, Lint.Above>) -> List<&2, Bool>:
56 match recursive:
57 case True{}:
58 [Bool.not(is_tail(path, True{}))]
59 case False{}:
60 []
61
62def deep.visit(+u: Unit, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Bool>:
63 deep.of(Lint.is_recursive(path, node), path)
64
65# The definitions among `nodes` that call themselves outside a tail position, as the check names them, onto `out`;
66# with `forking` false, not those with a parallel let, whose such calls are the values of their forks.
67def deep(nodes: List<&2, Lint.Node>, +forking: Bool, out: List<&2, String>) -> List<&2, String>:
68 match nodes:
69 case Nil{}:
70 out
71 case Con{Lint.Node{Lint.Definition{+t, u}, n, s, +k, f}, rest}:
72 deep(
73 rest,
74 forking,
75 Lists.push(
76 String,
77 Lists.when(
78 String,
79 List.contains(
80 ~Bool,
81 ~Bool.and,
82 Lint.visit(
83 ~Unit,
84 ~Bool,
85 ~deep.visit,
86 Unit{},
87 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
88 ),
89 True{}
90 )
91 && (forking || Bool.not(GpuFit.forks(k, False{}))),
92 t
93 ),
94 out
95 )
96 )
97 case Con{node, rest}:
98 deep(rest, forking, out)
99
100def is_pattern(syntax: Lint.Syntax) -> Bool:
101 match syntax:
102 case Lint.PatternVariable{b, q}:
103 True{}
104 case Lint.PatternConstructor{t}:
105 True{}
106 case _:
107 False{}
108
109def binders(nodes: List<&2, Lint.Node>, n: Nat) -> Nat:
110 match nodes:
111 case Nil{}:
112 n
113 case Con{Lint.Node{Lint.PatternVariable{b, q}, nm, s, k, f}, rest}:
114 binders(rest, 1n+n)
115 case Con{node, rest}:
116 binders(rest, n)
117
118# Whether a let leads to a fork: it is one (it binds `many` names), or it binds one (`one`), and the last of `nodes`,
119# 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
120# before it.
121def leads(nodes: List<&2, Lint.Node>, many: Bool, one: Bool) -> Bool:
122 match nodes many one:
123 case _ True{} _:
124 True{}
125 case _ False{} False{}:
126 False{}
127 case Con{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, Nil{}} False{} True{}:
128 +count = binders(kids, 0n)
129 leads(kids, Nat.is_gt(count, 1n), Nat.is_eq(count, 1n))
130 case Con{x, Nil{}} False{} True{}:
131 False{}
132 case Con{x, rest} False{} True{}:
133 leads(rest, False{}, True{})
134 case Nil{} False{} True{}:
135 False{}
136
137# 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
138# rest of the block.
139def is_value(x: Lint.Node, +parent: Lint.Node, at: U32) -> Bool:
140 match x parent:
141 case Lint.Node{s, n, sp, k, f} Lint.Node{ps, pn, psp, +kids, pf}:
142 leads([parent], False{}, Bool.not(is_pattern(s)) && Bool.not(is_last(kids, at)))
143
144# Whether `x`, below `path`, or a node above it, is a value of a fork, or `found`.
145def is_inside(path: List<&2, Lint.Above>, x: Lint.Node, found: Bool) -> Bool:
146 match path found:
147 case _ True{}:
148 True{}
149 case Nil{} False{}:
150 False{}
151 case Con{Lint.Above{+p, at}, rest} False{}:
152 is_inside(rest, p, is_value(x, p, at))
153
154def message(+callee: String, loop: String) -> String:
155 callee
156 ++ " calls itself outside a tail position, so Bend gives each of its calls a frame, and "
157 ++ loop
158 ++ " 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 "
159 ++ callee
160 ++ " 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."
161
162# The finding about a call of a deep definition (if `deep`), when the call is in a fork.
163def judge.deep(
164 deep: Bool,
165 path: List<&2, Lint.Above>,
166 +node: Lint.Node,
167 callee: String,
168 name: String
169) -> List<&2, Lint.Finding>:
170 match deep:
171 case True{}:
172 Lint.finding(
173 Lint.Information{},
174 is_inside(path, node, False{}),
175 Lint.Node.span(Some{node}),
176 message(callee, name)
177 )
178 case False{}:
179 []
180
181def judge.call(
182 +owner: Owner,
183 path: List<&2, Lint.Above>,
184 node: Lint.Node,
185 callee: String,
186 +called: String
187) -> List<&2, Lint.Finding>:
188 match owner:
189 case Owner{deeps, target, name}:
190 judge.deep(
191 List.contains(~String, ~String.eq, deeps, called) && Bool.not(String.eq(called, target)),
192 path,
193 node,
194 callee,
195 name
196 )
197
198def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
199 match node:
200 case Lint.Node{
201 Lint.Application{},
202 n,
203 s,
204 Con{Lint.Node{Lint.Reference{called}, callee, rs, rk, rf}, args},
205 f
206 }:
207 judge.call(owner, path, node, callee, called)
208 case _:
209 []
210
211def defs(
212 nodes: List<&2, Lint.Node>,
213 +deeps: List<&2, String>,
214 out: List<&2, Lint.Finding>
215) -> List<&2, Lint.Finding>:
216 match nodes:
217 case Nil{}:
218 List.reverse(&2, Lint.Finding, out)
219 case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, k, f}, rest}:
220 defs(
221 rest,
222 deeps,
223 Lists.onto(
224 &2,
225 Lint.Finding,
226 Lint.visit(
227 ~Owner,
228 ~Lint.Finding,
229 ~visit,
230 Owner{deeps, t, n},
231 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
232 ),
233 out
234 )
235 )
236 case Con{node, rest}:
237 defs(rest, deeps, out)
238
239def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
240 +nodes = Lint.Here.nodes(here)
241 Lint.done(defs(nodes, deep(nodes, False{}, []), []))
242
243def rule() -> Lint.Rule:
244 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}