[red-knot] use fixpoint iteration for all cycles#14029
Conversation
CodSpeed Performance ReportMerging #14029 will degrade performances by 5.98%Comparing Summary
Benchmarks breakdown
|
|
|
Nice on bringing down the regression. I'm still somewhat surprised that we see an 11% perf regression and a 4 perf regression in the salsa benchmarks (that don't have any cycles). |
|
Yeah I planned to do some more looking at profiles; thanks for doing that! |
carljm
force-pushed
the
cjm/fixpoint
branch
6 times, most recently
from
bbd7090 to
3189bd8
Compare
This is split out of #14029, to reduce the size of that PR, and to validate that this "fallback type" support in `TypeInference` doesn't come with a performance cost. It also improves the reliability and debuggability of our current (temporary) cycle handling. In order to recover from a cycle, we have to be able to construct a "default" `TypeInference` where all expressions and definitions have some "default" type. In our current cycle handling, this "default" type is just unknown or a todo type. With fixpoint iteration, the "default" type will be `Type::Never`, which is the "bottom" type that fixpoint iteration starts from. Since it would be costly (both in space and time) to actually enumerate all expressions and definitions in a scope, just to insert the same default type for all of them, instead we add an optional "missing type" fallback to `TypeInference`, which (if set) is the fallback type for any expression or definition which doesn't have an explicit type set. With this change, cycles can no longer result in the dreaded "Missing key" errors looking up the type of some expression.
carljm
changed the title
|
There was a problem hiding this comment.
This looks good to me. Do you think it would be useful to have any documentation on when/where to add cycle fallbacks or documentation on the cycle fallback function itself?
And very impressive that this results in only a 1% perf regression in the cold case. Nice work!
Yes, I can add that. I think the latter is probably the most useful and will serve as the former by example, too? Not sure where to put the former that it would be discoverable when needed. Also, Salsa's panic message if you do hit a cycle on a query without cycle handling is pretty informative and would be enough to find existing examples to copy. |
|
Changed my mind -- too many cases of cycle handling, felt too redundant to repeat the same docs on each. So I added a paragraph to the doc comment at the top of |
2 participants
Pulls in the latest Salsa main branch, which supports fixpoint iteration, and uses it to handle all query cycles.
With this, we no longer need to skip any corpus files to avoid panics.
Latest perf results show a 6% incremental and 1% cold-check regression. This is not a "no cycles" regression, as tomllib and typeshed do trigger some definition cycles (previously handled by our old
infer_definition_typesfallback toUnknown). We don't currently have a benchmark we can use to measure the pure no-cycles regression, though I expect there would still be some regression; the fixpoint iteration feature in Salsa does add some overhead even for non-cyclic queries.I think this regression is within the reasonable range for this feature. We can do further optimization work later, but I don't think it's the top priority right now. So going ahead and acknowledging the regression on CodSpeed.
Mypy primer is happy, so this doesn't regress anything on our currently-checked projects. I expect it probably unlocks adding a number of new projects to our ecosystem check that previously would have panicked.
Fixes #13792
Fixes #14672