Yapf: Pathologically slow example

[DRMacIver]

The following takes 25 seconds to reformat on my machine. In comparison, many significantly larger files run in under a second:

specialElements = frozenset((
    (namespaces['html'], 'address'),
    (namespaces['html'], 'applet'),
    (namespaces['html'], 'area'),
    (namespaces['html'], 'article'),
    (namespaces['html'], 'aside'),
    (namespaces['html'], 'base'),
    (namespaces['html'], 'basefont'),
    (namespaces['html'], 'bgsound'),
    (namespaces['html'], 'blockquote'),
    (namespaces['html'], 'body'),
    (namespaces['html'], 'br'),
    (namespaces['html'], 'button'),
    (namespaces['html'], 'caption'),
    (namespaces['html'], 'center'),
    (namespaces['html'], 'col'),
    (namespaces['html'], 'colgroup'),
    (namespaces['html'], 'command'),
    (namespaces['html'], 'dd'),
    (namespaces['html'], 'details'),
    (namespaces['html'], 'dir'),
    (namespaces['html'], 'div'),
    (namespaces['html'], 'dl'),
    (namespaces['html'], 'dt'),
    (namespaces['html'], 'embed'),
    (namespaces['html'], 'fieldset'),
    (namespaces['html'], 'figure'),
    (namespaces['html'], 'footer'),
    (namespaces['html'], 'form'),
    (namespaces['html'], 'frame'),
    (namespaces['html'], 'frameset'),
    (namespaces['html'], 'h1'),
    (namespaces['html'], 'h2'),
    (namespaces['html'], 'h3'),
    (namespaces['html'], 'h4'),
    (namespaces['html'], 'h5'),
    (namespaces['html'], 'h6'),
    (namespaces['html'], 'head'),
    (namespaces['html'], 'header'),
    (namespaces['html'], 'hr'),
    (namespaces['html'], 'html'),
    (namespaces['html'], 'iframe'),
    # Note that image is commented out in the spec as "this isn't an
    # element that can end up on the stack, so it doesn't matter,"
    (namespaces['html'], 'image'),
    (namespaces['html'], 'img'),
    (namespaces['html'], 'input'),
    (namespaces['html'], 'isindex'),
    (namespaces['html'], 'li'),
    (namespaces['html'], 'link'),
    (namespaces['html'], 'listing'),
    (namespaces['html'], 'marquee'),
    (namespaces['html'], 'menu'),
    (namespaces['html'], 'meta'),
    (namespaces['html'], 'nav'),
    (namespaces['html'], 'noembed'),
    (namespaces['html'], 'noframes'),
    (namespaces['html'], 'noscript'),
    (namespaces['html'], 'object'),
    (namespaces['html'], 'ol'),
    (namespaces['html'], 'p'),
    (namespaces['html'], 'param'),
    (namespaces['html'], 'plaintext'),
    (namespaces['html'], 'pre'),
    (namespaces['html'], 'script'),
    (namespaces['html'], 'section'),
    (namespaces['html'], 'select'),
    (namespaces['html'], 'style'),
    (namespaces['html'], 'table'),
    (namespaces['html'], 'tbody'),
    (namespaces['html'], 'td'),
    (namespaces['html'], 'textarea'),
    (namespaces['html'], 'tfoot'),
    (namespaces['html'], 'th'),
    (namespaces['html'], 'thead'),
    (namespaces['html'], 'title'),
    (namespaces['html'], 'tr'),
    (namespaces['html'], 'ul'),
    (namespaces['html'], 'wbr'),
    (namespaces['html'], 'xmp'),
    (namespaces['svg'], 'foreignObject')
))

[gwelymernans]

Oof...Yeah, this is because it's trying _all_ combinations of newlines for this data literal. (This is also a good test for a heuristic that I put into YAPF.) In the meantime, you could put a "# yapf: disable" at the end of the data literal so that we won't mess up the formatting:

FOO = frozenset((
1,
...
)) # yapf: disable

[DRMacIver]

I confess this example doesn't actually come from my code, so I'm not in _immediate_ need of working around it. I'm just experimenting at this point.

[gwelymernans]

Quite alright. :-) It's good to know where we're doing less than good.

[DRMacIver]

Here is a possibly related example which is instead pathological in space: https://gist.github.com/DRMacIver/8c2a4c3fdbb923c4a27c

It takes more than 100MB to run (and is extracted from an example only about 4 times larger that crashed when it hit my default 2GB ulimit)

[lins05]

Here is another example that's very slow to format:

answers = [
    ('', ''),
    # 1
    ('', ''),
    # 2
    ('', ''),
    # 3
    ('', ''),
    # 4
    ('', ''),
    # 5
    ('', ''),
    # 6
    ('', ''),
]

It feels like the time grows exponentially with the items in this array.

[ppolewicz]

OP issue now takes less than 2.5 seconds on my laptop. I guess some optimization was done along the way.

[hayd]

Perhaps this/these should be added as a (timed) test?

[gwelymernans]

That isn't a bad idea. I've not set up Python performance tests before. Any thoughts on the best way to do this? (I assume it involves the timeit module somehow.)

[chkno]

User (CPU) time running over first example above, measured at every yapf commit:

[w0rp]

I would like to see some more work on improving the performance of this tool. I tried it out for the first time today, and for the most part the formatting seems to be pretty good. yapf currently takes a few seconds at a time to format most of the files in the codebase I work on primarily these days. If that time could be reduced to sub-second speeds, then yapf could be used for automatically formatting Python code in Vim pretty well.

[ppolewicz]

@w0rp see the --lines switch. It should allow you to run the common case in milliseconds when changes are precisely pointed to.

[w0rp]

Even with --lines, yapf can take a few seconds to execute on some of my source files.

[ppolewicz]

Oh. Please create a new issue for this, including configuration,
commandline arguments and code.

04.09.2016 15:17 "w0rp" [email protected] napisał(a):

Even with --lines, yapf can take a few seconds to execute on some of my
source files.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/yapf/issues/39#issuecomment-244603029, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAsWGdsTGDsBUy63hI1O8PNtRGN0rvwRks5qmsTPgaJpZM4D1egy
.

[gwelymernans]

@w0rp Yes, please file a new issue for that. It may be another pathological example that we should optimize for.

Performance is more of a journey than a goal. There will always be ways to do things better. :-) So having an issue open for performance isn't great. It's better to have them for pathological examples.

[campos-ddc]

Is this still an issue? Takes 0.611 seconds in my machine.

[gwelymernans]

@campos-ddc I believe this is no longer an issue. Any new slow examples should file new bugs. :-)