performance/dead_accumulator.bend

bend-lint-rules@0.2.0.0 · 138 lines · 9 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.2.0.0/linter/lint.bend as Lint
14import bend-lint-api@0.2.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}}