Skip to content
← Back

src/syntax/process/compile-expressions/retry_site_stats.ghul

1
namespace Syntax.Process is
2
use Ghul.Disposable
3
use Ghul.Pipes
4
5
use Collections.LIST
6
use Collections.MAP
7
use Collections.SET
8
9
enum RetrySiteKind is
10
// Re-walks a subtree under a narrower expected type or other
11
// information an earlier walk produced.
12
REWALK_WITH_INFORMATION,
13
14
// Re-walks a subtree under a different reading or lowering.
15
ALTERNATIVE,
16
17
// Opens a speculation level that the sites above roll back;
18
// walks nothing a second time.
19
DIAGNOSTIC_SCOPE
20
si
21
22
// Every local re-walk compile-expressions performs, by the name its
23
// `RETRY_SITE_STATS.enter` call gives, with the kind of re-walk it
24
// is. A re-walk with information is one the obligation queue is
25
// meant to replace, so the list is expected to shrink; a site is
26
// entered only once it is listed here, which puts every new one in
27
// front of review.
28
class RETRY_SITES is
29
inventory: Collections.List[(site: string, kind: RetrySiteKind)] static =>
30
[
31
("attributes.constructor_fallback", RetrySiteKind.ALTERNATIVE),
32
("bindings.assignment_target_probe", RetrySiteKind.ALTERNATIVE),
33
("calls.constructor_constraint_retry", RetrySiteKind.REWALK_WITH_INFORMATION),
34
("calls.constructor_needs_retry", RetrySiteKind.REWALK_WITH_INFORMATION),
35
("calls.constructor_sibling_specialisation", RetrySiteKind.REWALK_WITH_INFORMATION),
36
("calls.delegate_value_construction", RetrySiteKind.REWALK_WITH_INFORMATION),
37
("calls.normalise_spread", RetrySiteKind.ALTERNATIVE),
38
("calls.resolve_deferred_defaults", RetrySiteKind.REWALK_WITH_INFORMATION),
39
("calls.try_overload_after_null", RetrySiteKind.REWALK_WITH_INFORMATION),
40
("calls.try_overload_on_partial", RetrySiteKind.REWALK_WITH_INFORMATION),
41
("fusion.harvest", RetrySiteKind.ALTERNATIVE),
42
("fusion.restore", RetrySiteKind.ALTERNATIVE),
43
("lambdas.convert_to_delegate", RetrySiteKind.ALTERNATIVE),
44
("operators.resolve_deferred_index", RetrySiteKind.REWALK_WITH_INFORMATION),
45
("operators.resolve_deferred_operands", RetrySiteKind.REWALK_WITH_INFORMATION),
46
("tuples.sequence_element_rewalk", RetrySiteKind.REWALK_WITH_INFORMATION)
47
]
48
49
kind_of(site: string) -> RetrySiteKind static is
50
for entry in inventory do
51
if entry.site =~ site then
52
return entry.kind
53
fi
54
od
55
56
throw System.InvalidOperationException("retry site {site} is not in the inventory")
57
si
58
si
59
60
// Prototype measurement, printed alongside RETRY_STATS when
61
// GHUL_RETRY_STATS is set: how often each local re-walk in
62
// compile-expressions fires, how deeply the re-walks nest, and how
63
// many re-walks each body pays for under its whole-body walks.
64
// GHUL_RETRY_STATS_LOG names a file each firing and each body is
65
// appended to, one tab-separated line apiece, for aggregating
66
// several builds.
67
class RETRY_SITE_STATS is
68
enabled: bool static
69
_log: IO.TextWriter? static
70
71
_depth: int static
72
_information_depth: int static
73
74
_sites: MAP[string, RETRY_SITE_TOTALS] static
75
_site_order: LIST[string] static
76
_bodies: LIST[RETRY_BODY_TALLY] static
77
_finished: LIST[RETRY_BODY_TALLY] static
78
_next_body: int static
79
80
init() static is
81
enabled = Driver.COMPILER_ENVIRONMENT.retry_stats
82
_sites = MAP[string, RETRY_SITE_TOTALS]()
83
_site_order = LIST[string]()
84
_bodies = LIST[RETRY_BODY_TALLY]()
85
_finished = LIST[RETRY_BODY_TALLY]()
86
87
let path = Driver.COMPILER_ENVIRONMENT.retry_stats_log
88
89
if enabled /\ path? then
90
let writer = IO.StreamWriter(path, true)
91
writer.auto_flush = true
92
_log = writer
93
fi
94
si
95
96
// Call immediately before a site rolls back to re-walk; the
97
// re-walk is counted as nested inside every other re-walk whose
98
// scope has not yet been disposed.
99
enter(site: string) -> RETRY_SITE_SCOPE static is
100
let kind = RETRY_SITES.kind_of(site)
101
102
if Semantic.INFERENCE_TRACE.enabled then
103
Semantic.INFERENCE_TRACE.rewalk(site, "{kind}")
104
fi
105
106
if !enabled then
107
return RETRY_SITE_SCOPE(false, false)
108
fi
109
110
let is_information = kind == RetrySiteKind.REWALK_WITH_INFORMATION
111
112
_depth = _depth + 1
113
114
if is_information then
115
_information_depth = _information_depth + 1
116
fi
117
118
_record(site, kind, _depth)
119
120
if _bodies.count > 0 then
121
let body = _bodies[_bodies.count - 1]
122
123
body.rewalks = body.rewalks + 1
124
body.rewalks_this_walk = body.rewalks_this_walk + 1
125
126
if body.rewalks_this_walk > body.max_rewalks_per_walk then
127
body.max_rewalks_per_walk = body.rewalks_this_walk
128
fi
129
130
if _depth > body.max_depth then
131
body.max_depth = _depth
132
fi
133
134
if is_information then
135
body.information_rewalks = body.information_rewalks + 1
136
body.information_this_walk = body.information_this_walk + 1
137
138
if body.information_this_walk > body.max_information_per_walk then
139
body.max_information_per_walk = body.information_this_walk
140
fi
141
142
143
if _information_depth > body.max_information_depth then
144
body.max_information_depth = _information_depth
145
fi
146
fi
147
fi
148
149
return RETRY_SITE_SCOPE(true, is_information)
150
si
151
152
// A diagnostic scope walks nothing twice, so it is counted but
153
// does not nest.
154
note(site: string) static is
155
if !enabled then
156
return
157
fi
158
159
_record(site, RetrySiteKind.DIAGNOSTIC_SCOPE, _depth)
160
si
161
162
leave(is_information: bool) static is
163
_depth = _depth - 1
164
165
if is_information then
166
_information_depth = _information_depth - 1
167
fi
168
si
169
170
begin_body() -> int static is
171
if !enabled then
172
return -1
173
fi
174
175
let id = _next_body
176
_next_body = _next_body + 1
177
178
_bodies.add(RETRY_BODY_TALLY(id))
179
180
return id
181
si
182
183
begin_walk() static is
184
if !enabled \/ _bodies.count == 0 then
185
return
186
fi
187
188
_bodies[_bodies.count - 1].rewalks_this_walk = 0
189
_bodies[_bodies.count - 1].information_this_walk = 0
190
si
191
192
end_body(id: int, walks: int, function: Semantic.Symbols.Function?, location: Source.LOCATION) static is
193
if !enabled \/ _bodies.count == 0 then
194
return
195
fi
196
197
// A body whose walk threw leaves its tally behind; drop it.
198
while _bodies.count > 1 /\ _bodies[_bodies.count - 1].id != id do
199
_bodies.remove_at(_bodies.count - 1)
200
od
201
202
let body = _bodies[_bodies.count - 1]
203
_bodies.remove_at(_bodies.count - 1)
204
205
body.walks = walks
206
body.name = "{if function? then function.qualified_name else "<no symbol>" fi} at {location}"
207
208
for site in body.sites do
209
_sites[site].bodies = _sites[site].bodies + 1
210
od
211
212
_finished.add(body)
213
214
if let log = _log then
215
log.write_line("body\t{body.name}\t{body.walks}\t{body.rewalks}\t{body.max_rewalks_per_walk}\t{body.max_depth}\t{body.information_rewalks}\t{body.max_information_depth}\t{body.max_information_per_walk}")
216
fi
217
si
218
219
_record(site: string, kind: RetrySiteKind, depth: int) static is
220
if !_sites.contains_key(site) then
221
_sites[site] = RETRY_SITE_TOTALS(kind)
222
_site_order.add(site)
223
fi
224
225
let t = _sites[site]
226
227
t.firings = t.firings + 1
228
t.depth_sum = t.depth_sum + cast long(depth)
229
230
if depth > t.max_depth then
231
t.max_depth = depth
232
fi
233
234
let body_name =
235
if _bodies.count > 0 then
236
let body = _bodies[_bodies.count - 1]
237
238
if !body.sites.contains(site) then
239
body.sites.add(site)
240
fi
241
242
"{body.id}"
243
else
244
t.outside_bodies = t.outside_bodies + 1
245
"-"
246
fi
247
248
if let log = _log then
249
log.write_line("site\t{kind}\t{site}\t{body_name}\t{depth}")
250
fi
251
si
252
253
report() static is
254
if !enabled \/ _finished.count == 0 then
255
return
256
fi
257
258
let error = IO.Std.error
259
260
error.write_line("retry site stats: {_finished.count} bodies")
261
error.write_line(" kind\tsite\tfirings\tbodies\toutside-body\tmax-depth\tmean-depth")
262
263
for site in _site_order do
264
let t = _sites[site]
265
let mean = cast double(t.depth_sum) / cast double(t.firings)
266
267
error.write_line(" {t.kind}\t{site}\t{t.firings}\t{t.bodies}\t{t.outside_bodies}\t{t.max_depth}\t{mean:F2}")
268
od
269
270
let with_rewalks = LIST[RETRY_BODY_TALLY]()
271
let with_information = LIST[RETRY_BODY_TALLY]()
272
let repeated mut = 0
273
let repeated_with_rewalks mut = 0
274
275
for body in _finished do
276
if body.rewalks > 0 then
277
with_rewalks.add(body)
278
fi
279
280
if body.information_rewalks > 0 then
281
with_information.add(body)
282
fi
283
284
if body.walks > 1 then
285
repeated = repeated + 1
286
287
if body.rewalks > 0 then
288
repeated_with_rewalks = repeated_with_rewalks + 1
289
fi
290
fi
291
od
292
293
error.write_line("retry site stats: {with_rewalks.count} bodies with a local re-walk, {with_information.count} with a re-walk with information")
294
error.write_line("retry site stats: {repeated} bodies took more than one outer walk, {repeated_with_rewalks} of them with a local re-walk")
295
296
_write_products("outer walks x most local re-walks in one walk", with_rewalks, body => body.walks * body.max_rewalks_per_walk)
297
_write_products("outer walks x most re-walks with information in one walk", with_information, body => body.walks * body.max_information_per_walk)
298
299
error.write_line(" heaviest bodies: walks\tre-walks\tmost-in-one-walk\tmax-depth\tinformation-re-walks\tmost-information-in-one-walk\tmax-information-depth\tname")
300
301
let remaining = LIST[RETRY_BODY_TALLY](with_rewalks)
302
303
for _ in 0..25 do
304
if remaining.count == 0 then
305
break
306
fi
307
308
let heaviest mut = 0
309
310
for i in 1..remaining.count do
311
if _weight(remaining[i]) > _weight(remaining[heaviest]) then
312
heaviest = i
313
fi
314
od
315
316
let body = remaining[heaviest]
317
remaining.remove_at(heaviest)
318
319
error.write_line(" {body.walks}\t{body.rewalks}\t{body.max_rewalks_per_walk}\t{body.max_depth}\t{body.information_rewalks}\t{body.max_information_per_walk}\t{body.max_information_depth}\t{body.name}")
320
od
321
si
322
323
_weight(body: RETRY_BODY_TALLY) -> long static =>
324
cast long(body.walks * body.max_rewalks_per_walk) * 100000L + cast long(body.rewalks)
325
326
_write_products(title: string, bodies: LIST[RETRY_BODY_TALLY], product: RETRY_BODY_TALLY -> int) static is
327
let products = MAP[int, int]()
328
329
for body in bodies do
330
let p = product(body)
331
let count mut = 0
332
products.try_get_value(p, count ref)
333
products[p] = count + 1
334
od
335
336
let keys = LIST[int](products.keys)
337
keys.sort()
338
339
IO.Std.error.write_line(" {title}:")
340
341
for k in keys do
342
IO.Std.error.write_line(" {k}: {products[k]}")
343
od
344
si
345
si
346
347
struct RETRY_SITE_SCOPE: Disposable is
348
_active: bool
349
_is_information: bool
350
351
init(active: bool, is_information: bool) is
352
_active = active
353
_is_information = is_information
354
si
355
356
dispose() is
357
if _active then
358
RETRY_SITE_STATS.leave(_is_information)
359
fi
360
si
361
si
362
363
class RETRY_SITE_TOTALS is
364
kind: RetrySiteKind public
365
firings: int public
366
bodies: int public
367
outside_bodies: int public
368
max_depth: int public
369
depth_sum: long public
370
371
init(kind: RetrySiteKind) is
372
self.kind = kind
373
si
374
si
375
376
class RETRY_BODY_TALLY is
377
id: int public
378
name: string public
379
walks: int public
380
rewalks: int public
381
rewalks_this_walk: int public
382
max_rewalks_per_walk: int public
383
max_depth: int public
384
information_rewalks: int public
385
information_this_walk: int public
386
max_information_per_walk: int public
387
max_information_depth: int public
388
sites: SET[string] public
389
390
init(id: int) is
391
self.id = id
392
name = ""
393
sites = SET[string]()
394
si
395
si
396
si