Skip to content

[ty] Handle cycles when finding implicit attributes #19833

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Aug 8, 2025
Merged

[ty] Handle cycles when finding implicit attributes #19833

merged 1 commit into from
Aug 8, 2025

Conversation

dcreager
Copy link
Member

@dcreager dcreager commented Aug 8, 2025 •
edited
Loading

The minimal reproduction of astral-sh/ty#948 is an example of a class with implicit attributes whose types end up depending on themselves. Our existing cycle detection for infer_expression_types is usually enough to handle this situation correctly, but when there are very many of these implicit attributes, we get a combinatorial explosion of running time and memory usage.

Adding a separate cycle handler for ClassLiteral::implicit_attribute lets us catch and recover from this situation earlier.

Closes astral-sh/ty#948

@dcreager dcreager requested a review from carljm as a code owner August 8, 2025 18:06
@dcreager dcreager added the ty Multi-file analysis & type inference label Aug 8, 2025
@github-actions GitHub Actions
Copy link
Contributor

github-actions bot commented Aug 8, 2025

Diagnostic diff on typing conformance tests

No changes detected when running ty on typing conformance tests ✅

@github-actions GitHub Actions
Copy link
Contributor

github-actions bot commented Aug 8, 2025

mypy_primer results

No ecosystem changes detected ✅

Memory usage changes were detected when running on open source projects 
trio (https://github.com/python-trio/trio)
- TOTAL MEMORY USAGE: ~159MB
+ TOTAL MEMORY USAGE: ~167MB
-     struct fields = ~9MB
+     struct fields = ~10MB
-     memo metadata = ~22MB
+     memo metadata = ~23MB

sphinx (https://github.com/sphinx-doc/sphinx)
-     struct metadata = ~11MB
+     struct metadata = ~12MB
-     memo metadata = ~38MB
+     memo metadata = ~40MB

prefect (https://github.com/PrefectHQ/prefect)
-     struct metadata = ~25MB
+     struct metadata = ~26MB

@codspeed-hq CodSpeed HQ
Copy link

codspeed-hq bot commented Aug 8, 2025

CodSpeed Instrumentation Performance Report

Merging #19833 will improve performances by 7.15%

Comparing dcreager/flax-hang (cac8c77) with main (0095ff4)

Summary

⚡ 2 improvements
✅ 40 untouched benchmarks

Benchmarks breakdown

Benchmark BASE HEAD Change
⚡ ty_micro[many_enum_members] 103.2 ms 96.3 ms +7.15%
⚡ ty_micro[many_string_assignments] 73.3 ms 69.8 ms +5.04%

@codspeed-hq CodSpeed HQ
Copy link

codspeed-hq bot commented Aug 8, 2025

CodSpeed WallTime Performance Report

Merging #19833 will improve performances by 9.43%

Comparing dcreager/flax-hang (cac8c77) with main (0095ff4)

Summary

⚡ 1 improvements
✅ 6 untouched benchmarks

Benchmarks breakdown

Benchmark BASE HEAD Change
⚡ medium[pandas] 26.9 s 24.6 s +9.43%

carljm
carljm approved these changes Aug 8, 2025
View reviewed changes
Copy link
Contributor

@carljm carljm left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice find! I suspect the win here is not "catching the cycle sooner" but that we are now memoizing a chunk of work that we did not memoize before, and presumably that work was previously being repeated a lot in cycle iteration, and now is not.

This is a good reminder that there are potentially significant performance wins hiding in "add memoization" that aren't necessarily obvious until we hit a pathological case.

@dcreager dcreager merged commit 3a542a8 into main Aug 8, 2025
39 checks passed
@dcreager dcreager deleted the dcreager/flax-hang branch August 8, 2025 21:01
@dcreager dcreager mentioned this pull request Aug 8, 2025
Closed
@MichaReiser
Copy link
Member

This does seem to increae memory usage a fair bit. I'm not suggesting that this wasn't the right fix. But it might have been interesting to measure the total memory usage on a large project and comparing it to main (by using TY_MEMORY_REPORT=full).

@AlexWaygood
Copy link
Member

The minimal reproduction of astral-sh/ty#948 is an example of a class with implicit attributes whose types end up depending on themselves.

Is it worth adding something like this as a micro-benchmark, to ensure that we don't regress on this in the future?

Lee-W added a commit to astronomer/ruff that referenced this pull request Aug 11, 2025
@Lee-W
fixup! [ty] Handle cycles when finding implicit attributes (astral-sh…
3218171 
…#19833)
Lee-W added a commit to astronomer/ruff that referenced this pull request Aug 11, 2025
@Lee-W
fixup! [ty] Handle cycles when finding implicit attributes (astral-sh…
d4804b3 
…#19833)
dcreager added a commit that referenced this pull request Aug 11, 2025
@dcreager
Merge branch 'main' into dcreager/bound-typevar
5b8c6e1 
* main: (31 commits)
  Add AIR301 rule (#17707)
  Avoid underflow in default ranges before a BOM (#19839)
  Update actions/download-artifact digest to de96f46 (#19852)
  Update docker/login-action action to v3.5.0 (#19860)
  Update rui314/setup-mold digest to 7344740 (#19853)
  Update cargo-bins/cargo-binstall action to v1.14.4 (#19855)
  Update actions/cache action to v4.2.4 (#19854)
  Update Rust crate hashbrown to v0.15.5 (#19858)
  Update Rust crate camino to v1.1.11 (#19857)
  Update Rust crate proc-macro2 to v1.0.96 (#19859)
  Update dependency ruff to v0.12.8 (#19856)
  SIM905: Fix handling of U+001C..U+001F whitespace (#19849)
  RUF064: offer a safe fix for multi-digit zeros (#19847)
  Clean up unused rendering code in `ruff_linter` (#19832)
  [ty] Add Salsa caching to `TupleType::to_class_type` (#19840)
  [ty] Handle cycles when finding implicit attributes (#19833)
  [ty] fix goto-definition on imports (#19834)
  [ty] Implement stdlib stub mapping (#19529)
  [`flake8-comprehensions`] Fix false positive for `C420` with attribute, subscript, or slice assignment targets (#19513)
  [ty] Implement module-level `__getattr__` support (#19791)
  ...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@carljm carljm carljm approved these changes

@AlexWaygood AlexWaygood Awaiting requested review from AlexWaygood AlexWaygood is a code owner

@sharkdp sharkdp Awaiting requested review from sharkdp sharkdp is a code owner

Assignees
No one assigned
Labels
ty Multi-file analysis & type inference
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Hang in flax/nnx/variablelib.py
4 participants
@dcreager @MichaReiser @AlexWaygood @carljm