argparse.ArgumentParser is slow when parsing a very long option list

Open
#96,859 7 comments 1 reaction 0 assignees View on GitHub

@serhiy-storchaka is already working on this.

Since Oct 2, 2024.

  • #124909 by @serhiy-storchaka — open

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
25/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
python
Domain
cli, performance

Research direction

Start with argparse.ArgumentParser and parse_args(), using the issue's repeated --item=x reproduction to observe the scaling. Inspect the linked PRs for work already addressing the behavior. Done means parsing a very long option list no longer exhibits the reported O(N^2) growth.

Written by the indexing model from the issue text.

Description

performance stdlib type-feature

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 (a9d58feccfd956dc99195af6872b06446738d7db)
  • Operating system and architecture: Fedora release 36 (Thirty Six)
Linked PRs
  • gh-124740
  • gh-124745
  • gh-124909
Dominant language
Python
Stars
77.2k
Forks
36k
Avg merge
1d 9h
Merged PRs (30d)
558

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from python/cpython

All issues in python/cpython

Similar issues

More Python issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.