performance/dead_accumulator.bend
bend-lint-rules@0.1.0.0 · 138 lines · 0 definitions
1# performance/dead_accumulator: a parameter of a loop that only grows and is never read: each use of it is
2# an argument of the loop's call of itself, at its own place, with something added to it (inside a
3# constructor, such as `x <> acc`), and the loop never matches it, returns it, or gives it to another
4# call. It is built on every step and freed at the end.
5# Heuristics: measured on bend-ml's BPE encode (bend-ml-bpe-tokenizer, as llama.bend uses it): its
6# `done` keeps the rules applied so far, for its proofs, and `encode` drops it; a 48,900-entry list built
7# and freed for each word was half of the time to tokenize 19 KB of text (26.1 s, against 11.5 s with
8# `-done`), with the same ids and the same proofs. A parameter that the loop passes unchanged is not
9# reported: it grows nothing. A use in a type or a proof does not count, as it does not run: the fix,
10# an erased parameter (`-acc`), keeps it there. Only the loop's own calls are read; a call of the loop
11# through another definition, or through a template, is not.
12import Base
13import bend-lint-api@0.1.0.0/linter/lint.bend as Lint
14import bend-lint-api@0.1.0.0/shared/lists.bend as Lists
15
16# Types
17# =====
18
19# What judging the uses of one parameter reads: its loop's name (as the check names it), the place of the parameter
20# among the loop's parameters (as a call's arguments are), and its binder.
21type Owner is Data:
22 Owner{target: String, at: U32, binder: U32}
23
24# Functions
25# =========
26def message(+name: String, loop: String) -> String:
27 name
28 ++ " only grows: "
29 ++ loop
30 ++ " passes it to itself with something added, and nothing reads it, so Bend builds it on every step and frees it at the end. All lanes. Measured on the CPU, in bend-ml's BPE encode, where such a list, built per word, was half of the time: 26.1 s to tokenize 19 KB of text, against 11.5 s after the fix. Confidence: medium, as the gain is what building it costs. Erase it, with `-"
31 ++ name
32 ++ "`: the checker keeps it for proofs, and the compiler deletes it; or remove it. If it gets only a few small items, expect this finding."
33
34# How a use of the parameter below `path` ends: 0 if it is read (in anything but the loop's call of itself, at the
35# parameter's place), 1 if it is passed there as it is, 2 if it is passed there with something added (`grown`).
36def kind(path: List<&2, Lint.Above>, target: String, at: U32, grown: Bool) -> U32:
37 match path:
38 case Con{Lint.Above{Lint.Node{Lint.Construction{t}, n, s, k, f}, a}, rest}:
39 kind(rest, target, at, True{})
40 case Con{Lint.Above{Lint.Node{Lint.Annotation{}, n, s, k, f}, a}, rest}:
41 kind(rest, target, at, grown)
42 case Con{
43 Lint.Above{
44 Lint.Node{
45 Lint.Application{},
46 n,
47 s,
48 Con{Lint.Node{Lint.Reference{t}, rn, rs, rk, rf}, args},
49 f
50 },
51 a
52 },
53 rest
54 }:
55 Bool.pick(
56 U32,
57 String.eq(t, target) && U32.is_eq(a, (at + 1: U32)),
58 Bool.pick(U32, grown, 2, 1),
59 0
60 )
61 case _:
62 0
63
64# How the parameter is used at a node, below `path`, if the node is a use of it in live code.
65def use.visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, U32>:
66 match owner node:
67 case Owner{target, at, binder} Lint.Node{Lint.Variable{v}, n, s, k, f}:
68 Bool.pick(
69 List<&2, U32>,
70 U32.is_eq(v, binder) && Lint.is_live(path),
71 [kind(path, target, at, False{})],
72 []
73 )
74 case _ _:
75 []
76
77# Whether a parameter of quantity `q` that is used as `kinds` says is a dead accumulator: it is there at run time, it
78# is only passed to the loop's own calls, and grows in one at least.
79def is_dead(q: Lint.Quantity, +kinds: List<&2, U32>) -> Bool:
80 match q:
81 case Lint.Erased{}:
82 False{}
83 case Lint.Template{}:
84 False{}
85 case _:
86 Bool.not(
87 List.contains(~U32, ~U32.is_eq, kinds, 0)
88 )
89 && List.contains(~U32, ~U32.is_eq, kinds, 2)
90
91# The findings about the parameters among `nodes`, a definition's, onto `out`; `at` is the place of the first.
92def params(
93 nodes: List<&2, Lint.Node>,
94 +loop: Lint.Node,
95 +target: String,
96 +name: String,
97 +at: U32,
98 out: List<&2, Lint.Finding>
99) -> List<&2, Lint.Finding>:
100 match nodes:
101 case Nil{}:
102 out
103 case Con{Lint.Node{Lint.Parameter{b, q}, pn, ps, pk, pf}, rest}:
104 params(
105 rest,
106 loop,
107 target,
108 name,
109 (at + 1: U32),
110 Lists.onto(
111 &2,
112 Lint.Finding,
113 Lint.finding(
114 Lint.Information{},
115 is_dead(q, Lint.visit(~Owner, ~U32, ~use.visit, Owner{target, at, b}, [loop])),
116 ps,
117 message(pn, name)
118 ),
119 out
120 )
121 )
122 case Con{node, rest}:
123 params(rest, loop, target, name, at, out)
124
125def defs(nodes: List<&2, Lint.Node>, out: List<&2, Lint.Finding>) -> List<&2, Lint.Finding>:
126 match nodes:
127 case Nil{}:
128 List.reverse(&2, Lint.Finding, out)
129 case Con{Lint.Node{Lint.Definition{+t, u}, +n, s, +k, f}, rest}:
130 defs(rest, params(k, Lint.Node{Lint.Definition{t, u}, n, s, k, f}, t, n, 0, out))
131 case Con{node, rest}:
132 defs(rest, out)
133
134def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
135 Lint.done(defs(Lint.Here.nodes(here), []))
136
137def rule() -> Lint.Rule:
138 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}