Skip to content
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

Time to process a long set/lists of strings increases exponentially with the number of strings #484

Open
MartinFalatic opened this issue Apr 17, 2019 · 1 comment
Labels
bug Something isn't working
Milestone

Comments

@MartinFalatic
Copy link

Describe the bug
A clear and concise description of what the bug is.

To Reproduce
Steps to reproduce the behavior:

  1. Run bandit on any of the files attached in Examples.zip

  2. Notice how the run time increases exponentially (user time approximately quadruples as the number of strings in the set doubles.)

(This also occurs if the large sequence of short strings is a list rather than a set.)

Python2 versus Python 3: Though the latter runs a little faster overall, the exponential nature of this problem is still evident.

Expected behavior
The run time is linear despite the extra-long data.

Additionally, it'd be useful to be able to see exactly what file is being processed to locate such bottlenecks, versus the 242 [0.. 50.. 100.. 150.. output. Debug output is far too noisy for this purpose when scoping hundreds of files.

Bandit version

For Python 2:

bandit 1.5.1
  python version = 2.7.15 (default, Jan 12 2019, 21:07:57) [GCC 4.2.1 Compatible Apple LLVM 10.0.0 (clang-1000.11.45.5)]

For Python3 (slightly faster):

bandit 1.5.1
  python version = 3.6.8 (default, Jan 25 2019, 14:34:44) [GCC 4.2.1 Compatible Apple LLVM 10.0.0 (clang-1000.11.45.5)]

Additional context
n/a

@ericwb ericwb added the bug Something isn't working label May 9, 2019
@ericwb ericwb added this to the Near Future milestone May 9, 2019
@amacfie
Copy link
Contributor

amacfie commented Jan 1, 2020

If user time quadruples as the number of strings in the set doubles then the running time would be quadratic.

Interesting that this happens as the AST gets wider but the depth stays the same.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

3 participants