Skip to content

Prevent repetitive recursive scanning of dicts when making them long-… #1052

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.

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

Merged
merged 1 commit into from
Jul 24, 2018

Conversation

dhalbert
Copy link
Collaborator

@dhalbert dhalbert commented Jul 19, 2018

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 to make_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 to make_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.

@tannewt tannewt self-requested a review July 24, 2018 01:14
Copy link
Member

@tannewt tannewt left a comment

Choose a reason for hiding this comment

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

Looks great to me! Can't wait to try this with Celeste.py. Thanks!

@tannewt tannewt merged commit 08def6b into adafruit:3.x Jul 24, 2018
@dhalbert dhalbert deleted the speed-up-dict-long-lived branch August 6, 2019 02:37
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants