Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Performance penalty: combinatorial explosion in transform #16

Open
DNikolaevAtRocket opened this issue Jul 6, 2021 · 3 comments · May be fixed by #64
Open

Performance penalty: combinatorial explosion in transform #16

DNikolaevAtRocket opened this issue Jul 6, 2021 · 3 comments · May be fixed by #64
Labels
enhancement New feature or request help wanted Extra attention is needed

Comments

@DNikolaevAtRocket
Copy link

Description

Using docopt for building utilities with relatively wide range of options is pretty limited because of a huge performance penalty.
Namely, a combinatorial explosion may happen in the transform function: the pattern expansion (like ((-a | -b) (-c | -d)) => (-a -c | -a -d | -b -c | -b -d)) has unacceptable computational complexity.

A good example would be the GNU ls utility. See the sample below.

To Reproduce

The script below takes almost 3 seconds to run which is terribly slow for just to parse CLI arguments.

"""
ls with a subset of GNU options (that's not even all of them!)

Usage:
    ls [-a|-A] [--hide=PATTERN] [-I=PATTERN] [-dLR]
       [--color] [-h|--si] [--indicator-style=WORD|-p|-F|--file-type]
       [--format=WORD|-x|-m|-x|-l|-1|-C|-g|-n|-o] [-Giks]
       [--sort=WORD|-f|-U|-S|-t|-v|-X] [--group-directories-first] [-r]
       [--time=WORD|-u|-c] [--time-style=TIME_STYLE]
       [FILES ...]
    ls --help
    ls --version

Arguments:
    FILES
        list of files
"""
from docopt import docopt

args = docopt()
@h4l
Copy link
Contributor

h4l commented Aug 21, 2022

I noticed this while digging around in the commit history just now for another issue I reported. This change was introduced in some refactoring by the original author after the last release of docopt (0.6.2): ba4740e

i.e. the original author never released this change, but it got picked up into docopt-ng as it was in docopt's master branch.

@NickCrews
Copy link
Contributor

If anyone wants to tackle this, I will gladly review. Thanks for the bug report!

@bittner bittner added enhancement New feature or request help wanted Extra attention is needed labels May 31, 2023
@ThosRTanner
Copy link
Contributor

I don't think it's that commit that affects the performance. I've just undone that individual one and seen no difference in the time taken. (Although moving the definition of parent outside the function speeds it up from 2.6s to 2.5s roughly)

@ThosRTanner ThosRTanner linked a pull request Apr 10, 2024 that will close this issue
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request help wanted Extra attention is needed
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

This reworks the transform function somewhat to speed it up. ThosRTanner/docopt-ng
5 participants
@h4l @bittner @ThosRTanner @NickCrews @DNikolaevAtRocket