Prevent repetitive recursive scanning of dicts when making them long-… #1052
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.
Fixes #1051.
I tracked down the slowness of imports to the long-lived dict conversion at the end of an
import
. Printing out the args tomake_dict_long_lived()
showed it was being called zillions of times with the same arg, which I think is the globals dict. I'm not exactly sure of the structure of the globals dict, but its entries apparently include backpointers to globals dict itself.Because of the
max_depth
countdown, the recursion eventually stops,but the number of calls dramatically increases as the number of entries in the global dict increases. I think it's something like O(n^10).Originally I made a simple fix that tested if a dict itself was already long-lived, and just returned immediately. However, I think that was wrong because additional non-long-lived entries can be added to a long-lived dict. For instance, multiple imports will add non-long-lived entries to the globals on each import.
The
map
structure in a dict contains some bit fields. I added one more:.scanning
, which marks the dict as being in the process of becoming long-lived. If the same dict is passed again tomake_dict_long_lived()
, it will see that the.scanning
flag is set and just return. When the children of the dict have been made long-lived, the flag is cleared before the new pointer is returned.There's no available bit field for
mp_obj_fun_bc_t
or for properties, which are the other objects the long-lived conversion code recurses on. However, these don't seem to present the same problem.@tannewt Take a look. We can discuss it when you're back.