very long run time and/or stack overflow during inference about astroid HOT 13 CLOSED

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

Profile of analysis of a similar class with just 14 methods, which takes 30 seconds.

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

The raw data which was used to generate the above image.

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

The raw data which was used to generate the above image.

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

As a minor update, my attempt to time the inference on the somewhat smaller class is still running, ten days later. The cputime is 9 days, 20:58:43.

I'm killing it now.

from astroid.

Original comment by Sylvain Thénault (BitBucket: sthenault, GitHub: @sthenault?):

there is much probably an infinite loop somewhere which doesn't end into an
infinite recursion error and so ends endlessly.

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

My hypothesis is different: I believe it's tracing all the possible assignment paths in a permutative manner, yielding O(n^n) performance. With smaller numbers (3-10), it does complete, just exponentially slower for each new method.

from astroid.

Original comment by BitBucket: eevee, GitHub: @eevee?:

I looked into this a bit in the course of trying to improve pylint performance on a large and terrible codebase. :)

Buck is correct; this is equivalent to O(n^n). The following happens:

• Encounter trans = self.transaction in method 1. Try to infer self.transaction.
• Encounter self.transaction = trans in method 1. Infer trans. Find trans = self.transaction in method 1. Skip it because it's already being inferred.
• Encounter self.transaction = trans in method 2. Infer trans. Find trans = self.transaction in method 2. Try to infer self.transaction.
• Encounter self.transaction = trans in method 1...

This repeats rather ridiculously. Every assignment of self.transaction tries to infer from every assignment to it. Method 1 tries to infer from methods 2 through n, which each try to infer from methods 2 through n except themselves, etc. So each of n methods tries to infer from n - 1 methods which try to infer from n - 2 methods, and so on, producing O(n!). It only terminates at all because the inference of a particular expression is prevented from inferring itself; otherwise method 1 would try to infer itself forever.

I think I have a small fix for this, which involves extending the existing recursive-inference protection to avoid inferring the same attribute on an instance of the same class twice in the call stack. I'll post it as soon as I figure out how to do that with hg and bitbucket. :)

from astroid.

Original comment by Sylvain Thénault (BitBucket: sthenault, GitHub: @sthenault?):

sounds good eevee, thanks !

don't hesitate to ask for help for submitting your patch.

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

+1 +1

from astroid.

Original comment by Buck Evan (BitBucket: bukzor, GitHub: @bukzor?):

@eevee Put your diff on http://paste.pound-python.org/ if you're really stuck on bitbucket/hg.

This page always gives me enough information to do what I need with hg: http://mercurial.selenic.com/wiki/GitConcepts#Command_equivalence_table

from astroid.

Original comment by Sylvain Thénault (BitBucket: sthenault, GitHub: @sthenault?):

@eevee any update on this? Astroid should be released soon, it would be great if it could include a fix for this one.

from astroid.

Original comment by BitBucket: eevee, GitHub: @eevee?:

Finally submitted pull request #28, which includes a commit to fix this issue.

from astroid.

Original comment by Sylvain Thénault (BitBucket: sthenault, GitHub: @sthenault?):

Avoid recursively inferring the same attr on the same class. Closes #7

from astroid.