performance/template_value_field.bend

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