argparse.ArgumentParser is slow when parsing a very long option list #96859
Description
Bug report
The following parser exhibits O(N^2) behavior when parsing a very long option list (e.g. --item=a --item=b ...):
parser = argparse.ArgumentParser(description="test")
parser.add_argument('--item', dest='accumulate', action='append')Here is a simple repro that measures the time parse_args() take depending on the number of options:
#!/usr/bin/env python3
import argparse
from datetime import datetime
def run_test(num_iterations):
"""Parse a list with 'append' action and measure the time it takes."""
parser = argparse.ArgumentParser(description="test")
parser.add_argument('--item', dest='accumulate', action='append')
start = datetime.now()
args = parser.parse_args(['--item=x' for _ in range(num_iterations)])
end = datetime.now()
diff = end - start
print(f"{num_iterations:8} iterations: {diff} s")
def main():
for i in range(8, 18):
run_test(pow(2, i))
if __name__ == "__main__":
main()The output on my machine:
> ./repro.py
256 iterations: 0:00:00.002699 s
512 iterations: 0:00:00.008444 s
1024 iterations: 0:00:00.028508 s
2048 iterations: 0:00:00.104813 s
4096 iterations: 0:00:00.389232 s
8192 iterations: 0:00:01.552962 s
16384 iterations: 0:00:06.132139 s
32768 iterations: 0:00:25.233547 s
65536 iterations: 0:01:51.921170 s
131072 iterations: 0:07:42.047914 s
Your environment
- CPython versions tested on: HEAD of main (a9d58fe)
- Operating system and architecture: Fedora release 36 (Thirty Six)