Fix quadratic-time ModuleNode.sort_types_by_inheritance #5139
Conversation
|
This needs further work; will update when it's ready. |
|
The failing tests are probably mostly an unrelated issue to do with a new version of line_profiler. So they may not be to do with this PR. I'll rerun the tests on this PR when that's fixed. |
thanks! I'm seeing failures on the internal version of this as well, though; I'll have to debug those and add more tests to Cython. |
|
The problem is the sort comparator I defined isn't a total ordering. I'll have to implement a proper topological sort. |
It should take O(n log n) time now.
swolchok
force-pushed
the
fix-quadratic-sort-types-by-inheritance
branch
from
b825a21 to
d6b2900
Compare
Co-authored-by: scoder <[email protected]>
|
Closing and reopening to rerun CI |
|
I simplified the implementation. @swolchok, could you please validate that this doesn't lead to a performance regression on your side again? |
|
I'll merge this since it's a major improvement. We can have further PRs if we need more. Thanks! |
At Meta, we have some large .pyx files generated by https://github.com/facebook/fbthrift . I found through profiling that
ModuleNode.sort_types_by_inheritancewas taking about 10% of the time for Cython to process our largest file, and through inspection that it took quadratic time. This PR changessort_types_by_inheritanceto usesortedto avoid quadratic time, with the result thatsort_type_by_inheritancetake a small fraction of a percent on the same large workload after this change.This function seems to be covered by the
cdef_class_orderandooo_base_classestests; they failed during development and now pass.