Optimize cases with long potential simple_keys #555
Merged
Conversation
This file contains 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
liggitt
reviewed
Nov 26, 2019
niemeyer
requested changes
Nov 29, 2019
efficient lookup in yaml_parser_fetch_value().
|
Thanks again for the first pass. Are you up for considering the addition of the single_key index? I'd like to have something to include in the next set of Kubernetes patch releases around the first week of January. |
niemeyer
added a commit
that referenced
this pull request
Jan 21, 2020
Message from original commit (53403b5): This change introduces an index to lookup token numbers referenced by simple_keys in O(1), thus significantly reducing the performance impact of certain abusively constructed snippets. When we build up the simple_keys stack, we count on the (formerly named) staleness check to catch errors where a simple key is required but would be > 1024 chars or span lines. The previous simplification that searches the stack from the top can go 1024 keys deep before finding a "stale" key and stopping. I added a test that shows that this consumes ~3s per 1MB of document size.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
When we build up the simple_keys stack, we count on the (formerly named) staleness check to catch errors where a simple key is required but would be > 1024 chars or span lines. The previous simplification that searches the stack from the top can go 1024 keys deep before finding a "stale" key and stopping. I added a test that shows that this consumes ~3s per 1MB of document size.
I split that staleness check back out into a separate loop so that we don't unnecessarily re-process a bunch of keys just to get down to the ones that might have gone stale.