performance/bang_after_fork.bend

bend-lint-rules@0.2.0.0 · 175 lines · 12 definitions

1# performance/bang_after_fork: a `!` call that runs after a fork of the same evaluation, so Bend runs it
2# on the CPU pool, not on the GPU: in its definition, a let before it forks (a parallel let, or a value
3# that calls a definition under which a parallel let runs), or one of its arguments does.
4# Heuristics: a bang that follows the host's forks in one evaluation runs on the CPU pool ("bend guide
5# shaders"); a `!` call is not one of those forks: Bend's radix sort benchmark, three `!` calls in a row,
6# took the same time with IO steps between them. Measured on a discrete GPU, a numeric bang that took
7# 0.55 s on the GPU after an IO step took 3.9 s, its time on the CPU pool, after a parallel let, after a
8# let whose value forked in a call, and with an argument that forked; after a let whose value looped
9# without forking, it stayed on the GPU. A short call loses little on the CPU pool. An IO step (`<-` in a
10# `do` block) starts a new evaluation, so a fork before one does not count; nor does a fork in a
11# definition that calls this one, which the rule does not follow. A `!` call of a definition under which
12# no parallel let runs, or of one that returns Unit, is left to performance/gpu_fit and
13# performance/drop_in_bang: they ask to remove the `!`.
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
17import bend-lint-api@0.2.0.0/shared/names.bend as Names
18import bend-lint-api@0.2.0.0/shared/sets.bend as Sets
19import bend-lint-rules@0.2.0.0/performance/deep_call_in_fork.bend as Deep
20import bend-lint-rules@0.2.0.0/performance/gpu_fit.bend as GpuFit
21
22# Types
23# =====
24
25# What judging a file's calls reads: the program's definitions, by the name the check gives them; those under which a
26# parallel let runs (see GpuFit.program.under); and where the file writes `!(`.
27type Program is Data:
28  Program{defs: Map<&2, Maybe<&2, Lint.Def>>, under: Set(), bangs: List<&2, U32>}
29
30# Functions
31# =========
32def message(callee: String) -> String:
33  callee
34    ++ "! runs after a fork in the same evaluation (no IO step between them), so Bend runs it on the CPU pool, not on the GPU. GPU: measured 3.9 s for a numeric fork tree, against 0.55 s after the fix. CPU (`--gpu off`): no change. JS: no GPU, so no change. Confidence: high, as Bend's scheduler decides it. Put an IO step, such as `t : Nat <- IO.now()`, between the forks and this call, as Bend's slash boss demo does. If this call is short, so that the CPU pool runs it as fast, expect this finding."
35
36# The definition an application below `path` calls by name on the host: not with `!`, as a `!` call runs on the GPU,
37# and a `!` call after it stays there.
38def host.visit(
39  +bangs: List<&2, U32>,
40  +path: List<&2, Lint.Above>,
41  +node: Lint.Node
42) -> List<&2, String>:
43  match node:
44    case Lint.Node{
45      Lint.Application{},
46      n,
47      s,
48      Con{Lint.Node{Lint.Reference{t}, rn, Some{Lint.Span{p, beg, end}}, rk, rf}, args},
49      f
50    }:
51      Bool.pick(List<&2, String>, List.contains(~U32, ~U32.is_eq, bangs, end), [], [t])
52    case _:
53      []
54
55# Whether `nodes` fork on the host when they run: a call among them or under them, made without `!`, is of a
56# definition under which a parallel let runs.
57def forks(nodes: List<&2, Lint.Node>, program: Program) -> Bool:
58  match program:
59    case Program{defs, under, bangs}:
60      Sets.has_any(Lint.visit(~List<&2, U32>, ~String, ~host.visit, bangs, nodes), under, False{})
61
62# The nodes of a let (`kids`) that run before the rest of its block, its last node: its binders and values.
63def let.values(+kids: List<&2, Lint.Node>) -> List<&2, Lint.Node>:
64  List.take(&2, Lint.Node, kids, Nat.sub(Lists.length(&2, Lint.Node, kids), 1n))
65
66# Whether the let of `kids` forks before the rest of its block, if the node is in it (`last`): it is a parallel let
67# (`parallel`), or a value of it forks.
68def let.forks(last: Bool, parallel: Bool, kids: List<&2, Lint.Node>, program: Program) -> Bool:
69  match last parallel:
70    case False{} _:
71      False{}
72    case True{} True{}:
73      True{}
74    case True{} False{}:
75      forks(let.values(kids), program)
76
77# Whether a fork runs before the node below `path`, in the same evaluation, or `found`: a let above it, whose rest of
78# block it is in, forks (a parallel let, or a value that forks), and no lambda (the rest of an IO step) comes between.
79def after(path: List<&2, Lint.Above>, +program: Program, found: Bool) -> Bool:
80  match path found:
81    case _ True{}:
82      True{}
83    case Nil{} False{}:
84      False{}
85    case Con{Lint.Above{Lint.Node{Lint.Lambda{b, q}, n, s, k, f}, at}, rest} False{}:
86      False{}
87    case Con{Lint.Above{Lint.Node{Lint.Body{}, n, s, k, f}, at}, rest} False{}:
88      False{}
89    case Con{Lint.Above{Lint.Node{Lint.Destructure{q}, n, s, +kids, f}, at}, rest} False{}:
90      after(
91        rest,
92        program,
93        let.forks(Deep.is_last(kids, at), Nat.is_gt(Deep.binders(kids, 0n), 1n), kids, program)
94      )
95    case Con{Lint.Above{Lint.Node{Lint.Let{}, n, s, +kids, f}, at}, rest} False{}:
96      after(rest, program, let.forks(Deep.is_last(kids, at), False{}, kids, program))
97    case Con{a, rest} False{}:
98      after(rest, program, False{})
99
100# Whether a fork runs before a call with `args` below `path`, in the same evaluation, if it is `asked`: an argument
101# forks, or a let above it does.
102def after.if(
103  asked: Bool,
104  args: List<&2, Lint.Node>,
105  path: List<&2, Lint.Above>,
106  +program: Program
107) -> Bool:
108  match asked:
109    case True{}:
110      after(path, program, forks(args, program))
111    case False{}:
112      False{}
113
114# The finding about an application below `path`, if it is a `!` call of a definition that forks, made after a fork.
115def visit(
116  +program: Program,
117  +path: List<&2, Lint.Above>,
118  +node: Lint.Node
119) -> List<&2, Lint.Finding>:
120  match program node:
121    case Program{
122      +defs,
123      +under,
124      +bangs
125    } Lint.Node{
126      Lint.Application{},
127      n,
128      span,
129      Con{Lint.Node{Lint.Reference{+t}, callee, Some{Lint.Span{p, beg, end}}, k, f}, args},
130      facts
131    }:
132      Lint.finding(
133        Lint.Warning{},
134        after.if(
135          List.contains(
136            ~U32,
137            ~U32.is_eq,
138            bangs,
139            end
140          )
141            && Sets.has(under, t)
142            && Bool.not(GpuFit.is_drop(Names.find(Lint.Def, defs, t), t)),
143          args,
144          path,
145          Program{defs, under, bangs}
146        ),
147        span,
148        message(callee)
149      )
150    case _ _:
151      []
152
153# The findings in the file of `here`, which writes `!(` where `bangs` say: none, if it writes none.
154def scanned(+here: Lint.Here, bangs: List<&2, U32>) -> Lint.Ask(List<&2, Lint.Finding>):
155  match bangs:
156    case Nil{}:
157      Lint.done([])
158    case Con{b, rest}:
159      +sources = Lint.Here.sources(here)
160      +defs = Lint.Program.defs(sources, Map.new(&2, Maybe<&2, Lint.Def>))
161      Lint.done(
162        Lint.visit(
163          ~Program,
164          ~Lint.Finding,
165          ~visit,
166          Program{defs, GpuFit.program.under(sources, defs), Con{b, rest}},
167          Lint.Here.nodes(here)
168        )
169      )
170
171def run(+here: Lint.Here) -> Lint.Ask(List<&2, Lint.Finding>):
172  scanned(here, GpuFit.bangs(Lint.Here.text(here), 0, []))
173
174def rule() -> Lint.Rule:
175  Lint.Rule{Lint.Needs{False{}, False{}}, [], Lint.OnFile{run}}