Appearance
| 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 |