performance/template_value_field.bend
bend-lint-rules@0.2.2.0 · 180 lines · 0 definitions
1# performance/template_value_field: a value field of a record of functions that reads a template whose type is a
2# record of functions. Bend writes a template where it is used, so a record of functions passed as one is built
3# again at each use; a field that is not a function is computed then, and reading the template builds its whole
4# record, closures too, to read a part of it, then frees the rest.
5# Heuristics: measured on a combinator of two records of functions, nested 6 deep and run 2M times: 1.7 s with a
6# count as a value field, against 1.0 s with the count under a lambda (`u => ..`), on the C lane (one thread), and
7# 49 s against 14 s on the JS lane, with the same output; issue #2 measured 6% more time on a nested model, and
8# nothing on a shallow one, as the cost doubles with each level. The lambda moves the work to each read: with the
9# count read on every step too, it took 2.4 s against 1.9 s. A record of functions is a datatype of the program
10# with a field whose written type is a function; a record that the rule judges is built in live code, outside a
11# lambda, with a lambda among its fields: a record of values only is a result, built once. A template of another
12# type (a number, a function, a list) builds no record of closures, and is not judged. A use in a type, or under a
13# lambda, does not run when the record is built.
14import Base
15import bend-lint-api@0.2.2.0/linter/lint.bend as Lint
16import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
17
18# Types
19# =====
20
21# What judging the uses of one definition's templates reads: the binders of its templates whose type is a record of
22# functions, and its name as written.
23type Owner is Data:
24 Owner{templates: List<&2, U32>, name: String}
25
26# Functions
27# =========
28def message(+template: String, owner: String) -> String:
29 template
30 ++ " is a template, so reading it here builds its whole record, closures too, to read a part of it; and a record of functions passed as a template is built again at each use, so "
31 ++ owner
32 ++ " repeats this wherever its record is used, twice as often at each level of nesting. All lanes. Measured on a combinator nested 6 deep: 1.7 s against 1.0 s after the fix on the C lane, 49 s against 14 s on the JS lane; on a nested model, 6% of the time. Confidence: medium, as the fix moves the work to each read of the field. Make the field a function of Unit (`n: Unit -> U32`, built as `u => ..`), so that "
33 ++ template
34 ++ " is read only when the field is called. If the field is read about as often as the record is built, expect this finding."
35
36def records.step(+u: Unit, +node: Lint.Node, found: Bool) -> Bool:
37 match node:
38 case Lint.Node{
39 Lint.Field{b, q},
40 n,
41 s,
42 Con{Lint.Node{Lint.Forall{fb, fq}, fn, fs, fk, ff}, rest},
43 f
44 }:
45 True{}
46 case _:
47 found
48
49# The datatypes among `nodes` with a field whose written type is a function, by the name the check gives them, onto
50# `out`.
51def records(nodes: List<&2, Lint.Node>, out: List<&2, String>) -> List<&2, String>:
52 match nodes:
53 case Nil{}:
54 out
55 case Con{Lint.Node{Lint.Datatype{t}, n, s, kids, f}, rest}:
56 records(
57 rest,
58 Lists.push(
59 String,
60 Lists.when(String, Lint.fold(~Unit, ~Bool, ~records.step, Unit{}, kids, False{}), t),
61 out
62 )
63 )
64 case Con{node, rest}:
65 records(rest, out)
66
67def program.records(sources: List<&2, Lint.Source>, out: List<&2, String>) -> List<&2, String>:
68 match sources:
69 case Nil{}:
70 out
71 case Con{Lint.Source{path, ns, text, nodes}, rest}:
72 program.records(rest, records(nodes, out))
73
74# The datatype a type's nodes write, by the name the check gives it, or "" for another form (a function, a sort).
75def written(nodes: List<&2, Lint.Node>) -> String:
76 match nodes:
77 case Con{Lint.Node{Lint.Reference{t}, n, s, k, f}, rest}:
78 t
79 case Con{Lint.Node{Lint.TypeApplication{t}, n, s, k, f}, rest}:
80 t
81 case _:
82 ""
83
84# The binders of the templates among a definition's nodes whose type is one of `records`, onto `out`.
85def templates(
86 nodes: List<&2, Lint.Node>,
87 +records: List<&2, String>,
88 out: List<&2, U32>
89) -> List<&2, U32>:
90 match nodes:
91 case Nil{}:
92 out
93 case Con{Lint.Node{Lint.Parameter{b, Lint.Template{}}, n, s, kids, f}, rest}:
94 templates(
95 rest,
96 records,
97 Lists.push(
98 U32,
99 Lists.when(U32, List.contains(~String, ~String.eq, records, written(kids)), b),
100 out
101 )
102 )
103 case Con{node, rest}:
104 templates(rest, records, out)
105
106def is_lambda(node: Lint.Node) -> Bool:
107 match node:
108 case Lint.Node{Lint.Lambda{b, q}, n, s, k, f}:
109 True{}
110 case _:
111 False{}
112
113# Whether a node below `path` is computed when a record of functions is built: under no lambda, and in a construction
114# with a lambda among its fields (`found`, once one is).
115def is_built(path: List<&2, Lint.Above>, found: Bool) -> Bool:
116 match path:
117 case Nil{}:
118 found
119 case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest}:
120 False{}
121 case Con{Lint.Above{Lint.Node{Lint.Construction{t}, n, s, kids, f}, at}, rest}:
122 is_built(rest, Bool.or(found, Lists.any(~Lint.Node, ~is_lambda, kids)))
123 case Con{a, rest}:
124 is_built(rest, found)
125
126def visit(+owner: Owner, +path: List<&2, Lint.Above>, +node: Lint.Node) -> List<&2, Lint.Finding>:
127 match owner node:
128 case Owner{templates, name} Lint.Node{Lint.Variable{b}, template, span, k, f}:
129 Lint.finding(
130 Lint.Information{},
131 Bool.and(
132 List.contains(~U32, ~U32.is_eq, templates, b),
133 Bool.and(Lint.is_live(path), is_built(path, False{}))
134 ),
135 span,
136 message(template, name)
137 )
138 case _ _:
139 []
140
141# The findings in the definitions among `nodes` that have templates of `records`, onto `out` (last first).
142def defs(
143 nodes: List<&2, Lint.Node>,
144 +records: List<&2, String>,
145 out: List<&2, Lint.Finding>
146) -> List<&2, Lint.Finding>:
147 match nodes:
148 case Nil{}:
149 out
150 case Con{Lint.Node{Lint.Definition{t, u}, +n, s, +kids, f}, rest}:
151 defs(
152 rest,
153 records,
154 Lists.onto(
155 &2,
156 Lint.Finding,
157 Lint.visit(
158 ~Owner,
159 ~Lint.Finding,
160 ~visit,
161 Owner{templates(kids, records, []), n},
162 [Lint.Node{Lint.Definition{t, u}, n, s, kids, f}]
163 ),
164 out
165 )
166 )
167 case Con{node, rest}:
168 defs(rest, records, out)
169
170def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
171 Lint.done(
172 List.reverse(
173 &2,
174 Lint.Finding,
175 defs(Lint.Here.nodes(here), program.records(Lint.Here.sources(here), []), [])
176 )
177 )
178
179def rule() -> Lint.Rule:
180 Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}