Time to process a long set/lists of strings increases exponentially with the number of strings
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 8.3k
- Forks
- 835
- Avg merge
- 5d 3h
- Merged PRs (30d)
- 1
Description
Describe the bug
A clear and concise description of what the bug is.
To Reproduce
Steps to reproduce the behavior:
-
Run bandit on any of the files attached in Examples.zip
-
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
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reproducing the slowdown with the attached Examples.zip and a Bandit run, comparing runtime as the number of strings changes. Profile the scan to identify the operation causing the exponential behavior and inspect how progress output reports files. Done means runtime is approximately linear for long string sets or lists, with any file-identification output change covered as appropriate.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- devtools, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100