Repository navigation
Heavily nested structures are very slow to proceed #3796
Description
Hi,
the dictionary below takes more than 30s to be processed. If the codebase contains more of such structures, it takes painfully long time to check it.
For now we use #3789 as a workaround to skip such slow parts.
Cheers,
yed_
testing env:
MB Pro 2013
Python 3.6
Mypy 0.521
testing file:
input = {
'body': {
'token': {
'type': 'string',
'required': False
},
'payloads': {
'type': 'list',
'required': True,
'schema': {
'type': 'dict',
'schema': {
'message': {
'type': 'string',
'required': True
},
'notification': {
'type': 'dict',
'required': True,
'schema': {
'body': {
'type': 'dict',
'schema': {
'type': {
'type': 'string',
'required': True
},
'data': {
'type': 'dict',
'required': True,
'schema': {
'bid': {
'type': 'string',
'required': False
},
'url': {
'type': 'string',
'required': False
}
}
}
}
}
}
}
}
}
}
}
}
Activity
gvanrossum commented on Aug 3, 2017
Wow. Confirmed -- on my Mac it takes 21s to process that file.
refi64 commented on Aug 3, 2017
I wonder if this is somehow similar to:
https://spin.atomicobject.com/2016/04/26/swift-long-compile-time/
refi64 commented on Aug 3, 2017
(I mean algorithm-wise.)
ilevkivskyi commented on Aug 7, 2017
It looks like we have two problems here. This code typechecks quickly:
while this takes around 41 seconds on my desktop:
Independently, this takes even more, around 1 minute 12 seconds:
Taking into account that dict translates into an overloaded generic function, it looks like both problems combine in the original example.
JukkaL commented on Aug 7, 2017
Yeah, there clearly are various scenarios in which type checking is exponential in time. This is basically a known problem, but I doubt anybody has done a careful analysis of potential sources of exponential behavior. A potential simple fix is to use caching for the inferred type of an expression. I think that the tuple (identity of an expression, type context) could be used as a cache key, as long as as the cache is cleared at certain points -- for example, after leaving a scope or after each statement. I'm not 100% sure though.
hauntsaninja commented on Dec 7, 2020
The example in the original report is fixed by #9477