Significantly speedup ESP on large expressions that contain many strings by yilei · Pull Request #3467 · psf/black (original) (raw)

Description

Previously, when ESP 1) merges strings in StringMerger; 2) strips parens in StringParenStripper, it finds and does one transform for one string group. Each transform will create a new line with 1) one group of strings merged; 2) one group of strings' parens stripped. This new line is then re-checked by those transformers. This is O(n^2) complexity.

Since these transformers won't cause line breaks, the same transforms can be done at one pass, and it only creates one new line. The new approach is O(n).

Tested on the example from #3340 (not compiled, since I'm failing to use cibuildwheel to compile with mypyc on my machines):

  1. Before this change, it took ~111 seconds to finish after I increased the recursionlimit to 1M
  2. After this change, it took ~3.7s
  3. In the stable style without ESP, this file takes ~2.5s. The increase is now sane.

Fixes #3340, since this no longer triggers recursion limit errors.

Hopefully this also solves #2314

Checklist - did you ...