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

Bắt đầu với argparse.ArgumentParser và parse_args(), sử dụng cách tái hiện lặp lại --item=x trong issue để quan sát khả năng mở rộng. Kiểm tra các PR được liên kết để tìm những công việc đã xử lý hành vi này. Được xem là hoàn thành khi việc phân tích một danh sách tùy chọn rất dài không còn thể hiện mức tăng trưởng O(N^2) đã được báo cáo.