performance/deep_call_in_fork.bend

bend-lint-rules@0.2.0.0 · 257 lines · 19 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.0.0/linter/lint.bend as Lint
15import bend-lint-api@0.2.0.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}}