performance/append_in_loop.bend
bend-lint-rules@0.2.1.0 · 269 lines · 0 definitions
1# performance/append_in_loop: a loop that appends to its accumulator. A definition passes
2# `List.append(.., acc, ..)` or `acc ++ ..` to a call of itself, where acc is one of its parameters.
3# Heuristics: an append copies acc, so a loop of n steps copies O(n²) items, where adding at the head
4# copies none. `++` copies only on the C lane: the JS lane joins strings natively. A loop that also
5# keeps each value it builds, by passing acc in another argument too, needs the copies: it is not
6# reported. It knows Base's List.append and String.append (`++`), not other functions that copy
7# their first argument.
8import Base
9import bend-lint-api@0.2.1.0/linter/lint.bend as Lint
10import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
11
12# Types
13# =====
14
15# A function that copies its first list or text to append to it.
16type Append is Data:
17 ListAppend{}
18 StringAppend{}
19
20# What judging the calls of a loop to itself reads: the loop's parameters, and the file's text.
21type Loop is Data:
22 Loop{params: List<&2, Lint.Node>, text: String}
23
24# Functions
25# =========
26
27# The append that a call of `callee` with `count` arguments is.
28def Append.of(+callee: String, +count: Nat) -> Maybe<&2, Append>:
29 Bool.pick(
30 Maybe<&2, Append>,
31 String.eq(callee, "List.append") && Nat.is_eq(count, 4n),
32 Some{ListAppend{}},
33 Lists.when(Append, String.eq(callee, "String.append") && Nat.is_eq(count, 2n), StringAppend{})
34 )
35
36# Which argument an append copies.
37def Append.at(a: Append) -> Nat:
38 match a:
39 case ListAppend{}:
40 2n
41 case StringAppend{}:
42 0n
43
44# What a finding says about an append of `acc` in the loop `loop`. `args` are the append's arguments.
45def Append.message(
46 a: Append,
47 loop: String,
48 +acc: String,
49 +source: String,
50 +args: List<&2, Lint.Node>
51) -> String:
52 match a:
53 case ListAppend{}:
54 +q = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 0n)))
55 +t = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 1n)))
56 "List.append copies "
57 ++ acc
58 ++ " on each call of "
59 ++ loop
60 ++ ", so a loop of n steps copies O(n²) items. All lanes. Confidence: high, as the copies grow with the square of the steps. Add each item at the head instead, with `item <> "
61 ++ acc
62 ++ "`, and reverse "
63 ++ acc
64 ++ " once when the loop ends: `List.reverse("
65 ++ q
66 ++ ", "
67 ++ t
68 ++ ", "
69 ++ acc
70 ++ ")`; to add a list each step, collect the lists, with `piece <> pieces`, and join them once: `List.concat("
71 ++ q
72 ++ ", "
73 ++ t
74 ++ ", List.reverse("
75 ++ q
76 ++ ", List<"
77 ++ q
78 ++ ", "
79 ++ t
80 ++ ">, pieces))`. If the loop runs only a few steps, expect this finding."
81 case StringAppend{}:
82 "++ copies "
83 ++ acc
84 ++ " on each call of "
85 ++ loop
86 ++ ", so a loop of n steps copies O(n²) characters. CPU and GPU: measured 12.6 s for 20,000 lines, against 0.07 s after the fix. JS: strings join natively, at no cost. Confidence: high, as the copies grow with the square of the steps. Collect the pieces in a list instead, with `piece <> pieces`, and join them once when the loop ends: `String.concat(List.reverse(&2, String, pieces))`. If the loop runs only a few steps, expect this finding."
87
88# Whether a variable the file writes, of the binder `b`, is among `nodes` or under them, or `found`.
89def has(nodes: List<&2, Lint.Node>, +b: U32, found: Bool) -> Bool:
90 match nodes found:
91 case _ True{}:
92 True{}
93 case Nil{} False{}:
94 False{}
95 case Con{Lint.Node{Lint.Variable{v}, n, Some{s}, k, f}, rest} False{}:
96 has(rest, b, U32.is_eq(v, b))
97 case Con{Lint.Node{syntax, n, s, kids, f}, rest} False{}:
98 has(rest, b, has(kids, b, False{}))
99
100def judged(
101 kept: Bool,
102 a: Append,
103 name: String,
104 acc: String,
105 span: Lint.Span,
106 text: String,
107 args: List<&2, Lint.Node>
108) -> List<&2, Lint.Finding>:
109 match kept:
110 case True{}:
111 []
112 case False{}:
113 [Lint.Finding{Lint.Warning{}, span, Append.message(a, name, acc, text, args), []}]
114
115# The finding about an append (`a`, at `span`, with `args`) to `acc`, if it is a parameter of the loop `name` that its
116# call does not also use (in `before` and `after`, its nodes but the append): then it keeps each value the loop builds,
117# and the copies are needed.
118def accumulated(
119 acc: Maybe<&2, Lint.Node>,
120 a: Append,
121 loop: Loop,
122 name: String,
123 span: Lint.Span,
124 args: List<&2, Lint.Node>,
125 before: List<&2, Lint.Node>,
126 after: List<&2, Lint.Node>
127) -> List<&2, Lint.Finding>:
128 match acc loop:
129 case Some{Lint.Node{Lint.Variable{+b}, var, s, k, f}} Loop{params, text}:
130 judged(
131 has(after, b, has(before, b, Maybe.is_none(&2, Nat, Lint.parameter(params, b)))),
132 a,
133 name,
134 var,
135 span,
136 text,
137 args
138 )
139 case _ _:
140 []
141
142def appended(
143 append: Maybe<&2, Append>,
144 +args: List<&2, Lint.Node>,
145 loop: Loop,
146 name: String,
147 span: Lint.Span,
148 before: List<&2, Lint.Node>,
149 after: List<&2, Lint.Node>
150) -> List<&2, Lint.Finding>:
151 match append:
152 case Some{+a}:
153 accumulated(
154 List.get(&2, Lint.Node, args, Append.at(a)),
155 a,
156 loop,
157 name,
158 span,
159 args,
160 before,
161 after
162 )
163 case None{}:
164 []
165
166# The findings about an argument of a call of the loop `name`, if it appends; `before` and `after` are the call's other
167# nodes.
168def argument(
169 arg: Lint.Node,
170 loop: Loop,
171 name: String,
172 before: List<&2, Lint.Node>,
173 after: List<&2, Lint.Node>
174) -> List<&2, Lint.Finding>:
175 match arg:
176 case Lint.Node{
177 Lint.Application{},
178 n,
179 Some{span},
180 Con{Lint.Node{Lint.Reference{callee}, rn, rs, rk, rf}, +parts},
181 f
182 }:
183 appended(
184 Append.of(callee, Lists.length(&2, Lint.Node, parts)),
185 parts,
186 loop,
187 name,
188 span,
189 before,
190 after
191 )
192 case _:
193 []
194
195# The findings about the arguments `args` of a call of the loop `name`, after the call's nodes `before` (last first).
196def arguments(
197 args: List<&2, Lint.Node>,
198 +loop: Loop,
199 +name: String,
200 +before: List<&2, Lint.Node>,
201 out: List<&2, Lint.Finding>
202) -> List<&2, Lint.Finding>:
203 match args:
204 case Nil{}:
205 List.reverse(&2, Lint.Finding, out)
206 case Con{+arg, +rest}:
207 arguments(
208 rest,
209 loop,
210 name,
211 arg <> before,
212 Lists.onto(&2, Lint.Finding, argument(arg, loop, name, before, rest), out)
213 )
214
215def call.of(loop: Loop, kids: List<&2, Lint.Node>) -> List<&2, Lint.Finding>:
216 match kids:
217 case Con{Lint.Node{s, +name, sp, k, f}, args}:
218 arguments(args, loop, name, [Lint.Node{s, name, sp, k, f}], [])
219 case Nil{}:
220 []
221
222def call(loop: Loop, node: Lint.Node) -> List<&2, Lint.Finding>:
223 match node:
224 case Lint.Node{s, n, sp, kids, f}:
225 call.of(loop, kids)
226
227def calls(recursive: Bool, loop: Loop, node: Lint.Node) -> List<&2, Lint.Finding>:
228 match recursive:
229 case True{}:
230 call(loop, node)
231 case False{}:
232 []
233
234def visit(+loop: Loop, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
235 calls(Lint.is_recursive(path, node), loop, node)
236
237def defs(
238 nodes: List<&2, Lint.Node>,
239 +text: String,
240 out: List<&2, Lint.Finding>
241) -> List<&2, Lint.Finding>:
242 match nodes:
243 case Nil{}:
244 List.reverse(&2, Lint.Finding, out)
245 case Con{Lint.Node{Lint.Definition{t, u}, n, s, +k, f}, rest}:
246 defs(
247 rest,
248 text,
249 Lists.onto(
250 &2,
251 Lint.Finding,
252 Lint.visit(
253 ~Loop,
254 ~Lint.Finding,
255 ~visit,
256 Loop{k, text},
257 [Lint.Node{Lint.Definition{t, u}, n, s, k, f}]
258 ),
259 out
260 )
261 )
262 case Con{node, rest}:
263 defs(rest, text, out)
264
265def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
266 Lint.done(defs(Lint.Here.nodes(here), Lint.Here.text(here), []))
267
268def rule() -> Lint.Rule:
269 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}