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

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

Comienza con argparse.ArgumentParser y parse_args(), usando la reproducción repetida de --item=x del issue para observar la escalabilidad. Inspecciona los PR enlazados en busca de trabajo que ya esté abordando este comportamiento. Se considera terminado cuando analizar una lista de opciones muy larga ya no presenta el crecimiento O(N^2) reportado.