Speed up typechecking of dict, set and list expressions#9477
Merged
msullivan merged 2 commits intopython:masterfrom Oct 18, 2020
Merged
Speed up typechecking of dict, set and list expressions#9477msullivan merged 2 commits intopython:masterfrom
msullivan merged 2 commits intopython:masterfrom
Conversation
1213635 to
7e06318
Compare
Typechecking of dict, set, and list literals currentlly goes through typechecking of the generic dict/set/list constructor internally. This is usually fine but becomes horrendously slow when the number of items is large: - for generic methods, `infer_arg_types_in_context` is called twice - `infer_arg_types_in_context` is O(n**2) where `n` is the number of arguments, which, in the case of a literal, is the number of items. Add an `O(n)` fast path for deriving the type of simple container literal expressions. This fast path only handle a subset of cases but it provides a tremendous speedup for the relatively common case of large literal constants. The real-world example that motivated this change is a 1889 lines long dict constant representing the parsed value of a mock JSON response from a 3rd party service, where typechecking previously took upwards of 50s and is now down to under 1s with this fast path.
7e06318 to
b01b068
Compare
msullivan
reviewed
Oct 18, 2020
Collaborator
msullivan
left a comment
There was a problem hiding this comment.
This is fantastic and I'm thrilled to merge it. This has been a pretty silly pain point for a while. Could you add docstrings to the fast path functions explaining the rationale and what cases are covered by the fast paths?
Contributor
Author
|
Added docstrings as requested |
Collaborator
|
Thank you! |
This was referenced Dec 7, 2020
Collaborator
|
Just wanted to chime in and say this is great! :-) Thanks again! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Typechecking of dict, set, and list literals currently
goes through typechecking of the generic dict/set/list
constructor internally. This is usually fine but becomes
horrendously slow when the number of items is large:
infer_arg_types_in_contextiscalled twice
infer_arg_types_in_contextis O(n**2) wherenisthe number of arguments, which, in the case of a
literal, is the number of items.
Add an
O(n)fast path for deriving the type of simplecontainer literal expressions. This fast path only handle
a subset of cases but it provides a tremendous speedup for
the relatively common case of large literal constants.
The real-world example that motivated this change is a
1889 lines long dict constant representing the parsed value
of a mock JSON response from a 3rd party service, where
typechecking previously took upwards of 50s and is now
down to under 1s with this fast path.