Repository navigation
Commit 10b3b79
committed
perf(rust-lsp): O(1) type map in the registry build + macro-expansion dedup
The four kernel rust files' wall time was a CONSTANT ~63.5 s that no
resolution-side fix moved -- because it was not resolution. The shared
all_defs registry build had two lookups INSIDE its registration loop
(receiver auto-registration probe via cbm_registry_lookup_type, and the
trait-linkage scan), and before finalize the registry has no buckets: both
probes were full linear scans over the types registered so far. On the
1.4M-def shared build that is ~10^10 strcmps ~= 63 s, paid once by the
building file while the sibling null-filter files waited on the once-guard
for exactly the same wall time. This is the checklist's own
lookup-in-registration-loop pattern -- invisible on small per-file builds.
Fix: a CBMIdxMemo (new in lsp_neg_memo.h: exact-match, strcmp-verified
string-key -> index map, arena-backed, first-put-wins to mirror the linear
scans' first-match semantics) maintained alongside every add_type in
rust_populate_cross_registry; both probes become O(1).
Also rides along: a per-root-invocation macro-expansion memo. Kernel
macro_rules are self-recursive (define_sizes! re-invokes itself) and the
expansion fallback ("no pattern matched -- still expand the first rule")
made recursion non-convergent: unbounded BREADTH under the depth-8 guard
turned 2-44 source invocations into ~200k expansions (each a fresh
tree-sitter parse of the substituted body). Identical (macro, substituted
text) now expands once per chain; the memo resets at each top-level source
site so per-site attribution is untouched, and the arg re-parse dedup only
applies at recursion depth > 0. Side effect: the eval-step cap no longer
exhausts, so a few previously-truncated real calls now resolve (kernel:
+25 edges).
Verified: kernel rust subtree byte-identical before/after (sorted node and
edge sets, exact); rust_lsp suite 506 passed.
Signed-off-by: Martin Vogel <[email protected]>1 parent 2f11a4d commit 10b3b79
3 files changed
Lines changed: 156 additions & 8 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
139 | 139 | | |
140 | 140 | | |
141 | 141 | | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
142 | 230 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
29 | 29 | | |
30 | 30 | | |
31 | 31 | | |
| 32 | + | |
32 | 33 | | |
33 | 34 | | |
34 | 35 | | |
| |||
3159 | 3160 | | |
3160 | 3161 | | |
3161 | 3162 | | |
| 3163 | + | |
| 3164 | + | |
| 3165 | + | |
| 3166 | + | |
| 3167 | + | |
| 3168 | + | |
| 3169 | + | |
| 3170 | + | |
| 3171 | + | |
| 3172 | + | |
| 3173 | + | |
| 3174 | + | |
| 3175 | + | |
| 3176 | + | |
3162 | 3177 | | |
3163 | 3178 | | |
3164 | 3179 | | |
| |||
3239 | 3254 | | |
3240 | 3255 | | |
3241 | 3256 | | |
| 3257 | + | |
| 3258 | + | |
| 3259 | + | |
| 3260 | + | |
| 3261 | + | |
| 3262 | + | |
| 3263 | + | |
| 3264 | + | |
| 3265 | + | |
| 3266 | + | |
| 3267 | + | |
| 3268 | + | |
| 3269 | + | |
| 3270 | + | |
3242 | 3271 | | |
3243 | 3272 | | |
3244 | 3273 | | |
| |||
5342 | 5371 | | |
5343 | 5372 | | |
5344 | 5373 | | |
| 5374 | + | |
| 5375 | + | |
| 5376 | + | |
| 5377 | + | |
| 5378 | + | |
| 5379 | + | |
| 5380 | + | |
| 5381 | + | |
| 5382 | + | |
| 5383 | + | |
| 5384 | + | |
| 5385 | + | |
| 5386 | + | |
| 5387 | + | |
| 5388 | + | |
| 5389 | + | |
| 5390 | + | |
| 5391 | + | |
5345 | 5392 | | |
5346 | 5393 | | |
5347 | 5394 | | |
| |||
5358 | 5405 | | |
5359 | 5406 | | |
5360 | 5407 | | |
| 5408 | + | |
5361 | 5409 | | |
5362 | 5410 | | |
5363 | 5411 | | |
| |||
5398 | 5446 | | |
5399 | 5447 | | |
5400 | 5448 | | |
5401 | | - | |
| 5449 | + | |
5402 | 5450 | | |
5403 | 5451 | | |
5404 | 5452 | | |
5405 | 5453 | | |
5406 | 5454 | | |
5407 | 5455 | | |
| 5456 | + | |
| 5457 | + | |
5408 | 5458 | | |
5409 | 5459 | | |
5410 | 5460 | | |
| |||
5413 | 5463 | | |
5414 | 5464 | | |
5415 | 5465 | | |
5416 | | - | |
5417 | | - | |
5418 | | - | |
5419 | | - | |
5420 | | - | |
5421 | | - | |
| 5466 | + | |
| 5467 | + | |
| 5468 | + | |
5422 | 5469 | | |
5423 | 5470 | | |
5424 | 5471 | | |
| |||
5437 | 5484 | | |
5438 | 5485 | | |
5439 | 5486 | | |
5440 | | - | |
| 5487 | + | |
| 5488 | + | |
5441 | 5489 | | |
5442 | 5490 | | |
5443 | 5491 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
174 | 174 | | |
175 | 175 | | |
176 | 176 | | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
177 | 189 | | |
178 | 190 | | |
179 | 191 | | |
| |||
0 commit comments